Homework Help

Show that a^6001 is congruent with a (mod 8525), where a and 8525 are coprime.   Hint:...

user profile pic

svjr | Student, Undergraduate | (Level 2) Honors

Posted October 18, 2011 at 3:17 AM via web

dislike 1 like

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

user profile pic

mathsworkmusic | (Level 1) Educator

Posted April 28, 2013 at 9:12 PM (Answer #1)

dislike 1 like

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

Join to answer this question

Join a community of thousands of dedicated teachers and students.

Join eNotes