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

## Expert Answers 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

Approved by eNotes Editorial Team

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