Browse · MathNet
Print1 Autumn tournament
Bulgaria number theory
Problem
Find all pairs of co-prime naturals such that and divides for every natural number .
Solution
Since and are co-prime, so are and , respectively, what is requested is equivalent to dividing for each .
From and we get that necessarily divides and . Hence divides and since , then necessarily divides .
Clearly , i.e. . If , then gives , but is not divisible by . If , then , but is not divisible by .
It remains , respectively . Indeed, is divisible by .
From and we get that necessarily divides and . Hence divides and since , then necessarily divides .
Clearly , i.e. . If , then gives , but is not divisible by . If , then , but is not divisible by .
It remains , respectively . Indeed, is divisible by .
Final answer
(3, 5)
Techniques
Greatest common divisors (gcd)Inverses mod n