23
$\begingroup$

So basically we have a number $10101...10101$ that contains $2016$ zeros and can be written as$ \sum _{ k=0 }^{ 2016 }{ 100^{ k } }$ . I want to prove that this number is not a prime without using anything besides a piece of paper and a pen. I'm stuck on this for quite a few days now.

$\endgroup$
5
  • 1
    $\begingroup$ Hint: See the Sum of digits. $\endgroup$
    – Chad Shin
    Feb 11, 2016 at 0:02
  • 4
    $\begingroup$ @ChadShin The sum of the digits is $2017$, which is not divisible by $3$. $\endgroup$
    – user236182
    Feb 11, 2016 at 0:03
  • $\begingroup$ Then $10101...10101$=$\frac{10^{4014}-1}{99}$? $\endgroup$
    – Chad Shin
    Feb 11, 2016 at 0:05
  • 2
    $\begingroup$ @ChadShin 4034 in the exponent. $\endgroup$ Feb 11, 2016 at 0:06
  • $\begingroup$ It would give you some insight to use a computer to factor this number. The smallest prime factor is 80681, so I would look for a pattern to the multiples of that prime. $\endgroup$ Feb 11, 2016 at 13:24

4 Answers 4

35
$\begingroup$

Note that $1010101....10101$ is $\frac{10^{4034}-1}{99}$.

Also, $10^{4034}-1$ is $(10^{2017}-1)(10^{2017}+1)$, both of which are larger than $99$.

This implies that the number is not prime.

$\endgroup$
6
  • 7
    $\begingroup$ Specifically, $10^{2017}-1$ is divisible by $9$ and $10^{2017}+1$ is divisible by $11$. So this factorization can be written as $(111\cdots 1)\cdot (909090\dots91)$. $\endgroup$ Feb 11, 2016 at 0:12
  • 2
    $\begingroup$ @MXYMXY If the number of $1$s is even, then $101$ divides such a number. If the number of $1$s is $2k+1$, ThomasAndrews shows that you have $\overbrace{11\cdots1}^{2k+1}\cdot\overbrace{9090\cdots9091}^{2k}$. $\endgroup$
    – 2'5 9'2
    Feb 11, 2016 at 0:22
  • 1
    $\begingroup$ Using pen and paper, how did you figure out 1010101... is 10^4034-1/99? $\endgroup$ Feb 11, 2016 at 11:36
  • 6
    $\begingroup$ @Thomas Well, $101 \dots 101=\sum _{ k=0 }^{ 2016 }{ 100^{ k } }$, as pointed by OP. So I used the formula for the sum of geometric progressions. $\endgroup$
    – S.C.B.
    Feb 11, 2016 at 11:51
  • 2
    $\begingroup$ @Thomas $1~\overbrace{01~01}^{2016} = \overbrace{01~01~01}^{2016+1}= \frac{\overbrace{99~99~99}^{2016+1}}{99}=\frac{100^{2016+1} - 1}{99} = \frac{10^{4034}-1}{99} $ $\endgroup$ Feb 11, 2016 at 14:15
13
$\begingroup$

And since you have asked this question, here is an interesting piece of information, that in the sequence $101,10101,1010101,....$ none of the numbers are prime EXCEPT the first one. This can be proved quite easily and in your case the number is $${{(10^{4034}-1)}/99}$$, and the numerator can be written as $${{(10^{2017}}-1)} \times {{(10^{2017}}+1)}$$ and the first multiplicand has a factor 10-1=9 and the second multiplicand has a factor 10+1=11 so their product is divisible by 9 and 11, which are coprime,hence divisible by 99, so the number is not prime, because it has 2 factors now both greater than 1. So it is a prime which is anyway supported by the result above.

$\endgroup$
5
  • $\begingroup$ Why does it prove it is not a prime when the factors in the numerator are greater than 99? $\endgroup$ Feb 11, 2016 at 0:28
  • $\begingroup$ yes look at the first question @mathsmittens there is the solution to the result I stated, that's why I attached it. $\endgroup$ Feb 11, 2016 at 0:29
  • $\begingroup$ @mathsmittens because none of the above numbers will be completely cancelled by 9 and 11. in fact i will edit it right now. just a sec. $\endgroup$ Feb 11, 2016 at 0:32
  • $\begingroup$ @mathsmittens yep edited it now. hope it is okay now. :) $\endgroup$ Feb 11, 2016 at 0:38
  • $\begingroup$ This argument fails when the number of $1$'s is prime. The same argument would claim there are no prime repunits, but OEIS has a list that are, starting with $11$ and $(10^{19}-1)/9$ $\endgroup$ Feb 11, 2016 at 15:29
8
$\begingroup$

Suppose $n + 1$ is odd. Let $a$ be a real number such that $|a| \neq 1$.

Then $X = \sum_{k=0}^{n}a^{2k} = \frac{a^{2(n+1)} - 1}{a^{2}-1} = \frac{a^{n+1} - 1}{a - 1} \cdot \frac{(-a)^{n+1} - 1}{(-a) - 1} = \sum_{k=0}^{n}a^{k} \cdot \sum_{k=0}^{n} (-a)^{k}$.

$\endgroup$
5
$\begingroup$

In fact, you can generalize this to any base $a\in\mathbb Z_{\ge 2}$.

If $a,k\in\mathbb Z_{\ge 2}$, then ($_a$ denotes 'base $a$'):

$$\underbrace{10101\cdots 101_a}_{k\text{ zeros}}=\sum_{i=0}^k a^{2i}=\frac{a^{2(k+1)}-1}{a^2-1}=\frac{\left(a^{k+1}+1\right)\left(a^{k+1}-1\right)}{a^2-1},$$

$a^{k+1}+1>a^{k+1}-1>a^2-1$, therefore $\underbrace{10101\cdots 101_a}_{k\text{ zeros}}$ is composite.

Therefore, $10101_a, 1010101_a,\ldots$ are all composite (for any base $a\in\mathbb Z_{\ge 2}$).

$\endgroup$
1
  • $\begingroup$ That is very interesting. Thank you for this insight. $\endgroup$
    – eem
    Aug 17, 2019 at 14:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .