May 2004 solution

Solution to MP42

We received solutions from Saïd Amghibech (Québec), Pierre Bornsztein (France), Gilles Feyrit (France), Xavier Hecquet (France), Wolfgang Kais (Germany), Normand Laliberté (Ontario), Patrick J. LoPresti (USA) and Juan Mir Pieras (Spain).

Answer: d can be any positive integer, and n = d³.

All solutions began by using condition (a) in the form, n = kd for some integer k > 1. The goal is to show that k = d² (which, of course, implies our answer, n = d³). We present four ways to establish this result.

Solution 1 by Amghibech, Kais, and Mir.

Setting n = kd in both numbers appearing in condition (b), we have kd² + 1 divides evenly into d²k² + d² =d²(k² + 1). Since d² and kd² + 1 are relatively prime, we deduce that

kd² + 1 divides evenly into k² + 1. (1)

Since all numbers involved are positive, the denominator cannot exceed the numerator: k² + 1 ≥ kd² + 1, so that

k ≥ d². (2)

If we subtract kd² + 1 from k² + 1 we have (from (1)) that kd² + 1 divides the difference (k² + 1) - (kd² + 1) = k(k - d²) ≥ 0. But k and kd² + 1 are relatively prime, so we conclude that

kd² + 1 divides evenly into k - d².

But the denominator is bigger than the numerator (kd² + 1 > k > k - d² ? 0), from which we conclude that the numerator must be zero: k - d² = 0, as desired.

(Mir's argument for the final step was a bit different - since k ≥ d2 is equivalent to k = d² + m with m ≥ 0, Mir proof that m = 0 leads to the same conclusion.)

Solution 2 by Bornsztein.

The solution here is quite similar to solution 1, but the different notation leads the argument in a somewhat different direction.

Since d is relatively prime to kd² + 1,

d²(k² + 1) 0 (mod kd² + 1) implies that k² + 1 0 (mod kd² + 1).

k(k - d²) = (k² + 1) - (kd² + 1) 0 (mod kd² + 1), so that (since k and kd² + 1 are relatively prime)

k - d² 0 (mod kd² + 1).

Thus, working modulo kd² + 1, k d². Multiplying both sides by k, we get k² kd² -1, while squaring both sides gives us d⁴ k² kd² -1. It follows that kd² + 1 divides both k² + 1 and d⁴ + 1. Hence, kd² + 1 ≤ k² + 1 and kd² + 1 ≤ d⁴ + 1. The first inequality tells us that d² ≤ k, while the second says k ≤ d². We conclude, finally, that k = d² as desired.

Solution 3 by LaLiberté.

To satisfy condition (b) there exists an integer c ≥ 1 for which n² + d² = c(nd + 1). Plugging n = kd (from condition (a)) into that equation we get k² d² + d² = ckd² + c, or

d²(k² + 1 - ck) = c. (3)

Since all integers in (3) are positive, k² + 1 - ck ≥ 1, which implies

k ≥ c. (4)

But also, (3) tells us that k² + 1 - ck ≥ c, so that k² + 1 ≥ c(k+1), or

(k² - 1 + 2)/(k+1) = (k² - 1)/(k+1) + 2/(k+1) = k-1 + 2/(k+1) ≥ c,

and therefore, c > k - 1 hence c ≥ k. This, together with (4), gives us c = k. Setting c = k in (3), we get d²(k² + 1 - k²) = k, and we once again conclude that k = d².

Solution 4 by Hecquet.

Keeping Laliberté's notation, d²(k² + 1 - ck) = c where c and k are positive integers and, k² + 1 - ck ≥ 1. We need to show that k² + 1 - ck = 1, that is c = k. Put z = k - c. Then the equation d²(k² + 1 - ck) = c becomes d²(kz + 1) = c, thus z = k - c = k - d²(kz + 1) = k - d²kz - d²; therefore

z + d² = k(1 - d²z). (5)

Note that the integer z is nonnegative since c = d²(kz + 1) is strictly positive. If z is positive, then the right-hand side of (5) is negative while the left-hand side is positive, which is impossible. Therefore z = 0, whence k = c.

Solution 5 by Feyrit, LoPresti and the students who wrote last year's Alberta exams.

The condition c(kd² + 1) = d² (k² + 1) = k(kd² + 1) + d² - k can be written (c - k)(kd² + 1) = d² - k, that is

c - k = (d² - k)/(kd² + 1) = d²/(kd² + 1) - k/(kd² + 1).

Note that because kd² + 1 (in the denominator) exceeds both d² and k in the numerator of the fraction on the right, that fraction must lie strictly between -1 and 1. But the term c - k on the left is an integer, and the only integer between -1 and 1 is 0. We conclude that the fraction on the right is zero, so that d² = k.