Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question
    
What does the overline stand for? –  Henning Makholm Nov 11 '12 at 19:51

2 Answers 2

Hint: The number $\overline{a1\cdots 1b}$ can be expressed as $$a\cdot10^{n+1} + \frac{10^n-1}9\cdot 10 +b.$$

share|improve this answer
    
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. –  Henning Makholm Nov 11 '12 at 20:08

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}$.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.