|
Solution for October 2011
| The Problem: |
 |
Find the smallest positive integer $n$ for which $n^2 + 3n + 5$ is divisible by 121, or prove that no such integer exists.
|
The solution:
No such integer exists --- unless, of course, you happen to be working in base 8. Benoît Humbert noted that in base 8 the answer is $n = 16_8 : 16_8^2 +3\cdot 16_8 +5 = 363_8 = 3\cdot 121_8$.
Correct solutions were submitted by
Bahman Ahmadi
(Regina) |
*Diana Andrei
(Sweden) |
Jose Arraiz
(Brazil) |
| Ashutosh |
Claudio Baiocchi
(Italy) |
Bojan Bašić
(Serbia) |
Quentin Baudenon
(France) |
Luigi Bernardini
(Italy) |
Daniel Bitin
(Romania) |
Lou Cairoli
(USA) |
Bernard Collignon
(France) |
Olivier Cyr
(France) |
Jean Drabbe
(Belgium) |
Jean-Denis Eiden
(France) |
*Mei-Hui Fang
(Austria) |
Sehmus Findik
(Turkey) |
Philippe Fondanaiche
(France) |
Jan Fricke
(Germany) |
Bruce Golfman
(Austria) |
Gruian Cornel
(Romania) |
Verena Haider
(Austria) |
Tom Holens
(Manitoba) |
*Benoît Humbert
(France) |
Ile Ilijevski
(Macedonia) |
Wolfgang Kais
(Germany) |
Omran Kouba
(Syria) |
Lethe Li
(USA) |
Matthew Lim
(USA) |
Roopesh Mangal
(Malaysia) |
Nawal Kishor Mishra
(India) |
Arnaud Piquerez
(France) |
Kevin Pratt |
Lee Reis |
Mathias Schenker
(Switzerland) |
Shiv Mohan Sharma
(India) |
Albert Stadler
(Switzerland) |
Hakan Summakoğlu
(Turkey) |
A. Teitelman
(Israel) |
Jan van Delden
(The Netherlands) |
Paul Voyer
(France) |
Allen Druze
(USA) |
Nicolas Michel
(France) |
Antonio Ledesma López
(Spain) |
Ritwik Chaudhuri
(India) |
|
* Submitted multiple solutions
We will provide a sample of the many nice proofs that we received. Cairoli found the problem (with two solutions) in Arthur Engel, Problem-Solving Strategies (Springer 1999), pages 131 and 138.
Method 1. Observe that
$$n^2 + 3n + 5 = (n+7)(n-4) + 33.$$
Because the difference $(n+7) - (n-4) = 11$, we deduce that either both $n+7$ and $n-4$ are divisible by 11, or neither is. But 11 divides 33, so if 11 also divides $n^2 + 3n + 5$, then it would divide the product $(n+7)(n-4)$, whence (because 11 is prime) 11 divides them both. This implies that if 121 were to divide $n^2 + 3n + 5$, then it would also divide 33, which is a contradiction. We conclude that 121 does not divide $n^2 + 3n + 5$.
Comment. Golfman observed that our argument remains valid when 11 is replaced by any prime $p$: If an integer $a$ is not divisible by $p$, then $p^2$ will never divide $m(m-p) + ap$. (In our problem $p=11, m=n+7$ and $a=3$.)
Method 2. By definition, 121 divides $n^2 + 3n + 5$ if and only if there exists an integer $k$ such that
$$n^2 + 3n + 5 = 121k.$$
For the quadratic $n^2 + 3n + 5-121k = 0$ to have an integer solution, its discriminant, namely $3^2-4(5-121k) = 484k - 11 = 11(44k-1)$, would have to be a perfect square. But since 11 is prime, $11(44k-1)$ could be a perfect square only if 11 were to divide $44k-1$, which it cannot. That contradiction proves that $n^2 + 3n + 5$ is not divisible by 11.
Method 3. Observe that $n^2 + 3n + 5 \; \equiv\; n^2 + (3-11)n + (5+11) = (n-4)^2 \pmod {11}$. Thus, if $n \not\equiv 4$ (mod 11), then $n^2 + 3n + 5 \not\equiv 0$ (mod 11), whence 121 does not divide $n^2 + 3n + 5$. (Alternatively because 11 is a small number, one can evaluate $n^2 + 3n + 5$ for $n$ running from 0 to 10 and observe that the sum is divisible by 11 exactly when $n = 4$.) On the other hand, if $ n\equiv 4 \pmod{11}$, then $n=11k + 4$ for some integer $k$ and
$$\begin{align*}
n^2 + 3n + 5
&
= (11k+4)^2 + 3(11k+4) + 5)\\
&= 121k^2 + 121k + 33 \equiv 33 \not\equiv 0 \pmod{121}.
\end{align*}$$
We conclude that there is no integer $n$ for which 121 divides $n^2 + 3n + 5$.
Comment. Haider reminded us that Hensel's lemma, also known as the lifting theorem for polynomial congruences, provides information about the divisibility of a polynomial by $p^{e+1}$ if one knows something about its divisibility by $p^e$. Although one would not bother with such a powerful tool in a simple problem such as ours — in fact, just to state the result requires more words than we've used in any of the above solutions — it is a very useful theorem to know. A careful statement with a proof can be found, for example, at
http://www.cs.xu.edu/math/math302/04f/PolyCongruences.pdf
We require just one of its three cases:
If $x \equiv a$ (mod $p^e$) is a solution to the polynomial congruence $f(x) \equiv 0$ (mod $p^e$) and $p$ divides $f'(a)$ (its formal derivative evaluated at $x = a$), but $p^{e+1}$ does not divide $f(a)$, then $f(x) \equiv 0$ (mod $p^{e+1}$) has no solutions that reduce to $a$ (mod $p^e$). To apply the lemma here we observe (as in the first step of Method 3) that $x = 4$ is the unique solution to $f(x) = x^2+3x+5 \equiv 0$ (mod 11), and
$$f'(4) = 2x+3|_{x=4} = 11 \equiv 0 \pmod{11},$$
but $11^2=121$ does not divide $f(4) = 33$; therefore by Hensel's lemma, there can be no solutions for $f(x) \equiv 0$ (mod 121).
Method 4. If $n$ is an integer for which $n^2 + 3n + 5$ is divisible by 121, then for $n=m+4$,
$$n^2 + 3n + 5 =
(m+4)^2 + 3(m+4) + 5 = m^2 + 11m + 33$$
is divisible by $121=11^2$, whence it is divisible by 11. But then, so is $m$, which implies that the first two summands on the right are divisible by $11^2$; however, this leads to a contradiction because the last term (namely 33) is not divisible by 121, so the given quadratic cannot be divisible by 121 after all.
|
