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 ).
We can split this into its prime factors. Obviously, it is a multiple of , so we only need to consider it .
( is the Euler Totient Function.) By Euler's Theorem, since ,
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|