2016 USAJMO Problems/Problem 2
Prove that there exists a positive integer such that has six consecutive zeros in its decimal representation.
Let digit of a number be the units digit, digit be the tens digit, and so on. Let the 6 consecutive zeroes be at digits through digit . The criterion is then obviously equivalent to
We will prove that satisfies this, thus proving the problem statement (since ).
( is the Euler Totient Function.) By Euler's Theorem, since gcd = 1,
Since , so
for and , and thus the problem statement has been proven.
Motivation for Solution
Modifying our necessary and sufficient inequality, we get:
Since gcd if (which is obviously true) and which is also true given that , we need the RHS to be greater than :
The first that satisfies this inequality is , so we let :
From this, Euler's Theorem comes to mind and we see that if , the equality is satisfied. Thus, we get that , which is less than , and we should be done. However, this requires slightly more formalization, and can be proven directly more easily if is known or suspected.
|2016 USAJMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAJMO Problems and Solutions|