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

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.