2016 USAJMO Problems/Problem 2

Revision as of 14:05, 22 April 2016 by Wl0410 (talk | contribs) (Solution)

Problem

Prove that there exists a positive integer $n < 10^6$ such that $5^n$ has six consecutive zeros in its decimal representation.

Solution

Let digit $1$ of a number be the units digit, digit $2$ be the tens digit, and so on. Let the 6 consecutive zeroes be at digits $k-5$ through digit $k$. The criterion is then obviously equivalent to

\[5^n \mod 10^k < 10^{k-6}\]

We will prove that $n = 20+2^{19}, k = 20$ satisfies this, thus proving the problem statement (since $n = 20+2^{19} < 10^6$).

We want

\[5^{20+2^{19}} \mod 10^{20}\]

\[5^{20} \left(5^{2^{19}} \mod 2^{20}\right)\]

\[5^{20} \left(5^{\varphi \left(2^{20}\right)} \mod 2^{20}\right)\]

($\varphi$ is the Euler Totient Function.) By Euler's Theorem, since gcd$\left(5, 2^{20}\right)$ = 1,

\[5^{\varphi \left(2^{20}\right)} \mod 2^{20} = 1\]

so

\[5^{20} \left(5^{\varphi \left(2^{20}\right)} \mod 2^{20}\right) = 5^{20}\]

Since $2^{20} > 10^6, 5^{20} < 10^{14} = 10^{20-6}$, so

\[5^n \mod 10^k < 10^{k-6}\]

for $n = 20+2^{19}$ and $k = 20$, and thus the problem statement has been proven. $\blacksquare$

Motivation for Solution

\modifying our necessary and sufficient inequality, we get:

\[5^n \mod 10^k < 10^{k-6}\]

\[5^k \left(5^{n-k} \mod 2^k\right) < 10^{k-6}\]

\[5^{n-k} \mod 2^k < \frac{2^{k-6}}{5^6}\]

Since gcd$\left(5^{n-k}, 2^k\right) = 1$ if $k \neq 0$ (which is obviously true) and $n \neq k$ which is also true given that $5^k < 10^k$, we need the RHS to be greater than $1$:

\[\frac{2^{k-6}}{5^6} > 1\]

\[2^{k-6} > 5^6\]

\[2^k > 10^6\]

The first $k$ that satisfies this inequality is $k = 20$, so we let $k = 20$:

\[5^{n-20} \mod 2^{20} < \frac{2^{14}}{5^6}\]

\[5^{n-20} \mod 2^{20} \leq 1\]

\[5^{n-20} \mod 2^{20} = 1\]

From this, Euler's Theorem comes to mind and we see that if $n-20 = \varphi\left(2^{20}\right)$, the equality is satisfied. Thus, we get that $n = 20 + 2^{19}$, which is less than $10^6$, and we should be done. However, this requires slightly more formalization, and can be proven directly more easily if $n = 20+2^{19}$ is known or suspected.

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

See also

2016 USAJMO (ProblemsResources)
First Problem Followed by
Problem 2
1 2 3 4 5 6
All USAJMO Problems and Solutions