13
$\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 at 6:43
  • 1
    $\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 at 21:17
  • 3
    $\begingroup$ This type of number is called a “repunit”. $\endgroup$ – Dan Jan 29 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 at 9:05
30
$\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).

$\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 at 6:45
  • $\begingroup$ Check the edit. I have found a better (and easier to understand) solution. $\endgroup$ – Ekesh Kumar Jan 29 at 6:51
  • 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 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 at 10:22
  • 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 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.

$\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 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 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 at 14:17
  • 2
    $\begingroup$ @Chris If you had 55 2's you simply would divide by 2. $\endgroup$ – rus9384 Jan 29 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 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$.

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

$\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 at 18:46
  • $\begingroup$ I think the math is nicer if you do $\sum_{k=0}^{54}10^k$. $\endgroup$ – Acccumulation Jan 29 at 21:05
  • $\begingroup$ This is the best answer here imo $\endgroup$ – goblin Jan 30 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 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.

$\endgroup$
  • 6
    $\begingroup$ Can you clarify how you obtained this? $\endgroup$ – Pedro A Jan 29 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 at 14:14
  • $\begingroup$ @PedroA Several repunit factorizations are available here $\endgroup$ – LegionMammal978 Jan 29 at 15:33
  • $\begingroup$ I got the same thing just entering factor((10^55-1)/9); into Maxima. $\endgroup$ – Daniel Schepler Jan 29 at 18:10
  • $\begingroup$ Or Maple or any other computer algebra system. $\endgroup$ – David G. Stork Jan 29 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.)

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