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**

## We’ll help your grades soar

Start your 48-hour free trial and unlock all the summaries, Q&A, and analyses you need to get better grades now.

- 30,000+ book summaries
- 20% study tools discount
- Ad-free content
- PDF downloads
- 300,000+ answers
- 5-star customer support

Already a member? Log in here.

Are you a teacher? Sign up now