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 "Mock AIME 1 2006-2007 Problems/Problem 12"

(→‎Solution)
m
Line 1: Line 1:
 
==Problem==
 
==Problem==
−
Let <math>k</math> be a positive integer with a first digit four such that after removing the first digit, you get another positive integer, <math>m</math>, that satisfies <math>14m+1=k</math>. Find the number of possible values of <math>m</math> between <math>0</math> and <math>10^{2007}</math>.
+
Let <math>k</math> be a [[positive integer]] with first [[digit]] 4 such that after removing the first digit, you get another positive integer, <math>m</math>, that satisfies <math>14m+1=k</math>. Find the number of possible values of <math>m</math> between <math>0</math> and <math>10^{2007}</math>.
 
==Solution==
 
==Solution==
−
The digit-removal condition is equivalent to the statement <math>k = 4\cdot10^n + m</math> where <math>10^n > m</math> and <math>n \geq 1</math>.  Thus <math>14m + 1 = 4\cdot 10^n + m</math> so <math>13m = 4\cdot 10^n - 1</math> and <math>m = \frac{4 \cdot 10^n - 1}{13}</math>.  It's easy to see that this value of <math>m</math> is small enough, so all we need to check is that it is an integer.  That happens if and only if 13 [[divide]]s <math>4\cdot 10^n - 1</math>, so <math>4\cdot 10^n \equiv 1 \pmod{13}</math> and multiplying by <math>4^{-1} \equiv 10 \pmod{13}</math> we have that <math>10^n \equiv 10 \pmod {13}</math>  Certainly <math>n = 1</math> is a solution.  All we need is the order of 10 <math>\pmod {13}</math>.  Now <math>10^2 = 100 \equiv 9</math> so <math>10^3 \equiv 90 \equiv -1</math> so <math>10^6 \equiv 1 \pmod{13}</math> and the order of 10 mod 13 is 6.  Thus, we get one value of <math>m</math> each time <math>n = 6j + 1</math>.  There are <math>335</math> such values of <math>n</math> which fall in the required range.
+
The digit-removal condition is equivalent to the statement <math>k = 4\cdot10^n + m</math> where <math>10^n > m</math> and <math>n \geq 1</math>.  Thus <math>14m + 1 = 4\cdot 10^n + m</math> so <math>13m = 4\cdot 10^n - 1</math> and <math>m = \frac{4 \cdot 10^n - 1}{13}</math>.  It's easy to see that this value of <math>m</math> is small enough, so all we need to check is that it is an [[integer]].  That happens if and only if 13 is a [[divisor]] of <math>4\cdot 10^n - 1</math>, so <math>4\cdot 10^n \equiv 1 \pmod{13}</math> and multiplying by <math>4^{-1} \equiv 10 \pmod{13}</math> we have that <math>10^n \equiv 10 \pmod {13}</math>  Certainly <math>n = 1</math> is a solution.  All we need is the order of 10 <math>\pmod {13}</math>.  Now <math>10^2 = 100 \equiv 9 \pmod{13}</math> so <math>10^3 \equiv 90 \equiv -1 \pmod{13}</math>, <math>10^6 \equiv 1 \pmod{13}</math> and the order of 10 mod 13 is 6.  Thus, we get one value of <math>m</math> each time <math>n = 6j + 1</math>.  There are <math>335</math> such values of <math>n</math> which fall in the required range.
 
----
 
----
  

Revision as of 01:00, 12 November 2006

Problem

Let $k$ be a positive integer with first digit 4 such that after removing the first digit, you get another positive integer, $m$, that satisfies $14m+1=k$. Find the number of possible values of $m$ between $0$ and $10^{2007}$.

Solution

The digit-removal condition is equivalent to the statement $k = 4\cdot10^n + m$ where $10^n > m$ and $n \geq 1$. Thus $14m + 1 = 4\cdot 10^n + m$ so $13m = 4\cdot 10^n - 1$ and $m = \frac{4 \cdot 10^n - 1}{13}$. It's easy to see that this value of $m$ is small enough, so all we need to check is that it is an integer. That happens if and only if 13 is a divisor of $4\cdot 10^n - 1$, so $4\cdot 10^n \equiv 1 \pmod{13}$ and multiplying by $4^{-1} \equiv 10 \pmod{13}$ we have that $10^n \equiv 10 \pmod {13}$ Certainly $n = 1$ is a solution. All we need is the order of 10 $\pmod {13}$. Now $10^2 = 100 \equiv 9 \pmod{13}$ so $10^3 \equiv 90 \equiv -1 \pmod{13}$, $10^6 \equiv 1 \pmod{13}$ and the order of 10 mod 13 is 6. Thus, we get one value of $m$ each time $n = 6j + 1$. There are $335$ such values of $n$ which fall in the required range.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_1_2006-2007_Problems/Problem_12&oldid=11616"