1
$\begingroup$

I recently learnt modular arithmetic for finding remainders when huge numbers are to be divided by some number. However, I am stuck at this problem:

What is the remainder when $\displaystyle32^{32^{32}}$ is divided by $7$?

I suppose the idea here is to reduce the exponent $32^{32}$ to such a number that $32$ raised to $32^{32}$ and $32$ raised to that number will give the same remainder. But how do we do that?

$\endgroup$
5
$\begingroup$

${\rm mod}\ 3\!:\ 32^{32}\equiv (-1)^{32}\equiv 1,\ $ so $\ \color{#c00}{ 32^{32} = 1 + 3k}$

${\rm mod}\ 7\!:\ 32^{\large 32^{32}}\!\equiv 4^{\large \color{#c00}{32^{32}}}\!\equiv 4^{\large \color{#c00}{1+3k}}\equiv 4(4^{\large 3})^{\large k}\equiv 4(1)^{\large k}\equiv 4 $

$\endgroup$
3
$\begingroup$

Note that $32 \equiv 4$ mod $7$ so we can equally well work with $4^{32^{32}}$.

$4^3=64\equiv 1$ mod $7$ so we need to look at the exponent $32^{32}$ modulo $3$ - i.e. adding or subtracting $3$ to the exponent doesn't change the remainder on division by $7$.

Note that $2^2=4\equiv 1$ modulo 3, and so working mod $3$ we have $$32^{32}\equiv2^{32}=(2^2)^{16}\equiv 1^{16}=1$$

So, working mod $7$ we have $$32^{32^{32}}\equiv4^{32^{32}}\equiv 4^1=4$$

$\endgroup$
2
$\begingroup$

First show that the exponent $32^{32} \cong 2 \pmod 6$. Then $32^2 \cong 2 \pmod 7$ (by Fermat's Little theorem).

$\endgroup$
  • $\begingroup$ Why use modulo $6$ for the exponent? $\endgroup$ – Tejas Mar 14 '14 at 13:56
  • 1
    $\begingroup$ I get $32^{32}\equiv 4$ mod $6$ $\endgroup$ – Mark Bennet Mar 14 '14 at 14:18
  • $\begingroup$ @TejasAdsul a consequence of Fermat's theorem, note that if $a \equiv b \pmod{6}$, then $$ 32^a \equiv 32^b \pmod{7} $$ $\endgroup$ – Omnomnomnom Mar 14 '14 at 14:18
  • $\begingroup$ oops, sorry for the arithmetic error. $\endgroup$ – user44441 Mar 14 '14 at 19:46
1
$\begingroup$

Observe $2^3 \equiv 1$(mod 7). So $(32)^{3k} \equiv 1$ (mod 7). $32 = 3 \times 10 + 2$. So $$ {32}^ {{32}^{32}} \equiv {32}^{(3 \times 10 + 2)^{32}} \equiv 32^{2^{32}} \equiv 32^{3k+1} \equiv 32 \equiv 4 \; (mod \; 7)$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.