Skip to main content
OlympiadHQ

Browse · MathNet

Print

Preselection tests for the full-time training

Saudi Arabia number theory

Problem

Let be two non-negative integers. Prove that divides if and only if divides .
Solution
Because and are relatively prime numbers, divides if and only if divides . But Therefore divides if and only if .

On the other hand, we have . We deduce that the prime number is the order of modulo . This implies that mod if and only if divides .

Techniques

Fermat / Euler / Wilson theoremsMultiplicative orderGreatest common divisors (gcd)