Can't use Euler's Theorem?

Question

I want to use Euler's theorem to calculate the following:

$14^{(2019^{2019})} \mod 60$

$a^{\phi(n)} \equiv 1 \mod n \iff \gcd(a,n) = 1$

Now I start with the outer one first:

$14^{(2019)}\mod 60 \iff \gcd(14,60) = 2$

Now I don't know how can I solve it ...

Can anyone suggest me any hints/further calculations?

Thank you in advance,

Kind Regards.

Answer 1

You can't use Euler's theorem because $\gcd(14,60) > 1$.

But you can use the Chinese remainder theorem, using $60 = 4 \cdot 15$: $$ \begin{align} 14^{(2019^{2019})} & \equiv \hphantom{-} 0 \bmod 4 \\ 14^{(2019^{2019})} & \equiv -1 \bmod 15 \end{align} $$ because $$ \begin{align} 14^2 & \equiv \hphantom{-} 0 \bmod 4 \\ 14\hphantom{^2} & \equiv -1 \bmod 15 \end{align} $$

Answer 2

You can calculate separately $2^{2019^{2019}}$ and $7^{2019^{2019}}$ first:

• It is not long to check that, if $n\ge 2$, $$2^n\equiv\begin{cases} 16&\text{ if }n\equiv 0\mod 4,\\ 32&\text{ if }n\equiv 1\mod 4,\\ 4&\text{ if }n\equiv 2\mod 4,\\ 8&\text{ if }n\equiv 3\mod 4. \end{cases}$$ So we have to compute the exponent mod. $4$: $$2019^{2019}\equiv (-1)^{2019}=-1\equiv3\mod 4\quad\text{and thus }\quad 2^{2019^{2019}}\equiv8\mod 60.$$
• As it is coprime to $60$, $7$ has order dividing $\varphi(60)=16$. Actually, $\;7^2=49\equiv -11\mod 60$, so $\;7^4\equiv (-11)^2=121\equiv 1$: $7$ has order $4$, so that $$7^{2019^{2019}}\equiv 7^{2019^{2019}\bmod4}\equiv 7^3\equiv-77\equiv -17\mod 60.$$

Answer 3

Like How to find last two digits of $2^{2016}$,

Get the last two digits of $16^{100}$ and $17^{100}$

what are the last two digits of $2016^{2017}$?

last two digits of $14^{5532}$?,

As $(14^n,60)=2^2$ for $n\ge2$

and as $14\equiv-1\pmod{15}\implies14^m\equiv(-1)^m$

$\implies F_{m+2}=14^{m+2}=14^2\cdot14^m\equiv14^2(-1)^m\pmod{15\cdot14^2}$

$F_{m+2}\equiv14^2(-1)^m\pmod{15\cdot4}$ as $15\cdot4$ divides $15\cdot14^2$

$F_{m+2}\equiv16(-1)^m\pmod{60}$

If $m$ is odd like here $2019^{2019}-2,$ $$F_{m+2}\equiv16(-1)\pmod{60}\equiv-16+60$$

Answer 4

Here's a way:

• Get rid of the gcd,
• then attempt by Euler's theorem, then reformulate mod 60

$$gcd(14,60)=2; gcd(14,15)=1; 14^{2019^{2019}}\equiv 14^{3^3}\equiv -1^3\equiv -1\bmod 15$$ which adding back a factor of 4 coincides with $44 \bmod 60$

Answer 5

$n\ge 2\,\Rightarrow\, 4\mid 14^n\Rightarrow\,14^n\bmod 60 = 4 (14^n/4 \bmod 15) = 4((-1)^n 4) = \left\{\begin{align} &16\ \ {\rm if}\ \ 2\mid n\\ &44\ \ {\rm if}\ \ 2\nmid n\end{align}\right. $