Skip to main content
OlympiadHQ

Browse · MathNet

Print

Ireland

Ireland number theory

Problem

Find with proof all solutions in nonnegative integers of the equation
Solution
We consider four cases: , , and .

Case 1: . In this case is odd, so there are no solutions.

Case 2: . We have , so , and, reading mod 4, we see that is odd. Next reading mod 3, we get that is even. Hence , , for some nonnegative integers . Then and . Suppose that . Then we have . Hence is divisible by . Since 5 is the order of 3 mod 11, , for some nonnegative integer , and is divisible by . This contradicts the fact that does not divide . So, in this case , , , is the only solution.

Case 3: . Here , so reading mod 4, we see that is even. If , then we have the solution , , , . Suppose that . Reading mod 3, we see that is even, so is even and is even. Write , . Now we have and this is impossible since the left-hand side is divisible by 8.

Case 4: . Reading mod 4, we see that is even. Reading mod 8, we find that is even and thus, and for some nonnegative integers . Hence . If , then . Since , and , this is impossible. Hence and we have two possibilities: (i) and , and (ii) and , where we again used . In case (i), we obtain, by subtraction, and thus . So and is even, say and then and thus and , since . But has no solutions. In case (ii), we have by subtraction and thus . Then either and or, reading mod 4, is even. For , we have and from we get and . The case gives the solution , , , . The case , does not yield solutions.

Combining all cases, we see that the solutions are , and .
Final answer
[[1, 1, 3, 1], [0, 1, 0, 2], [0, 2, 1, 3]]

Techniques

Techniques: modulo, size analysis, order analysis, inequalitiesMultiplicative orderFactorization techniques