Difference between revisions of "Mock AIME 1 2006-2007 Problems/Problem 12"

m
(No difference)

Revision as of 15:49, 3 April 2012

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.