2024 USAJMO Problems/Problem 3
Contents
[hide]Problem
Let be the sequence defined by and for each integer . Suppose that is prime and is a positive integer. Prove that some term of the sequence is divisible by .
Solution 1
Lemma :
Given a prime , a positive integer , and an even such that , we must have that .
Proof of Lemma :
Then,
Therefore, by induction, if there exists an even integer such that , then for all integers , , so we are done if there exists an even such that .
Now, consider the case where there is some prime such that there are no even integers such that .
Lemma :
In this case, we must have that if for all integers .
Proof of Lemma :
Suppose for the sake of contradiction that there exists some such that and does not divide . Then, we have , by Fermat's Little Theorem. Since for all , is even, then would be even. However this results in a contradiction.
Then, we get that if , then .
Then, by LTE, . Since , then for all positive integers , so then by Chinese Remainder Theorem there exists integers such that and , so we are done
Remark: I think this is a very cool NT problem.
-bronzetruck2016
See Also
2024 USAJMO (Problems • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAJMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.