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.

Remarks (added by pf02, October 2025)

1. On the discussion page https://artofproblemsolving.com/community/c6h58616 there are several variations of this solution, as well as solutions which can be called different from this one. It is worth looking at them.

2. As of today, the AI engines Gemini (from Google) and ChatGPT give correct solutions to this problem. The two solutions are essentially the same, and they are the same as one of the solutions from the discussion page. The prompt I gave to the AI engines was `prove that sum from k=0 to k=n of ("2n+1 choose 2k+1" * 2^(3k)) is not divisible by 5 for any n \ge 0'.

The original thread for this problem can be found here: [1]

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

Page

Toolbox

Search

1974 IMO Problems/Problem 3

Contents

Problem

Solution

Remarks (added by pf02, October 2025)

See Also