What is the concept behind divisibility of large numbers that contain only the digit 1?

Question

An example question I found in a text book is :

The 300 digit number with all digits equal to 1 is :

A) Divisible by neither 37 nor 101 B) divisible by 37 but not by 101 C) divisible by 101 but not by 37 D) Divisible by both 37 and 101

Hint: the $300$ digit number will contain repetitions of $111$ and repetitions of $1111$. — Raymond Manzoni, Nov 09 '13 at 13:57
@RaymondManzoni I don't know how that can be solved using the hint you've provided, I'm absolutely new to this kind of remainder questions — , Nov 09 '13 at 14:06
Try it with simpler examples : $111111$ may be written as $111\times 1000+111=111\times 1001$ so that $111111$ may be divided by $111$ and $1001$. Now $111$ and $1001$ may themselves have divisors... (in your case you are interested only by the $111$ divisor since the other one would look something like $10010010010\cdots01$). — Raymond Manzoni, Nov 09 '13 at 14:08
Oh ok....but can't get the 101 part for the 300 digit number @RaymondManzoni — , Nov 09 '13 at 14:22
The other repetition (since $300=75\times 4$) was of $1111$. — Raymond Manzoni, Nov 09 '13 at 14:25

score 0 · Accepted Answer · answered Nov 09 '13 at 14:29

$$\underbrace{11\cdots11}_{n \text{ digits}}=\frac{10^n-1}9$$ where $n$ is a positive integer

Now observe that $10^2\equiv-1\pmod {101}\implies 10^4\equiv1$

$\displaystyle\implies 10^{300}=(10^4)^{75}\equiv1^{75}\pmod{101}\equiv1$

$\displaystyle\implies 10^{300}-1\equiv0\pmod{1000} \implies \frac{10^{300}-1}9\equiv0\pmod{101}$ as $(101,9)=1$

Now, $10^3\equiv1\pmod {37}$ and $(37,9)=1$

1 Answers1