Math Central - mathcentral.uregina.ca
Problem of the Month
 Currentproblem Recent problemswith solutions
 Older problems from 2000 a 2005 2005/2006 06/07 07/08 08/09 09/10 10/11 11/12

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.

 Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.
 about math central :: site map :: links :: notre site français