Solution to May 2004 Problem The positive integers d and n are chosen so that (a) d divides evenly into n, and (b) nd + 1 divides evenly into n2 + d2. What are the possible values of d and n? We thank Andy Liu of the University of Alberta for this month's problem. 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 = d3. All solutions began by using condition (a) in the form, n = kd for some integer k > 1. The goal is to show that k = d2 (which, of course, implies our answer, n = d3). 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 kd2 + 1 divides evenly into d2k2 + d2 =d2(k2 + 1). Since d2 and kd2 + 1 are relatively prime, we deduce that
Since all numbers involved are positive, the denominator cannot exceed the numerator: k2 + 1 ≥ kd2 + 1, so that
If we subtract kd2 + 1 from k2 + 1 we have (from (1)) that kd2 + 1 divides the difference (k2 + 1) - (kd2 + 1) = k(k - d2) ≥ 0. But k and kd2 + 1 are relatively prime, so we conclude that
But the denominator is bigger than the numerator (kd2 + 1 > k > k - d2 ? 0), from which we conclude that the numerator must be zero: k - d2 = 0, as desired. (Mir's
argument for the final step was a bit different - since k ≥ d2 is equivalent
to k = d2 + 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 kd2 + 1,
k(k - d2) = (k2 + 1) - (kd2 + 1) 0 (mod kd2 + 1), so that (since k and kd2 + 1 are relatively prime)
Thus, working modulo kd2 + 1, k d2. Multiplying both sides by k, we get k2 kd2 -1, while squaring both sides gives us d4 k2 kd2 -1. It follows that kd2 + 1 divides both k2 + 1 and d4 + 1. Hence, kd2 + 1 ≤ k2 + 1 and kd2 + 1 ≤ d4 + 1. The first inequality tells us that d2 ≤ k, while the second says k ≤ d2. We conclude, finally, that k = d2 as desired. Solution 3 by LaLiberté. To satisfy condition (b) there exists an integer c ≥ 1 for which n2 + d2 = c(nd + 1). Plugging n = kd (from condition (a)) into that equation we get k2 d2 + d2 = ckd2 + c, or
Since all integers in (3) are positive, k2 + 1 - ck ≥ 1, which implies
But also, (3) tells us that k2 + 1 - ck ≥ c, so that k2 + 1 ≥ c(k+1), or
and therefore, c > k - 1 hence c ≥ k. This, together with (4), gives us c = k. Setting c = k in (3), we get d2(k2 + 1 - k2) = k, and we once again conclude that k = d2. Solution 4 by Hecquet. Keeping Laliberté's notation, d2(k2 + 1 - ck) = c where c and k are positive integers and, k2 + 1 - ck ≥ 1. We need to show that k2 + 1 - ck = 1, that is c = k. Put z = k - c. Then the equation d2(k2 + 1 - ck) = c becomes d2(kz + 1) = c, thus z = k - c = k - d2(kz + 1) = k - d2kz - d2; therefore Note that the integer z is nonnegative since c = d2(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(kd2 + 1) = d2 (k2 + 1) = k(kd2 + 1) + d2 - k can be written (c - k)(kd2 + 1) = d2 - k, that is
Note that because kd2 + 1 (in the denominator) exceeds
both d2 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 d2 = k.
|