Blog

by Davide Lombardo

EGMO 2013, problem 4. Find all positive integers $a$ and $b$ for which there are three consecutive integers at which the polynomial \[P(n)=\frac{n^5+a}{b}\] takes integer values.

The first thing I notice is that $b$ cannot be even, because the numbers $n^5+a$ and $(n+1)^5+a$ have different parity, so they can't both be divisible by an even number.

This being said, what is this problem really about? What we're being asked to study is really a congruence in disguise, because the condition can be rewritten as
\[
\begin{cases}
(n-1)^5+a \equiv 0 \pmod b\\
n^5+a \equiv 0 \pmod b\\
(n+1)^5+a \equiv 0 \pmod b
\end{cases}
\]
Now by the Chinese Remainder Theorem I probably only care about $b$ being the power of a prime, because if I can solve these congruences for two (powers of) primes then I can also solve them modulo the product. So let's say that $b$ is prime for now, I'll worry about powers later. Also I notice that $a$ is a bit of a red herring: if I rewrite the congruences as
\[
\begin{cases}
a \equiv -n^5 \pmod b \\
(n-1)^5-n^5 \equiv 0 \pmod b\\
(n+1)^5-n^5 \equiv 0 \pmod b
\end{cases}
\]
the truth seems to be that whenever I can find an $n$ that satisfies the last two equations, then I just choose $a$ appropriately from the first. So whatever, let's throw out the first equation altogether for now, and just work with
\[
\begin{cases}
(n-1)^5-n^5 \equiv 0 \pmod b\\
(n+1)^5-n^5 \equiv 0 \pmod b
\end{cases}
\]
Now I'm slightly confused: it's clear that (given $b$) the first equation only has finitely many solutions, and so does the second. But how do I combine them? Oh, maybe the idea is something like "well, these equations each have some solution, but the solutions to the first and the solutions to the second are almost always all distinct modulo $b$". Or are they? Maybe there's an infinite class of $b$ for which these really have common solutions... unclear*. While I think about how to proceed, I notice that $b$ cannot divide $n$, nor $n \pm 1$, because otherwise the congruences fail miserably for obvious reasons. I should probably rewrite the congruences again as
\[
(n-1)^5 \equiv n^5 \equiv (n+1)^5 \pmod b
\]
Now that I see them this way, I'm reminded of the fact that taking fifth powers is injective modulo 5 because of Fermat's little theorem, so $b$ cannot be 5. That is, if $b=5$ we have $(n-1)^5 \equiv n-1 \pmod 5$, $n^5 \equiv n \pmod 5$, $(n+1)^5 \equiv n+1 \pmod 5$ and therefore
\[
n-1 \equiv n \equiv n+1 \pmod 5,
\]
contradiction.
Actually I know more: taking 5th powers is injective modulo $b$ (a prime) whenever $5$ does not divide $b-1$. Oh, that sounds like an almost interesting fact: if $b$ is not 1 mod 5, then I also obtain $n-1 \equiv n \equiv n+1$, which can hardly happen. So $b \equiv 1 \pmod 5$, that's something. And now I'm afraid I really have to compute something, don't I? The prime $b$ divides the 2 numbers
\[
(n+1)^5-n^5, (n-1)^5-n^5
\]
so I guess I can try to run a "Euclidean algorithm-style" kind of computation to reduce the powers of $n$ involved. Let's see: $\left( (n+1)^5-n^5, (n-1)^5-n^5 \right)$ is the same as
\[
\left( 1 + 5 n + 10 n^2 + 10 n^3 + 5 n^4, -1 + 5 n - 10 n^2 + 10 n^3 - 5 n^4 \right)
\]
so clearly the very first thing I want to do is sum these expressions to get rid of the $n^4$:
\[
\left( 1 + 5 n + 10 n^2 + 10 n^3 + 5 n^4, 10 n + 20 n^3 \right).
\]
Oh, that's actually nice. I can also throw out a factor of 10 from $10n+20n^3$ (because I know that $b$ is neither 2 nor 5) and a factor of $n$ (because I know that $b$ cannot divide $n$), so I end up with having to compute
\[
\left( 5 n^4 + 10 n^3+10 n^2+5n+1, 2 n^2+1 \right)
\]
The unfortunate detail is that I cannot divide $5 n^4 + 10 n^3+10 n^2+5n+1$ by $2n^2+1$ as polynomials, because the leading terms do not divide each other. But that's not really a problem, let me double the first polynomial (which I can do for free, since $2n^2+1$ is odd anyway) and try again: I want to compute
\[
\left( 2(5 n^4 + 10 n^3+10 n^2+5n+1), 2 n^2+1 \right).
\]
Ugh, long polynomial division. Never could abide those, but fine, let's do it: after some computations on a separate sheet of paper, I find
\[
2(5 n^4 + 10 n^3+10 n^2+5n+1) = (2n^2+1)(5n^2+10n)+15n^2+2
\]
Ok, so (subtracting a multiple of the second polynomial from the first) I now have that if $b$ divides $(n+1)^5-n^5$ and $n^5-(n-1)^5$, then $b$ divides
\[
(15n^2+2,2n^2+1)
\]
and I suppose I should do one more step and compute
\[
\begin{aligned}
(15n^2+2,2n^2+1) & = (30n^2+4,2n^2+1) \\
& = (30n^2+4-15(2n^2+1),2n^2+1)\\
& =(-11,2n^2+1).
\end{aligned}
\]
But this is excellent, 11 is an actual number (as opposed to a polynomial in $n$)! So who cares about the congruences and everything else I said at the beginning: if $b$ divides both $(n+1)^5-n^5$ and $(n-1)^5-n^5$, then $(b,10n)=1$ and computing the GCD shows that $b$ divides $(11,2n^2+1)$. So $b$ is either 1 or 11. I guess when $b=1$ there is not much else to say (I can just take $a$ to be whatever I like), so I only need to deal with $b=11$.
In this case I know that I have to choose $a \equiv -n^5 \pmod{11}$ (we said that at the beginning, right?), and also -- since I'm assuming that $b=11$ divides $(11,2n^2+1)$ -- I know that $2n^2+1 \equiv 0 \pmod{11}$. This is a congruence I can do: if I multiply by 5 it becomes $10n^2+5 \equiv 0 \pmod{11}$, that is $n^2 \equiv 5 \pmod{11}$. Since $4^2 \equiv 16 \equiv 5 \pmod{11}$, the only solutions are $n \equiv \pm 4 \pmod {11}$. And so $a \equiv -n^5 \equiv -(\pm 4)^5 \equiv \mp 2^{10} \equiv \mp 1 \pmod {11}$. Mmmh, I realize I haven't done a single example (in my defense, I wouldn't have found 11 by examples...), so let's check that I haven't gotten anything wrong: I'm claiming that I can take $a \equiv -1 \pmod {11}$ and $n \equiv 4 \pmod{11}$. Is it true that $3^5-1, 4^5-1$ and $5^5 - 1$ are all 0 modulo 11? Well certainly $4^5 \equiv 2^{10} \equiv 1 \pmod{11}$ by Fermat's little theorem, and $5^5 \equiv (4^2)^5 \equiv 4^{10} \equiv 1 \pmod{11}$ for the same reason; also $3^5 \equiv 9 \cdot 9 \cdot 3 \equiv 12 \equiv 1 \pmod{11}$, so yeah, it seems to work out. Let's also do $a \equiv 1 \pmod{11}$ and $n \equiv -4 \pmod{11}$: we need to check that $-5^5 \equiv -1 \pmod{11}$, $-4^5 \equiv -1 \pmod{11}$, $-3^5 \equiv -1 \pmod{11}$, and these are the same congruences as before up to a sign, so they also work out.
Conclusion:
\[
\boxed{b=1, a \in \mathbb{Z}_{>0} \text{ or } b=11, a \equiv \pm 1 \pmod{11}}
\]

Second solution. I also sketch a less elementary (but somewhat more direct, in my opinion) solution to this problem. The idea is that from the congruences
\[
\begin{cases}
(n+1)^5 \equiv n^5 \pmod{b}\\
(n-1)^5 \equiv n^5 \pmod{b}
\end{cases}
\]
we see that $\frac{n+1}{n}$, $\frac{n-1}{n}$ are (primitive and distinct) fifth roots of unity modulo $b$. Call $t:=1/n$; then $1+t$ and $1-t$ are fifth roots of unity, and so are $(1+t)(1-t)=1-t^2$, $(1+t)^2=1+2t+t^2$ and $(1-t)^2=1-2t+t^2$. These are five 5th roots of unity, and all of them are primitive (because none of them is equal to 1!), so 2 of them are equal modulo $b$. We can remove 1 from each of them and divide by $t \neq 0$, and we find that two of the following 5 numbers are equal modulo $b$:
\[
1, -1, -t, 2+t, -2+t
\]
Since $t \not \equiv \pm 1 \pmod b$, it's easy to see that $t \equiv \pm 3 \pmod{b}$. Since $b$ divides both $(1+t)^5-1 \equiv (1+1/n)^5-1$ and $(1-t)^5-1 \equiv (1-1/n)^5 -1$, we find that $b$ divides either $(4^5-1,(-2)^5-1)=(1023,33)=33$ or $((-2)^5-1,4^5-1)=33$. Since $b$ cannot have a factor of 3 (recall the observation in the first solution that the prime factors of $b$ are congruent to 1 modulo 5!), this gives that $b$ divides 11.

* For the really committed readers: there is an advanced tool to answer this sort of question, called the resultant, which shows that we only need to care about $b$ being a power of $2$, $5$ or $11$. But during a competition, and without a computer, I probably wouldn't have been able to compute resultants...