2016 USAJMO Problems/Problem 2

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 \bmod 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}}\pmod{10^{20}}$

We can split this into its prime factors. Obviously, it is a multiple of $5^{20}$ , so we only need to consider it $\mod2^{20}$ .

$5^{20}\cdot5^{2^{19}}\pmod{2^{20}}$

$5^{20}\cdot5^{\varphi(2^{20})}\pmod{2^{20}}$

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

$5^{\varphi(2^{20})}\equiv1\pmod{2^{20}}$

so

$5^{20}\cdot5^{\varphi (2^{20})}\equiv5^{20}\pmod{2^{20}}$

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

$5^n \bmod 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.

2016 USAJMO (Problems • Resources)
Preceded by Problem 1	Followed by Problem 3
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions

Page

Toolbox

Search

2016 USAJMO Problems/Problem 2

Contents

Problem

Solution

Motivation for Solution

See also