Solution verification: $2851^{604^{20}}\overset{\text{?}} \equiv\pmod{14}$

Question

$$2851^{604^{20}}\equiv 9^{604^{20}}\equiv(-5)^{604^{20}}\equiv 5^{604^{20}}\pmod{14}$$ $$5^{\phi(14)}\equiv 1\pmod{14}$$ (Thanks for the remark in comments) $$\gcd(k,14)=1,k\in \mathbb N, k<14 ,k\in\{1,3,5,9,11,13\}\implies\phi(14)=6$$ $$604^{20}\equiv 4^{20}\equiv 4\pmod{6}$$ $$5^x\equiv 1\pmod{14}\implies 5^{x+4}\equiv5^4\pmod {14}\implies5^{604^{20}}\equiv5^4\equiv 9\equiv\pmod{14}$$ Therefore: $$2851^{604^{20}}\equiv 5\pmod{14}$$ Is this correct?

Answer 1

Close....

but in calculating $\phi(14)$ you forgot to include $1$ as one of the values relative prime to $14$.

It's a good idea to get used to the idea of calculating $\phi$ using it's multiple distributive property over primes.

$\phi(14) =\phi(2*7) =\phi(2)\phi(7) = (2-1)(7-1) = 6$.

Then we have $604^{20}\equiv 4^{20}\pmod 6$.

Calculating $4^{20}\pmod 6$ can be done are a variety of ways. But if you had a really difficult case you could use the Chinese Remainder theorem $4^{20}\equiv 0 \pmod 2$ and $4^{20}\equiv 1^{20\%\phi(3)=0}\equiv 1\pmod 3$ so $4^20\equiv 0\pmod 2$ and $1\pmod 3$ and the only option for that is $4^{20}\equiv 4 \pmod 6$.

.... or we could have simply done a few successiv squarings. $4^2\equiv 16\equiv 4\pmod 6$ so $4^k\equiv 4 \pmod 6$.

So we have $ 2851^{604^{20}}\equiv 5^4\pmod {14}$

And $5^4\equiv 25^2 \equiv 11^2 \equiv (-3)^2 \equiv 9\pmod {14}$.