Skip to main content
OlympiadHQ

Browse · MathNet

Print

Japan 2007

Japan 2007 number theory

Problem

How many pairs of integers satisfy ?
Solution
If or is , both must be .

Consider the case . Let be the G.C.D. of and , and , . Substituting them into the given equation we get Since divides and and are relatively prime, . Therefore divides . Let (). Substituting them into the last equation we get Let be the G.C.D of and , and , . Substituting them into the last equation we get Since and are relatively prime, must divide . Therefore .

Since is an integer, must divide . By , must be positive. Checking all the possible cases one by one, we get .

From , we get all the possible cases, including , as . So the answer is .
Final answer
8

Techniques

Techniques: modulo, size analysis, order analysis, inequalitiesGreatest common divisors (gcd)