m and n are positive integers with m > n and m + n even. Prove that the roots of x2 - (m2 - m + 1)(x - n2 - 1) - (n2 + 1)2 = 0 are positive integers, but not squares.
Solution
Put M = m2 - m + 1, N = n2 + 1. Then the equation is x2 - Mx + MN - N2 = (x - N)(x - M + N). So the roots are N and M - N. N is obviously a positive integer and since N2 < N2 + 1 < (N + 1)2 it cannot be a square.
M - N is obviously an integer. We have m > n, so m ≥ n+1, so M > (m-1)2 +1 ≥ n2 + 1 = N. So M - N is positive. It remains to show that M - N = m2 - m - n2 cannot be a square.
We claim that if m(m-1) = n2 + k2, then m and n have opposite parity. Since we are given that m + n is even, that is sufficient to prove that M - N cannot be a square.
Note first that a square = 0 or 1 mod 4. We consider four cases. If m = 1 mod 4, then m(m-1) = 0 mod 4, so n and k must both be even (if they were odd, the sum of their squares would be 2 mod 4), so m and n have opposite parity. If m = 2 mod 4, then n and k must both be odd, so again m and n have opposite parity.
If m = 3 mod 4, then there must be some prime p which is 3 mod 4 and divides m to an odd power. Since m and m-1 are relatively prime, it must also divide m(m-1) to an odd power. Similarly, if m = 0 mod 4, then m-1 = 3 mod 4 and so again we can find a prime p = 3 mod 4 which divides m(m-1) to an odd power. So we have n2 + k2 = 0 mod p. Hence n2 = - k2 mod p. Taking both sides the power (p-1)/2, which is odd, we get np-1 = - kp-1 mod p. But it is well-known that if p does not divide h then hp-1 = 1 mod p (this is Fermat's little theorem - see below for a proof). So p must divide both n and k. Thus p2 must divide m(m-1). We now divide through m(m-1) = n2 + k2 by p2 and repeat the argument. By a simple induction we find that p must divide m(m-1) to an even power. Contradiction. So there are no solutions with m = 3 or 0 mod 4.
Comment. This seems too advanced for an olympiad problem, so maybe there is an easier solution. To prove Fermat's theorem note that if p does not divide h, then h, 2h, 3h, ... , ph must be a complete set of residues mod p (in other words they all have different remainders on division by p). Obviously ph = 0 mod p, so the others must be a permutation of 1, 2, ... , p-1. Hence h.2h.3h. ... (p-1)h = 1.2. ... . (p-1) mod p. We can divide through by (p-1)! to conclude that hp-1 = 1 mod p.
© John Scholes
jscholes@kalva.demon.co.uk
9 July 2002