Browse · MathNet
PrintPreselection 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 .
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)