14
$\begingroup$

This is an exercise from a sequence and series book that I am solving.

I tried manipulating the number to make it easier to work with:

$$111...1 = \frac{1}9(999...) = \frac{1}9(10^{55} - 1)$$

as the number of $1$'s is $55$.

The exercise was under Geometric Progression and Geometric Mean. However, I am unable to think of a way to solve this problem using GP.

How do I proceed from here?

$\endgroup$
  • $\begingroup$ It is listed under geometric progression and geometric mean because that's how you get from $111\ldots$ to $\frac{1}{9}(10^{55} - 1)$ $\endgroup$ – Ekesh Kumar Jan 29 '19 at 6:43
  • 2
    $\begingroup$ You can either do five blocks of eleven 1s: $$11111111111\ 11111111111\ 11111111111\ 11111111111\ 11111111111 \\ = 11111111111\times 100000000001000000000010000000000100000000001$$ or you can do eleven blocks of five 1s: $$11111\ 11111\ 11111\ 11111\ 11111\ 11111\ 11111\ 11111\ 11111\ 11111\ 11111 \\ = 11111\times 100001000010000100001000010000100001000010000100001$$ It turns out, in this case, that all these factors are themselves composite. $\endgroup$ – Jeppe Stig Nielsen Jan 29 '19 at 21:17
  • 3
    $\begingroup$ This type of number is called a “repunit”. $\endgroup$ – Dan Jan 29 '19 at 21:21
  • 1
    $\begingroup$ @JeppeStigNielsen. And this shows that for a number consisting of $n$ ones (in any basis!) can only be prime if $n$ is prime. This is the primary background of Mersenne primes. $\endgroup$ – md2perpe Jan 30 '19 at 9:05
  • $\begingroup$ Cf. this question $\endgroup$ – J. W. Tanner May 7 '19 at 19:33
31
$\begingroup$

The number is composite.

We have

\begin{align*} \underbrace{11\ldots111}_{55 \text{ times }} = \frac{1}{9} \cdot (10^{55} - 1) \\ = \frac{1}{9} \cdot ((10^{5})^{11} - 1) \\ \end{align*}

Also, note that $x^{m} - 1$ is divisible by $x - 1$. Here, we can plug in $x = 10^{5}$ and $m = 11$. As a result, we see that the quantity is divisible by $99999$, meaning that the number must be divisible by $11111$ (and hence, composite).

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Can you please elaborate on the last step? How did you get k and concluded it to be an integer? Sorry, I am terrible at maths. $\endgroup$ – user69284 Jan 29 '19 at 6:45
  • 12
    $\begingroup$ "As a result, we see that the quantity is divisible by 99999" - this isn't right, surely. If it is divisible by 99999 then it is also divisible by 9 and as we all know something is divisible by 9 if the sum of the digits is divisible by 9. The sum of the digits of the original number is obviously 55 so it is not divisible by 9. $\endgroup$ – Chris Jan 29 '19 at 10:20
  • 19
    $\begingroup$ Oh, I think I see the confusion now. You have your factor of $1/9$ multiplying your number so in fact I believe you mean to say that the original number is divisible by 11111 $\endgroup$ – Chris Jan 29 '19 at 10:22
  • $\begingroup$ Isn't $x^m-1$ always divisible by $x-1$, not just when $m$ is odd? $\endgroup$ – Dan Jan 29 '19 at 21:17
  • 1
    $\begingroup$ @Dan That is true, but since we have a factor of $1/9$, we get $(1/9)\cdot(10-1)=1$ divides $11\dots1$ which isn't very helpful. $\endgroup$ – boboquack Jan 29 '19 at 22:43
36
$\begingroup$

You can see with some very quick "in your head" maths that this is a composite number. Since 55 is 5 times 11 we can take a number that is 11111111111 (eleven ones) and divide the original by it using standard long division. Its easy to see that the result will be 100000000001000000000010000000000100000000001.

