I got stuck with the following problem. Please give me an idea. Prove that for every natural number $n$ there is a number $\overline{a1 \cdots 1 b}$ which is divisible by $41$ and the number of $1$'s is exactly $n$.
Divisibility problem
-
0What does the overline stand for? – 2012-11-11
2 Answers
Hint: The number $\overline{a1\cdots 1b}$ can be expressed as $a\cdot10^{n+1} + \frac{10^n-1}9\cdot 10 +b.$
-
0... and $1/9 \equiv -9 \pmod{41}$. Also there are only 5 possible different values of $10^{n+1}$ modulo 41. – 2012-11-11
Let
$m=\overline{a\underbrace{1\dots 1}_nb}=10^{n+1}a+b+10\sum_{k=0}^{n-1}10^k=10^{n+1}a+b+\frac{10(10^n-1)}9\;.$
Let $r=10^{n+1}\bmod 41$ and $s=\frac{10}9(10^n-1)\bmod 41$; then $m\equiv ar+s+b\pmod{41}$. Thus, you want to find $a\in\{1,\dots,9\}$ and $b\in\{0,\dots,9\}$ such that $ar+s+b\equiv 0\pmod{41}$.
Now $10^5\equiv 1\pmod{41}$, so $r\in\{1,10,16,18,37\}$. Show that as $a$ ranges over $\{1,\dots,9\}$ and $b$ ranges over $\{0,\dots,9\}$, $ar+b$ ranges over all possible values mod $41$, so that you can always choose $a$ and $b$ to make $ar+s+b\equiv 0\pmod{41}$, no matter what $s$ is.
Correction: As Hagen points out, if $r=1$, $ar+b=a+b$ does not in fact cover the full range of residues mod $41$. However, in that case $5\mid n+1$, so you can explicitly compute $s\bmod{41}=\frac{10}9(10^n-1)\bmod{41}$ and verify that there is indeed a choice of $a$ that makes $ar+s+b\equiv 0\pmod{41}$.
-
0Actually, e.g. for $r=1$ the values $ar+b$ do *not* range over *all* possible values mod 41, only over $0,\ldots, 18$. But fortunately $r=1$ implies something special about $s$. – 2012-11-11