Skip to main content
OlympiadHQ

Browse · MathNet

Print

1 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 .
Final answer
(3, 5)

Techniques

Greatest common divisors (gcd)Inverses mod n