Browse · MathNet
PrintAustrian Mathematical Olympiad
Austria number theory
Problem
Let be a positive integer. Prove that is divisible by if and only if is divisible by .
Solution
If is a multiple of , both sides of the equivalence are wrong, so the equivalence is true.
If is not a multiple of , Fermat's little theorem implies that is a multiple of . The equivalence now follows from
If is not a multiple of , Fermat's little theorem implies that is a multiple of . The equivalence now follows from
Techniques
Fermat / Euler / Wilson theoremsInverses mod n