Better Students Ask More Questions.
Show that a^6001 is congruent with a (mod 8525), where a and 8525 are coprime. Hint:...
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`
Posted by mathsworkmusic on April 28, 2013 at 9:12 PM (Answer #1)
Join to answer this question
Join a community of thousands of dedicated teachers and students.