Because we are better than machines

Number Theory Level 3

$\Large 32^{32^{32}} \bmod 7 = \, ?$

Do you like challenging your brain?. Enter the world where Calculators will not help

2 Cannot be determined 3 4 5 6 1

2 solutions

Chew-Seong Cheong
Jun 15, 2016

Since 32 and 7 are coprime integers, we can apply Euler's theorem .

$\begin{aligned} 32^{32^{32}} & \equiv 32^{32^{32} \text{ mod } \color{#3D99F6}{6}} \text{ (mod 7)} \quad \quad \small \color{#3D99F6}{\phi(7) = 6} \\ & \equiv 32^{(30+2)^ {32} \text{ mod } 6} \text{ (mod 7)} \\ & \equiv 32^{\color{#3D99F6}{2^ {32} \text{ mod } 6}} \text{ (mod 7)} \quad \quad \small \color{#3D99F6}{\text{We note that }2^n \equiv \begin{cases} 2 \text{ (mod 6)} & \text{if } n \text{ is odd} \\ 4 \text{ (mod 6)} & \text{if } n \text{ is even} \end{cases}} \\ & \equiv 32^{\color{#3D99F6}{4}} \text{ (mod 7)} \\ & \equiv 2^{20} \text{ (mod 7)} \\ & \equiv 2^{20 \text{ (mod 6)}} \text{ (mod 7)} \\ & \equiv 2^2 \text{ (mod 7)} \\ & \equiv \boxed{4} \text{ (mod 7)} \end{aligned}$

Abhay Tiwari
Jun 15, 2016

$\large \dfrac{{{\color{#D61F06}{32}}^{{\color{#3D99F6}{32}}^{32}}}}{7}$

$\large \dfrac{{{\color{#D61F06}{(28+4)}}^{{\color{#3D99F6}{32}}^{32}}}}{7}$

$\large \dfrac{{{\color{#D61F06}{4}}^{{\color{#3D99F6}{32}}^{32}}}}{7}$

$\large \dfrac{{{\color{#D61F06}{4}}^{\color{#3D99F6}{32×32×32×\dots×32(32 times)}}}}{7}$

$\large \dfrac{{{\color{#D61F06}{2}}^{\color{#3D99F6}{32×32×32×\dots×32(31 times)}}}}{7}$

$\large \dfrac{{{\color{#D61F06}{4}}^{\color{#3D99F6}{32×32×32×\dots×32(30 times)}}}}{7}$

$\large \dfrac{{{\color{#D61F06}{2}}^{\color{#3D99F6}{32×32×32×\dots×32(29 times)}}}}{7}$

Finally, we get $\dfrac{4}{7}, \text {gives remainder} \space =\boxed{\color{#3D99F6}{4}}$

Hmmm, I don't think your solution made any sense. The usual approach is by Mr Chew Seong, or by Carmichael's lambda function , or even euler's theorem , or by order of an element .

Pi Han Goh - 4 years, 12 months ago

Yes, we can do by any of the method you mentioned. But this is the basic approach for anyone who does not know any of the above. Although, it cannot be applied everywhere yet we can solve many questions. Otherwise Euler is a better option.

Abhay Tiwari - 4 years, 12 months ago

No. I'm saying that your solution made no sense in the first place!

Pi Han Goh - 4 years, 12 months ago

@Pi Han Goh – okay, where does it not make sense? which line? I hope i can help to make it a little sensible.

Abhay Tiwari - 4 years, 12 months ago

@Abhay Tiwari – Your fourth line onwards

Pi Han Goh - 4 years, 12 months ago

@Pi Han Goh – $\large \dfrac{{{\color{#D61F06}{4}}^{\color{#3D99F6}{32×32×32×\dots×32(32 times)}}}}{7}$ , can also be written as $\large \dfrac{{{\color{#D61F06}{(4^{32})}}^{\color{#3D99F6}{32×32×32×\dots×32(31 times)}}}}{7}$ .

now take only $\large \dfrac{{{\color{#D61F06}{4}}^{\color{#3D99F6}{32}}}}{7}$

$\large \dfrac{{{\color{#D61F06}{16}}^{\color{#3D99F6}{16}}}}{7}$ , which gives $\large \dfrac{{{\color{#D61F06}{2}}^{\color{#3D99F6}{16}}}}{7}$ .

$\large \dfrac{{{\color{#D61F06}{(2^{4}=16)}}^{\color{#3D99F6}{4}}}}{7}$ , which will again result in $\large \dfrac{{{\color{#D61F06}{16}}}}{7}$

which finally yields $\dfrac{2}{7}$ .

Now, we have $\large \dfrac{{{\color{#D61F06}{2}}^{\color{#3D99F6}{32×32×32×\dots×32(31 times)}}}}{7}$ . Again performing the same steps we will get $\dfrac{4}{7}$ at last. And we will see that this keeps on repeating.

Abhay Tiwari - 4 years, 12 months ago

@Abhay Tiwari – Your phrasing is unusual, but your solution is essentially the same as "order of an element".

Try to use more "equal signs" and "congruence signs" when needed.

Pi Han Goh - 4 years, 12 months ago

@Pi Han Goh – okay, I will try to elaborate more from now onward.

Abhay Tiwari - 4 years, 12 months ago

Because we are better than machines

Do you like challenging your brain?. Enter the world where Calculators will not help

2 solutions

0 pending reports