1974 IMO Problems/Problem 3

Problem

Prove that the number $\sum^n_{k=0}\binom{2n+1}{2k+1}2^{3k}$ is not divisible by $5$ for any integer $n\ge0.$

Solution

Everything that follows takes place in $\mathbb F_5(\sqrt 2)$, i.e. the field we get by adjoining a root of $x^2-2=0$ to $\mathbb F_5$, the field with $5$ elements.

We have $\sum_{k=0}^n\binom{2n+1}{2k+1}2^{3k}=\sum_{k=0}^n\binom{2n+1}{2n-2k}3^k=\sum_{k=0}^n\binom{2n+1}{2(n-k)}2^{-k}$. Now, this is zero iff it's zero when we multiply it by $2^n$, so we may as well prove that $\sum_{k=0}^n\binom{2n+1}{2(n-k)}\sqrt 2^{2(n-k)}\ne 0$. The LHS is $\alpha$ from $(1+\sqrt 2)^{2n+1}=\alpha+\beta\sqrt 2,\ \alpha,\beta\in\mathbb F_5$. We have $(1-\sqrt 2)^{2n+1}=\alpha-\beta\sqrt 2$, so by multiplying them we get $-1=\alpha^2-2\beta^2$. If we were to have $\alpha=0$, then we would get $1=2\beta^2,\ \beta\in\mathbb F_5$, and this is impossible, since it would make $3=2^{-1}$ a square $\beta^2$ in $\mathbb F_5$ (i.e. $3$ would be a quadratic residue modulo $5$, and it's not).

The above solution was posted and copyrighted by grobber. The original thread for this problem can be found here: [1]


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See Also

1974 IMO (Problems) • Resources
Preceded by
Problem 2
1 2 3 4 5 6 Followed by
Problem 4
All IMO Problems and Solutions