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.
-
1$\begingroup$ Hint: See the Sum of digits. $\endgroup$– Chad ShinFeb 11, 2016 at 0:02
-
4$\begingroup$ @ChadShin The sum of the digits is $2017$, which is not divisible by $3$. $\endgroup$– user236182Feb 11, 2016 at 0:03
-
$\begingroup$ Then $10101...10101$=$\frac{10^{4014}-1}{99}$? $\endgroup$– Chad ShinFeb 11, 2016 at 0:05
-
2$\begingroup$ @ChadShin 4034 in the exponent. $\endgroup$– Thomas AndrewsFeb 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$– Robert SoupeFeb 11, 2016 at 13:24
4 Answers
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.
-
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'2Feb 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
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.
-
$\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
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}$.
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}$).
-
$\begingroup$ That is very interesting. Thank you for this insight. $\endgroup$– eemAug 17, 2019 at 14:26