You are viewing a single comment's thread. Return to all comments →
Hints:
(1) Euler's theorem: if a and n are coprime positive integers, we have
a^phi(n) mod n = 1,
where phi() is Euler's totient function. Fermat's little theorem is a special case of this where n is prime.
(2) What if a and n are not coprime? Try this:
a mod n = (a/d mod n/d)*d,
where d=gcd(a,n) is the greatest common divisor of a and n.
These are the main ingredients of this problem. Watch out for boundary cases.
Seems like cookies are disabled on this browser, please enable them to open this website
Devu Vs Police
You are viewing a single comment's thread. Return to all comments →
Hints:
(1) Euler's theorem: if a and n are coprime positive integers, we have
where phi() is Euler's totient function. Fermat's little theorem is a special case of this where n is prime.
(2) What if a and n are not coprime? Try this:
where d=gcd(a,n) is the greatest common divisor of a and n.
These are the main ingredients of this problem. Watch out for boundary cases.