2
$\begingroup$

How to prove that number $11...1$ (there are exactly $91$ ones) is composite? I considered this number modulo some small primes, but none of them worked.

$\endgroup$
  • $\begingroup$ This isn't really an answer, but it might help to see that the prime factorization isn't something simple for this number. $\endgroup$ – Tyberius Mar 18 '17 at 14:44
2
$\begingroup$

Note that

$$111\cdots 1 = \frac{999\cdots 9}{9} = \frac{10^{91}-1}{9} =\frac{(10^{7})^{13}-1}{9} =\frac{ (10^{7}-1)((10^{7})^{12} + (10^{7})^{11} + \cdots + 1)}{9} $$

$$ = \frac{ 10^{7}-1}{9} ((10^{7})^{12} + (10^{7})^{11} + \cdots + 1) =1111111\cdot((10^{7})^{12} + (10^{7})^{11} + \cdots + 1)$$

$\endgroup$
5
$\begingroup$

Notice that $91=13\cdot 7$. Consider the number $n=\sum_{k=0}^{12}10^k$, i.e. the number $111\cdots1$ with $13$ ones. Then $$\sum_{k=0}^{90}10^{k}=n+n\cdot 10^{13}+n\cdot 10^{26}+\cdots+n\cdot 10^{78}.$$

In general you have the following $$\left(\sum_{k=0}^{p-1}10^k\right)\cdot\left(\sum_{h=0}^{q-1}10^{hp}\right)=\sum_{h=0}^{q-1}\sum_{k=0}^{p-1}10^{k+hp}=\sum_{n=0}^{pq-1}10^n.$$ Thus any number made of a composite number of ones is still composite.

$\endgroup$
1
$\begingroup$

Since $u_n=111...111$ with $n$ ones is $\frac19(10^n-1)$, if $n = ab$, and using the factorization $x^m-1 =(x-1)\sum_{j=0}^{m-1} x^j $,

$\begin{array}\\ u_n &=\frac19(10^n-1)\\ &=\frac19(10^{ab}-1)\\ &=\frac19(10^{a}-1)\sum_{j=0}^{b-1}10^{aj}\\ \end{array} $

so $u_n$ is divisible by $u_a$ (and also by $u_b$).

Therefore, as Ender Wiggins pointed out, since $91=7\cdot 13$, $u_{91}$ is divisible by $u_7$ and $u_{13}$.

$\endgroup$
0
$\begingroup$

Try generalizing the following: $$ 111111=1001\cdot111=10101\cdot11. $$ Added: The more general phenomenon is that numbers whose base-$10$ representation has a repeating pattern, where the repeating unit consists of more than a single digit, are necessarily composite. For example, $$ 762127621276212=76212\cdot10000100001. $$ Our example $111111$ fits this description, since it can be thought of as two repetitions of the unit $111$ or as three repetitions of the unit $11$.

Interestingly, if the repeating pattern is only one digit long, as in $77777$, the number is, again, composite, as long as the digit is not $1$: $$ 77777=7\cdot11111. $$ The only case left is the case of repeating $1$s with a prime number of digits. These may very well be prime. Apart from $11$, the smallest example is the number consisting of $19$ $1$s.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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