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$
  • 1
    $\begingroup$ Hint: See the Sum of digits. $\endgroup$ – Chad Shin Feb 11 '16 at 0:02
  • 4
    $\begingroup$ @ChadShin The sum of the digits is $2017$, which is not divisible by $3$. $\endgroup$ – user236182 Feb 11 '16 at 0:03
  • $\begingroup$ Then $10101...10101$=$\frac{10^{4014}-1}{99}$? $\endgroup$ – Chad Shin Feb 11 '16 at 0:05
  • 2
    $\begingroup$ @ChadShin 4034 in the exponent. $\endgroup$ – Thomas Andrews Feb 11 '16 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$ – Robert Soupe Feb 11 '16 at 13:24
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$
  • 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$ – Thomas Andrews Feb 11 '16 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$ – alex.jordan Feb 11 '16 at 0:22
  • 1
    $\begingroup$ Using pen and paper, how did you figure out 1010101... is 10^4034-1/99? $\endgroup$ – Thomas Weller Feb 11 '16 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 '16 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$ – CodesInChaos Feb 11 '16 at 14:15
12
$\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$
  • $\begingroup$ Why does it prove it is not a prime when the factors in the numerator are greater than 99? $\endgroup$ – mathsmittens Feb 11 '16 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$ – user260674 Feb 11 '16 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$ – user260674 Feb 11 '16 at 0:32
  • $\begingroup$ @mathsmittens yep edited it now. hope it is okay now. :) $\endgroup$ – user260674 Feb 11 '16 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$ – Ross Millikan Feb 11 '16 at 15:29
7
$\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$
4
$\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$
  • $\begingroup$ That is very interesting. Thank you for this insight. $\endgroup$ – Aditya Dutt Aug 17 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.