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