What is the correct way of calculating $2^{3^{4^{5^{6^{7}}}}} \bmod 9$?
The first step is obviously to use Euler’s theorem since $\gcd(2,9) = 1$ and $\phi(9)=6$.
But then I have to calculate $3^{4^{5^{6^{7}}}} \bmod 6$, and since $\gcd(3,6) = 3 != 1$ then I cannot use Euler’s theorem.
I have looked on the internet and found incorrect ways like $3^{4^{5^{6^{7}}}} = 9^{2^{5^{6^{7}}}}$, but that’s wrong. What is the correct way to go about this? Thanks in advance.
On
As you observed, by Euler's theorem we only need to know the exponent modulo $6$.
It is odd and divisible by $3$, so it is $\equiv 3\pmod 6$.
We get $\equiv 2^3=8 \pmod 9$.
On
Seems like you just need to see whether $3^{4^{5^{6^7}}}$ is even or odd.
$2^3 = 8 \equiv -1 \mod 9$ so $2^{3(2n)} \equiv 1 \mod 9$ and $2^{3(2n+1)} \equiv -1 \mod 9$.
Since the exponent is $3$ multiplied by itself some crazy number of times, it's odd, because all of the factors are odd.
Hence, $2^{3^{4^{5^{6^7}}}} \equiv 8 \mod 9$.
On
To answer the GCD question in a more general sense: When $\gcd(a,b)\neq 1$ for $a^x\pmod b$, split the problem and use Chinese Remainder Theorem: Factor $b$ into prime powers $p^k$ and solve the equation $a^x \pmod{p^k}$ individually. Then combine them.
Applying it here, $\gcd(3,6)=3$, not $1$ so we factor $6 = 2\cdot 3$. Let $x$ be exponent of $3$. Solving equations mod $2$ and $3$:
$$
\begin{align*}
3^x &\equiv 0 \pmod 3\\
3^x &\equiv 1^x \equiv 1 \pmod 2
\end{align*}
$$
Combining, you would get $3 \pmod 6$, the only value mod $6$ that can give $0,1$ mod $3$ and $2$. This then gives $2^3\equiv 8 \pmod 9$ . For multiple equations, there is a systematic way to do this combination one pair at a time using modular inverses.
If ${3^{4^{5^{6^{7}}}}} \equiv k \mod 6$ then
$2^{3^{4^{5^{6^{7}}}}}\equiv 2^k \mod 9$
${3^{4^{5^{6^{7}}}}} $ is a multiple of $3$. So ${3^{4^{5^{6^{7}}}}} \equiv 0,3 \mod 6$. ${3^{4^{5^{6^{7}}}}} \equiv 0 \mod 6$ if it is an even multiple of $3$ and ${3^{4^{5^{6^{7}}}}} $ if it is an odd multiple of three.
As the only prime factor of ${3^{4^{5^{6^{7}}}}} $ is $3$ it is an odd multiple of three.
So ${3^{4^{5^{6^{7}}}}} \equiv 3 \mod 6$
So $2^{3^{4^{5^{6^{7}}}}} \equiv 2^3 \equiv 8 \mod 9$.