Modulus Problem

Question

What is the remainder when 25²⁰¹⁵ is divided by 18?

Answer 1

 

For forms

 

   a^k mod n

 

if  gcd(a,n) = 1 then Euler's Theorem can be applied.

 

 

Euler's Theorem:   if gcd(a,n) = 1, then a^k mod n ≡ a^{k mod Φ(n)} (mod n)

 

    where Φ(n) is Euler's Totient function.

 

For 25²⁰¹⁵ mod 18,   we have

  a = 25      

  k = 2015   

  n = 18       (18 = 2•3², to be used below)

 

[ NOTE: gcd(a,n) = gcd(25,18) = 1   so we can use Euler's Theorem ]

 

For n = p₁^k1p₂^k2 … p_r^kr   (n is the product of primes raised to some power,

                                      this is the FTO Arithmetic)

 

Φ(n) = n(1-1/p₁)(1-1/p₂) … (1-1/p_r)

 

 

Φ(n) = Φ(18) = 18*(1-1/2)(1-1/3) = 6

 

So  25²⁰¹⁵ mod 18  =  25^{(2015 mod 6)} mod 18

 

                             =  25⁵ mod 18               (2015 ≡ 5  (mod 6))

                             =  9765625 mod 18

                             =  13