Divisibility problem 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$.
 A: Hint: The number $\overline{a1\cdots 1b}$ can be expressed as
$$a\cdot10^{n+1} + \frac{10^n-1}9\cdot 10 +b.$$
A: 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}$.