Similarly you can see trivially see that 11111 is a factor of the number.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ If I may add: this becomes clearer if you think of splitting the number into equally-sized chunks. Thus you can conclude that any number whose representation consists of a non-prime number of digits is composite. $\endgroup$ – potestasity Jan 29 '19 at 12:57
  • 6
    $\begingroup$ @potestasity I think you mean "a non-prime number of identical digits"? Otherwise you may have accidentally destroyed most of the world's prime numbers. And of course it does not matter if the number of digits is composite, if the digit is itself not 1, e.g. 22222. $\endgroup$ – David Robinson Jan 29 '19 at 14:04
  • $\begingroup$ @DavidRobinson: While I agree with your initial point I don't follow your last sentence. If you had 55 2s instead of 55 1s the logic still works doesn't it? $\endgroup$ – Chris Jan 29 '19 at 14:17
  • 2
    $\begingroup$ @Chris If you had 55 2's you simply would divide by 2. $\endgroup$ – rus9384 Jan 29 '19 at 14:36
  • 1
    $\begingroup$ @Chris The point is that it works for 53 2's as well, because it's (53 1's) * 2. $\endgroup$ – Random832 Jan 29 '19 at 14:36
20
$\begingroup$

More explicitly, $$\begin{align*} \frac{10^{55} - 1}{9} &= \frac{(10^5)^{11} - 1}{9} \\ &= \frac{(10^5 - 1)(10^{50} + 10^{45} + 10^{40} + \cdots + 10 + 1)}{9} \\ &= \frac{(10 - 1)(10^4 + 10^3 + 10^2 + 10^1 + 1)(10^{50} + 10^{45} + \cdots + 1)}{9} \\ &= (10^4 + 10^3 + \cdots + 1)(10^{50} + 10^{45} + \cdots + 1). \end{align*}$$ The first factor is $11111$, which in turn is $41 \cdot 271$, and the second factor has as its smallest prime factor $1321$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Also, splitting $5\times 11$ the other way around, you get that 11111111111 is also a factor, and it doesn't share any factor with 11111, so this way, you can divide out both of them (if you wanted to get closer to full factorization instead of just proving it's composite). The remaining number is still large, though. $\endgroup$ – orion Jan 30 '19 at 7:55
6
$\begingroup$

This number can be written as $$x=\sum_{k=1}^{55}10^{k-1}$$ i.e. it has the following form: $$x=\sum_{k=1}^{n}a^{k-1}$$

Such numbers are always composite if $n$ is composite. Let $n = pq$, where $p,q\in\mathbb N$. Then, $$x=\sum_{k=1}^{pq}a^{k-1} = \sum_{l=1}^p \sum_{m=1}^q a^{q(l-1)+(m-1)}= \left(\sum_{l=1}^p a^{q(l-1)}\right)\left(\sum_{m=1}^q a^{(m-1)}\right)$$

Since, $55$ is composite, it follows that $\sum_{k=1}^{55}10^{k-1}$ is composite as well.

Simple illustrative example

To get the idea behind this construction, consider a simpler example of $$x = 111111=\sum_{k=1}^{6}10^{k-1}.$$ This number can be factorized using this construction (and the fact that $6=2\cdot3$) as $$x = 111000 + 111= 1001\cdot111$$ or $$x=110000 + 1100 + 11 = 10101\cdot11.$$

General conclusion

If a natural number $x$ can be represented with a string of composite number of repeating $1$s (regardless of the base of the numeral system), then $x$ is composite.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ If a natural number can be represented as two or more repetitions of the same digit sequence other than "1" then it is composite. If you have a composite number a*b of 1's then you have a repeats of (b 1's). $\endgroup$ – gnasher729 Jan 29 '19 at 18:46
  • $\begingroup$ I think the math is nicer if you do $\sum_{k=0}^{54}10^k$. $\endgroup$ – Acccumulation Jan 29 '19 at 21:05
  • $\begingroup$ This is the best answer here imo $\endgroup$ – goblin Jan 30 '19 at 3:26
  • $\begingroup$ @Acccumulation perhaps it is. I just wanted to write $55$ without writing $55-1$. Writing $k-1$ looks less bad to me. $\endgroup$ – Danijel Jan 30 '19 at 9:13
2
$\begingroup$

The prime factorization of the number is:

$$41 \cdot 271 \cdot 1321 \cdot 21649 \cdot 62921 \cdot 513239 \cdot 83251631 \cdot 1300635692678058358830121$$

obtained by FactorInteger[] in Mathematica.

| cite | improve this answer | |
$\endgroup$
  • 6
    $\begingroup$ Can you clarify how you obtained this? $\endgroup$ – Pedro A Jan 29 '19 at 11:14
  • 3
    $\begingroup$ I think if the OP searched for the factorization alone, he had used a calculator in the first place $\endgroup$ – Nico Haase Jan 29 '19 at 14:14
  • $\begingroup$ @PedroA Several repunit factorizations are available here $\endgroup$ – LegionMammal978 Jan 29 '19 at 15:33
  • $\begingroup$ I got the same thing just entering factor((10^55-1)/9); into Maxima. $\endgroup$ – Daniel Schepler Jan 29 '19 at 18:10
  • $\begingroup$ Or Maple or any other computer algebra system. $\endgroup$ – David G. Stork Jan 29 '19 at 18:10
1
$\begingroup$

You can either do five blocks of eleven 1s:

$$11111111111\ 11111111111\ 11111111111\ 11111111111\ 11111111111 \\ =11111111111×100000000001000000000010000000000100000000001$$

or you can do eleven blocks of five 1s:

$$11111\ 11111\ 11111\ 11111\ 11111\ 11111\ 11111\ 11111\ 11111\ 11111\ 11111 \\ =11111×100001000010000100001000010000100001000010000100001$$

It turns out, in this case, that all these factors are themselves composite.

(Answer taken from comment by Jeppe Stig Nielsen.)

| cite | improve this answer | |
$\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.