Finally, we shall solve two more problems – the last problem is rather surprising since at first glance, it doesn’t appear to involve congruences.
Problem 4 : Prove that if n is a perfect square, then .
Solution : this is rather simple: one could always write n = m2 and consider all possibilities of m modulo 4. But it’s easier to just consider m mod 2:
- If m = 2k is even, then m2 = 4k2 is a multiple of 4.
- If m = 2k+1 is odd, then m2 = 4k2 + 4k + 1 is congruent to 1 mod 4. ♦
The next problem illustrates a common technique, called infinite descent.
Problem 5 : Prove that the only solution of in integers is x = y = z = 0.
Solution : first it is clear that if x = 0 or y = 0, then we must have x = y = z = 0. Hence we assume that x, y and z are all non-zero. Taken modulo 5, we have
Hence, the only possibility for to be a multiple of 5 is . Thus x and y are both multiple of 5: write x = 5x’ and y = 5y’ which gives , i. e. . But this in turn means z is a multiple of 5: z = 5z’, so we are back to the original equation:
Since x, y and z are non-zero, so are x’, y’ and z’. But here the trouble begins: we can apply the same logic above and come to the conclusion that x’, y’ and z’ are also all multiples of 5, and so on, and so on. Thus, x, y and z are divisible by arbitrarily high powers of 5(!) which is clearly impossible if they are non-zero. ♦