3
$\begingroup$

$a = (5^4\ (\text{mod}\ 7))^3\ (\text{mod}\ 13)$

I know that I have to evaluate $5^4\ (\text{mod}\ 7)$ first, but how do you do that without using a calc?

then I have to evaluate $x^3\ (\text{mod}\ 13)$. Any tip?

3 Answers 3

6

$5^4=25\cdot 25\equiv 4\cdot 4 \equiv 2 \quad(\text{mod}\,7)$

$2^3 = 8 \equiv 8 \quad(\text{mod}\,13)$

3

Multiply in your head. Faster and safer than a calculator. No rummaging for the calculator, no dead battery, no keying errors.

Recall that $5^2=25$, remainder $4$ on division by $7$. Square again (that is, square $4$), take the remainder on division by $7$. We get $2$. Cube $2$.

-2

You can use the fact that multiplication distributes over addition. So, (5)(5)(5)(5)=(25)(5)(5)=(20+5)(5)(5)=((5)20+(5)5)5=(100+25)(5)=(125)5=(100+20+5)5=(100(5)+20(5)+5(5))=(500+100+25)=625. (700-70)=630, so 623 comes as the closest multiple of 7 to 625 which is not greater than 625. So, 625 (mod 7)≡2. Since two the third power equals eight, and 8 mod 13 is congruent to 8, we get 8. Personally, I like Argon's method better, but I didn't know that

a(b) (mod x)≡(a (mod x))(b (mod x)).