Difference between revisions of "1991 USAMO Problems/Problem 3"
(→Solution 2) |
(→Solution 2) |
||
(One intermediate revision by the same user not shown) | |||
Line 29: | Line 29: | ||
<cmath>a_m = a_{m + 1} = a_{m + 2} = \cdots \pmod{\varphi(n + 1)}.</cmath> | <cmath>a_m = a_{m + 1} = a_{m + 2} = \cdots \pmod{\varphi(n + 1)}.</cmath> | ||
− | Since <math>n + 1</math> is coprime to | + | Since <math>n + 1</math> is coprime to powers of <math>2</math>, it follows by Euler’s theorem that |
<cmath>2^{a_m} = 2^{a_{m + 1}} = 2^{a_{m + 2}} = \cdots \pmod{n + 1},</cmath> | <cmath>2^{a_m} = 2^{a_{m + 1}} = 2^{a_{m + 2}} = \cdots \pmod{n + 1},</cmath> |
Latest revision as of 18:18, 5 June 2023
Contents
Problem
Show that, for any fixed integer the sequence is eventually constant.
[The tower of exponents is defined by . Also means the remainder which results from dividing by .]
Solution 1
Suppose that the problem statement is false for some integer . Then there is a least , which we call , for which the statement is false.
Since all integers are equivalent mod 1, .
Note that for all integers , the sequence eventually becomes cyclic mod . Let be the period of this cycle. Since there are nonzero residues mod . . Since does not become constant mod , it follows the sequence of exponents of these terms, i.e., the sequence does not become constant mod . Then the problem statement is false for . Since , this is a contradiction. Therefore the problem statement is true.
Note that we may replace 2 with any other positive integer, and both the problem and this solution remain valid.
Solution 2
We’ll prove by strong induction that for every natural number , the sequence is eventually constant. Since every term of the sequence is , the claim is true when . Assuming that it’s true for , we’ll now show that it’s true for as well.
Suppose first that is odd. Since , by our inductive hypothesis there exists an such that
Since is coprime to powers of , it follows by Euler’s theorem that
or equivalently
which is what we wanted to show.
Now suppose that is even. Write , where is odd. The series must eventually be constant , since for large enough . And by our inductive hypothesis, the series must also eventually be constant . So for large enough ,
Since and are coprime, these equations are also true modulo . So
which completes the proof.
See Also
1991 USAMO (Problems • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.