Math Central - mathcentral.uregina.ca
Problem of the Month
  Recent problems
with 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
*Diana Andrei
Jose Arraiz
Ashutosh Claudio Baiocchi
Bojan Bašić
Quentin Baudenon
Luigi Bernardini
Daniel Bitin
Lou Cairoli
Bernard Collignon
Olivier Cyr
Jean Drabbe
Jean-Denis Eiden
*Mei-Hui Fang
Sehmus Findik
Philippe Fondanaiche
Jan Fricke
Bruce Golfman
Gruian Cornel
Verena Haider
Tom Holens
*Benoît Humbert
Ile Ilijevski
Wolfgang Kais
Omran Kouba
Lethe Li
Matthew Lim
Roopesh Mangal
Nawal Kishor Mishra
Arnaud Piquerez
Kevin Pratt Lee Reis
Mathias Schenker
Shiv Mohan Sharma
Albert Stadler
Hakan Summakoğlu
A. Teitelman
Jan van Delden
(The Netherlands)
Paul Voyer
Allen Druze
 Nicolas Michel
Antonio Ledesma López
Ritwik Chaudhuri
 * 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
n^2 + 3n + 5
& = (11k+4)^2 + 3(11k+4) + 5)\\
&= 121k^2 + 121k + 33 \equiv 33 \not\equiv 0 \pmod{121}.
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


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.



Home Resource Room Home Resource Room Quandaries and Queries Mathematics with a Human Face About Math Central Problem of the Month Math Beyond School Outreach Activities Teacher's Bulletin Board Canadian Mathematical Society University of Regina PIMS