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$.
Asked
Active
Viewed 247 times
3
-
What does the overline stand for? – hmakholm left over Monica Nov 11 '12 at 19:51
2 Answers
5
Hint: The number $\overline{a1\cdots 1b}$ can be expressed as $$a\cdot10^{n+1} + \frac{10^n-1}9\cdot 10 +b.$$
Hagen von Eitzen
- 374,180
-
Thanks. I did this of course but how do I prove the existence of such a and b? – Adam Nov 11 '12 at 20:05
-
... and $1/9 \equiv -9 \pmod{41}$. Also there are only 5 possible different values of $10^{n+1}$ modulo 41. – hmakholm left over Monica Nov 11 '12 at 20:08
3
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}$.
Brian M. Scott
- 616,228
-
Actually, 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$. – Hagen von Eitzen Nov 11 '12 at 22:16