Skip to main content
OlympiadHQ

Browse · MathNet

Print

Austrian 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

Techniques

Fermat / Euler / Wilson theoremsInverses mod n