# How to calculate $9^{47^{51}} \mod 67$? [closed]

I've looked at some other related things on here, but this seems a little more complicated with the double exponentiation. Is there a general algorithm to calculate $a^{c_1^{c_2^{...^{c_n}}}} \mod p$ or something?

• Have you heard of Euler's theorem? Jun 18, 2016 at 8:29
• @Arthur I'll look into it, I'm only a beginner in math, so this is the first time I hear about it, thanks Jun 18, 2016 at 8:30
• See here and the scores of questions linked to that umbrella question. I would vote to close this as a dupe, but have promised not to do that. Apr 1, 2018 at 7:48

$$\phi(67)=66=2\cdot 3\cdot 11$$ and

By Fermat's Theorem, $$47^{51}\equiv47^{1}\equiv 47\pmod2$$ $$47^{51}\equiv47^{1}\equiv 47\pmod3$$ $$47^{51}\equiv47^{1}\equiv 47\pmod {11}$$

Thus, using Chinese Remainder $$47^{51}\equiv 47\pmod {66}$$

Thus, by Fermat' Little theorem: $$9^{47^{51}}\equiv 9^{47}\equiv 3^{94}\equiv 3^{28}\equiv (-64)^{28}\equiv ((-4)^3)^{28}\equiv (-4)^{84}\equiv (-4)^{18}\equiv 4^{18}\equiv 2^{36}\equiv -2^3\equiv -8\pmod{67}$$ , where $2^{33}\equiv -1$ comes from the fact that $2^{33}=\left(\frac 2{67}\right)=(-1)^{\frac{p^2-1}8}$

First focus on $47^{51}$ in your example. You must figure that out mod $66$, the latter number being the Euler totient of $67$. Let $r$ be that residue and then attack $9^r$ modulo $67$.

$67$ is a prime number, thus, Fermat's Theorem holds.

This implies

$$9^{66}=1 \pmod {67}$$ you should resolve now $$47^{51} = ? \pmod {66}$$

Consider that $66 = 2\cdot3\cdot11$, you can use the Chinese Remainder Theorem.

• Please put braces around $51$ in $47^{51}$. :-) Jun 18, 2016 at 8:32
• Yes, I was editing Jun 18, 2016 at 8:34
• Please check my edit to see a lot of nice features of latex :)
– Emre
Jun 18, 2016 at 8:34

First of all, $$9^{47^{51}}=3^{2\cdot47^{51}}$$

As $\phi(67)=\lambda(67)=66,$ $$3^{2\cdot47^{51}}\equiv3^{2\cdot47^{51}\pmod{66}}\pmod{67}$$

As $(2\cdot47^{51},66)=2,$ let us find $47^{51}\pmod{33}$

As $\lambda(33)=\cdots=10,51\equiv1\pmod{10},$

$$47^{51}\equiv47^1\pmod{33}\equiv14$$

$$\implies2\cdot47^{51}\equiv14\cdot2\pmod{66}$$

$$\implies3^{2\cdot47^{51}}\equiv3^{28}\pmod{67}$$

Now $3^4\equiv14,3^8=(3^4)^2\equiv14^2\equiv-5$

$\implies3^{28}=3^4\cdot(3^8)^3\equiv14\cdot(-5)^3\equiv14\cdot9\equiv-8\equiv-8+67$

• What is $\lambda(n)$?
– Emre
Jun 18, 2016 at 8:50
• @Emre wikipedia says it's Carmichael function Jun 18, 2016 at 8:51
• @Emre, See math.stackexchange.com/questions/167616/…, mathworld.wolfram.com/CarmichaelFunction.html, OR Carmichael_function Jun 18, 2016 at 8:54
• @OscarLanzi, $$\lambda(33)=(\lambda(11),\lambda(3))=(10,2)=10$$ Jun 18, 2016 at 9:10
• Got rid of comment, thought \$\lambda meant something else. Jun 18, 2016 at 9:11