# How to find divisibility of a very large number

I was asked this question in a test:

The number $$111111...111$$ ($$1$$ comes 91 times) is a:

A) Prime number

B) Composite Number

C) divisible by $$\frac{10^7 -1}{9}$$

The answer is B & C

How are we supposed to check divisibility by such a large number? I think that somehow Binomial Theorem comes into play but cannot figure out what splitting to do

• Looking at what $\frac{10^7-1}9$ actually is will probably help you greatly. – Arthur Mar 27 at 15:12
• It is 1111111. But I can't find a way to check if 91 times is divisible by 7 times – Fitz Watson Mar 27 at 15:15
• Is $777$ divisible by $7$? Is there an obvious way to see this immediately? Is $111\,111$ divisible by $11$? Is there an obvious way to see this immediately? Now apply the same tactic to your problem. – Arthur Mar 27 at 15:20
• – J. W. Tanner May 7 at 19:33

## 7 Answers

You want to show $$10^7-1|10^{91}-1$$. This follows from $$n-1|n^k-1$$ (prove by induction on $$k$$) with $$k=13$$.

$$111111111111111111111111111111111111111111111111111$$

$$1111111111111111111111111111111111111111$$

$$=1111111\times1000000100000010000001000000100000010000001$$

$$000000100000010000001000000100000010000001$$

• How did you come to know that it can be broken in such a manner? – Fitz Watson Mar 27 at 15:13
• Sorry but I didn't understand the meaning of $10^7 \equiv 1 (mod p)$. The notations $\equiv$ and $(mod p)$ are unknown to me – Fitz Watson Mar 27 at 15:52
• But @J.G. 's answer helped clear it out for me – Fitz Watson Mar 27 at 15:52
• Good. $a\equiv b \pmod p$ means $p$ divides $a-b.$ $10^7\equiv1 \pmod {10^7-1}$ so $(10^7)^{13}$=$10^{91}\equiv 1 \pmod {10^7-1}$, which means $10^7-1$ divides $10^{91}-1$ – J. W. Tanner Mar 27 at 16:02

Hint: The number is $$\frac{10^{91}-1}{9}$$. Then $$\frac{\frac{10^{91}-1}{9}}{\frac{10^7-1}{9}} = \frac{10^{91}-1}{10^7-1} = \frac{(10^{7})^{13}-1}{10^7-1}$$

You are supposed to follow the hinted at answer (C) and conclude (B) is true as well.

$$\frac{10^7-1}{9}=1111111$$. If you look at some simple cases, you readily see that $$1111111\mid 1111111$$ ($$7$$ ones) and $$1111111\mid 11111111111111$$ ($$14$$ ones) and see inductively that $$1111111$$ will divide any string of ones whose number is a multiple of $$7$$.

$$91$$ is a multiple of $$7$$.

J.W. Tanner does the division explicitly in his answer, and Dr. Sonnhard Graubner hints at the divisibility requirement in his answer. This answer addresses in finer detail the question you asked about "how to check the divisibility."

Any number that's fully 1's of composite length is composite. If the length is $$c\cdot b$$, then that means, it contains the lower number with c 1's exactly b times, in non overlapping substrings. This makes it divisible by the number with c 1's . In this case, $$91=7\cdot 13$$. This means, the 91 ones, can be grouped as follows: $$1111111111111,1111111111111,1111111111111,111111111111,1111111111111,1111111111111,1111111111111$$ or $$1111111,1111111,1111111,1111111,111111,1111111,1111111,1111111,111111,1111111,1111111,1111111,1111111$$

But these substrings have values (in base 10) of $$\frac{10^{13}-1}{9}$$ and $$\frac{10^{7}-1}{9}$$ respectively.

91 ones represents S=$$\sum_{k=0}^{90}10^k$$

$$S=\frac{1*10^{91}-1}{10-1}=\frac{10^{91}-1}{9}$$

One less than any power of 10 is divisible by 9 but that factor is cancelled by the denominator.

$$91=7 \times 13$$

$$a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+a^{n-3}b^2+...+b^{n-1})$$

$$10^{91}=(10^7)^{13}$$

Let $$a=10^7$$ and $$b=1$$.

Then $$10^{91}-1=(10^7-1)(10^{84}+10^{77}+10^{70}+...+1)$$

So $$S=\frac{(10^7-1)(10^{84}+10^{77}+10^{70}+...+1)}{9}$$

Iterating the process again:

$$S=\frac{9(10^6+10^5+10^4+..+1)(10^{84}+10^{77}+10^{70}+...+1)}{9}$$

• Did you mean that factor is cancelled by the denominator? – J. W. Tanner Mar 28 at 4:16
• I thought I'd keep the 9 in numerator and denominator to keep that in mind. It cancels with the other nine leaving explicitly the product of two other numbers so it isn't prime. – TurlocTheRed Mar 28 at 16:42
• I was just saying: did you mean to write the word denominator where you wrote the word numerator? – J. W. Tanner Mar 28 at 16:47
• I see. Thanks! will correct. – TurlocTheRed Mar 28 at 16:49

Hint: $$91=7\cdot 13$$ and so your number is not prime

• I'm sorry but I didn't get the hint – Fitz Watson Mar 27 at 15:12