-1

I want to calculate

14^(2017^2017) mod 60

I know that 14 and 60 is not GCD=1, so I can not solve this with phi-function directly.

I also tried to split 60 into prim-factors (2^2, 3, 5). Here I know that it is possible to solve

14^(2017^2017) mod 3
14^(2017^2017) mod 5

with the phi function, but

 14^(2017^2017) mod 2^2

is still not possible because GCD(14,4) = 2

MBD
  • 67
  • Is this a question from an on-going contest? – JRN May 01 '17 at 07:23
  • no. why do you think so? because of the current year or the fact that 2017 is prim? Just creative teachers. not more - not less. – MBD May 01 '17 at 16:20

1 Answers1

1

As $14=2\cdot7$

$14^{2017^{2017}}=7^{2017^{2017}}2^{2017^{2017}}$

Now as $2017^{2017}>2,2^{2017^{2017}}\equiv0\pmod{2^2}$

$\implies14^{2017^{2017}}\equiv0\pmod4\ \ \ \ (1)$

Also we can avoid Euler Totient function for $\pmod3,\pmod5$

as $14\equiv-1\pmod{15}$ and as $2^{2017^{2017}}$ is odd

$$14^{2017^{2017}}\equiv(-1)^{2017^{2017}}\equiv-1\pmod{15}\ \ \ \ (2)$$

Now we can apply Chinese Remainder Theorem

or by trial and error we have $$14^{2017^{2017}}\equiv3\cdot15-1\pmod{4\cdot15}$$

lab bhattacharjee
  • 274,582