# Show that a^6001 is congruent with a (mod 8525), where a and 8525 are coprime. Hint: 8525 = 5^2*11*31

### 1 Answer | Add Yours

Euler's Theorem says that if `a` and `n` are relatively prime, or coprime, then

`a^(phi(n)) -= 1` `mod n`

where `phi(n)` is Euler-s phi function (this gives the number of numbers less than or equal to `n`that are coprime with `n`)

Also, Euler's product formula states that

`phi(n) = n prod_(p_n)(1-1/p)`

where ` `` `the product is over prime factors of `n`.

Since the prime factorisation of 8525 = 5^2 x 11 x 31, then

`phi(8525) = 8525(1-1/5)(1-1/11)(1-1/31) = 6000`

Therefore, using Euler's Theorem

`a^6000 -= 1` `mod 8525`

`a^6000 - 1 -= 0` `mod 8525`

`a(a^6000-1) -= 0` `mod 8525`

`a^6001 -= a` `mod 8525`

**as required**