IMO 1978 SL 17

Origin: FRA

Problem

Prove that for any positive integers x, y, z with xy−z2 = 1 one can find nonnegative integers a, b, c, d such that x = a2 + b2, y = c2 + d2, z = ac + bd. Set z = (2q)! to deduce that for any prime number p = 4q + 1, p can be represented as the sum of squares of two integers.

Solution

Let z0 \geq1 be a positive integer. Supposing that the statement is true for all triples (x, y, z) with z < z0, we shall prove that it is true for z = z0 too.

If z0 = 1, verification is trivial, while x0 = y0 is obviously impossible. So let there be given a triple (x0, y0, z0) with z0 > 1 and x0 < y0, and define another triple (x, y, z) by x = z0, y = x0 + y0 −2z0, and z = z0 −x0. Then x, y, z are positive integers. This is clear for x, z, while y = x0 +y0− 2z0 \geq2(\sqrtx0y0 −z0) > 2(z0 −z0) = 0. Moreover, xy −z2 = x0(x0 + y0 − 2z0) −(z0 −x0)2 = x0y0 −z2 0 = 1 and z < z0, so that by the assumption, the statement holds for x, y, z. Thus for some nonnegative integers a, b, c, d we have x = a2 + b2, y = c2 + d2, z = ac + bd. But then we obtain representations of this sort for x0, y0, z0 too: x0 = a2 + b2, y0 = (a + c)2 + (b + d)2, z0 = a(a + c) + b(b + d). For the second part of the problem, we note that for z = (2q)!, z2 = (2q)!(2q)(2q −1) \cdot \cdot \cdot 1 \equiv(2q)! \cdot (−(2q + 1))(−(2q + 2)) \cdot \cdot \cdot (−4q) = (−1)2q(4q)! \equiv−1 (mod p), by Wilson’s theorem. Hence p | z2 + 1 = py for some positive integer y > 0. Now it follows from the first part that there exist integers a, b such that x = p = a2 + b2. Second solution. Another possibility is using arithmetic of Gaussian in- tegers. Lemma. Suppose m, n, p, q are elements of Z or any other unique factor- ization domain, with mn = pq. then there exist elements a, b, c, d such that m = ab, n = cd, p = ac, q = bd. Proof is direct, for example using factorization of a, b, c, d into primes. We now apply this lemma to the Gaussian integers in our case (because Z[i] has the unique factorization property), having in mind that xy = z2 + 1 = (z + i)(z −i). We obtain (1) x = ab, (2) y = cd, (3) z + i = ac, (4) z −i = bd for some a, b, c, d \inZ[i]. Let a = a1+a2i, etc. By (3) and (4), gcd(a1, a2) = \cdot \cdot \cdot = gcd(d1, d2). Then (1) and (2) give us b = a, c = d. The statement follows at once: x = ab = aa = a2 1 + a2 2, y = dd = d2 1 + d2 2 and z + i = (a1d1 + a2d2) + ı(a2d1 −a1d2) ⇒z = a1d1 + a2d2.