Skip to main content
OlympiadHQ

Browse · MathNet

Print

North Macedonia

North Macedonia number theory

Problem

Let be a natural number. Prove that if and only if .
Solution
Let . Clearly does not divide , so by Little Fermat's theorem we have that , i.e. .

Now we have , i.e. or , and because of we get .

Now let ; clearly does not divide , so as previously we have . We get , i.e. , i.e. , or , from where we have that , which concludes the proof.

Techniques

Fermat / Euler / Wilson theoremsPrime numbers