Skip to main content
OlympiadHQ

Browse · MathNet

Print

Preselection tests for the full-time training

Saudi Arabia number theory

Problem

Prove that if is an integer relatively prime with then
Solution
If is relatively prime with then it is relatively prime with both , . Since is relatively prime with then, by Fermat, which implies Since is relatively prime with then . Hence But , are relatively prime and therefore

Techniques

Fermat / Euler / Wilson theoremsChinese remainder theorem