Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2016 USAJMO Problems/Problem 2"

(→‎Motivation for Solution)
(→‎Solution: ; formatting improvements)
 
(6 intermediate revisions by one other user not shown)
Line 6: Line 6:
 
Let digit <math>1</math> of a number be the units digit, digit <math>2</math> be the tens digit, and so on. Let the 6 consecutive zeroes be at digits <math>k-5</math> through digit <math>k</math>. The criterion is then obviously equivalent to  
 
Let digit <math>1</math> of a number be the units digit, digit <math>2</math> be the tens digit, and so on. Let the 6 consecutive zeroes be at digits <math>k-5</math> through digit <math>k</math>. The criterion is then obviously equivalent to  
  
−
<cmath>5^n \mod 10^k < 10^{k-6}</cmath>
+
<cmath>5^n \bmod 10^k < 10^{k-6}</cmath>
  
 
We will prove that <math>n = 20+2^{19}, k = 20</math> satisfies this, thus proving the problem statement (since <math>n = 20+2^{19} < 10^6</math>).  
 
We will prove that <math>n = 20+2^{19}, k = 20</math> satisfies this, thus proving the problem statement (since <math>n = 20+2^{19} < 10^6</math>).  
Line 12: Line 12:
 
We want  
 
We want  
  
−
<cmath>5^{20+2^{19}} \mod 10^{20}</cmath>
+
<cmath>5^{20+2^{19}}\pmod{10^{20}}</cmath>
 +
 
 +
We can split this into its prime factors. Obviously, it is a multiple of <math>5^{20}</math>, so we only need to consider it <math>\mod2^{20}</math>.
  
−
<cmath>5^{20} \left(5^{2^{19}} \mod 2^{20}\right)</cmath>
+
<cmath>5^{20}\cdot5^{2^{19}}\pmod{2^{20}}</cmath>
  
−
<cmath>5^{20} \left(5^{\varphi \left(2^{20}\right)} \mod 2^{20}\right)</cmath>
+
<cmath>5^{20}\cdot5^{\varphi(2^{20})}\pmod{2^{20}}</cmath>
  
−
(<math>\varphi</math> is the Euler Totient Function.) By Euler's Theorem, since gcd<math>\left(5, 2^{20}\right)</math> = 1,  
+
(<math>\varphi</math> is the Euler Totient Function.) By Euler's Theorem, since <math>\bigl(5, 2^{20}\bigr)=1</math>,  
  
−
<cmath>5^{\varphi \left(2^{20}\right)} \mod 2^{20} = 1</cmath>
+
<cmath>5^{\varphi(2^{20})}\equiv1\pmod{2^{20}}</cmath>
  
 
so
 
so
  
−
<cmath>5^{20} \left(5^{\varphi \left(2^{20}\right)} \mod 2^{20}\right) = 5^{20}</cmath>
+
<cmath>5^{20}\cdot5^{\varphi (2^{20})}\equiv5^{20}\pmod{2^{20}}</cmath>
  
−
Since <math>2^{20} > 10^6, 5^{20} < 10^{14} = 10^{20-6}</math>, so
+
Since <math>2^{20} > 10^6, 5^{20} < 10^{14} = 10^{20-6}</math>,
  
−
<cmath>5^n \mod 10^k < 10^{k-6}</cmath>
+
<cmath>5^n \bmod 10^k < 10^{k-6}</cmath>
  
 
for <math>n = 20+2^{19}</math> and <math>k = 20</math>, and thus the problem statement has been proven. <math>\blacksquare</math>
 
for <math>n = 20+2^{19}</math> and <math>k = 20</math>, and thus the problem statement has been proven. <math>\blacksquare</math>
Line 60: Line 62:
 
From this, Euler's Theorem comes to mind and we see that if <math>n-20 = \varphi\left(2^{20}\right)</math>, the equality is satisfied. Thus, we get that <math>n = 20 + 2^{19}</math>, which is less than <math>10^6</math>, and we should be done. However, this requires slightly more formalization, and can be proven directly more easily if <math>n = 20+2^{19}</math> is known or suspected.  
 
From this, Euler's Theorem comes to mind and we see that if <math>n-20 = \varphi\left(2^{20}\right)</math>, the equality is satisfied. Thus, we get that <math>n = 20 + 2^{19}</math>, which is less than <math>10^6</math>, and we should be done. However, this requires slightly more formalization, and can be proven directly more easily if <math>n = 20+2^{19}</math> is known or suspected.  
  
−
==Solution 2==
 
−
 
−
We divide the positive numbers into <math>999999</math> groups.
 
 
{{MAA Notice}}
 
{{MAA Notice}}
  
 
==See also==
 
==See also==
 
{{USAJMO newbox|year=2016|num-b=1|num-a=3}}
 
{{USAJMO newbox|year=2016|num-b=1|num-a=3}}

Latest revision as of 14:43, 4 March 2023

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. AMC logo.png

See also

2016 USAJMO (Problems • Resources)
Preceded by
Problem 1 		Followed by
Problem 3
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2016_USAJMO_Problems/Problem_2&oldid=190622"