Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1974 IMO Problems/Problem 3"
 
Line 8: Line 8:
  
 
The above solution was posted and copyrighted by grobber. The original thread for this problem can be found here: [https://aops.com/community/p359102]
 
The above solution was posted and copyrighted by grobber. The original thread for this problem can be found here: [https://aops.com/community/p359102]
 +
 +
  
 
{{alternate solutions}}
 
{{alternate solutions}}

Latest revision as of 14:58, 29 January 2021

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1974_IMO_Problems/Problem_3&oldid=143900"