Euler's theorem: [3]^2014^2014 mod 98

Solution 1:

It seems you are mixing exponents and base numbers and what is to be calculated modulo $49$, and what is to be calculated modulo $42$. This is, in my opinion, the chief difficulty working with problems like this, and it's important to use the utmost care that you actually calculate the correct power in the correct modulus.

We want to know $3^{2014^{2014}} \pmod{98}$. Using the chinese remainder theorem, and the fact that the number is obviously odd, we now have left to calculate $3^{2014^{2014}} \pmod{49}$. In order to do that, we use Euler's theorem and try to figure out $2014^{2014} \pmod{42}$.

First of all, the reduction $2014 \equiv -2 \pmod {42}$ makes this a bit simpler. That means, in order to use Euler's theorem to calculate the power of $3$ modulo $49$, we don't need to bother with powers of $2014$ modulo $42$, it's enough to consider powers of $-2$.

Now, we want $(-2)^{2014} \pmod{42}$. Using the Chinese remainder theorem, we want to know $(-2)^{2014}$ modulo $7$, $3$ and $2$. Modulo $2$ and $3$ are easy, as $(-2)$ is congruent to $0$ and $1$, respectively.

Modulo $7$ we have Euler's theorem again, with $\phi(7) = 6$ and $2014 = 2010 + 4$, so $(-2)^{2014} \equiv (-2)^4 = 16 \pmod{7}$. We also see that $16 \equiv 1\pmod 3$ and $16\equiv 0\pmod 2$, so we must have $(-2)^{2014} \equiv 16 \pmod{42}$.

Going back to the base, this means that $$3^{2014^{2014}} \equiv 3^{(-2)^{2014}} \equiv 3^{16} \pmod{49}$$ So all that's left now is to calculate $3^{16} \pmod{49}$. This might be done by repeated squaring: $3^{16} = (((3^2)^2)^2)^2$. We have $$ 3^{16} = 9^8 = 81^4 \equiv (-17)^4 = 289^2 \equiv (-5)^2 = 25 \pmod{49} $$ So to get back to the original question, we know that $$ 3^{2014^{2014}} \equiv \cases{1 \pmod 2\\ 25\pmod{49}} $$ which means that it's congruent to $25$ modulo $98$.