# How to prove that a very large number is not prime

I'm solving few math problems for an upcoming math contest .

I am stuck with a short problem, where I have to prove that $A$ is not prime .

$$A = 100\ 000\ 000\ 000\ 000\ 000\ 001$$

$A$ is not a binary number. It's a decimal one.

I've tried to rewrite like this:

$$A = 1 \times 10^{20} + 1$$

But what can I do with that . I can't use GCD since it would a very long time to finish it and Obviously this isn't the point from this problem .

• Which is it? $10^{20}+1$ or $10^{21}+1$? – almagest May 5 '16 at 19:23
• Looks like $10^{21}+1$, divisible by $11$. – André Nicolas May 5 '16 at 19:24
• $10^{20}+1$ has the factor $10001$, $10^{21}+1$ is even easier it has many factors (including $7,11,13$). – almagest May 5 '16 at 19:25
• For positive odd $n$, $y+1$ is a factor of $y^n+1$. So $x^4+1$ is a factor of $(x^4)^5+1$, and $x+1$ is a factor of $x^{21}+1$. – peterwhy May 5 '16 at 19:28
• @piepi By the Linear Factor Test $\ y - a\$ is a factor of a polynomial $f(y)$ iff $f(a) = 0.$ Above is the special case $\,a=-1\,$ and $\,f(y) = y^n+1,\ n\,$ odd. – Bill Dubuque May 5 '16 at 19:47

We have the number $10^{20}+1$. Whenever we have something in this kind of form, we need to find an odd factor of the exponent. In this case $5 \mid 20$, so we can use $5$ as the factor.

Now, we can say $10^{20}+1=(10^4)^5+1$. How does this help us? Well, if we say that $x=10^4$, we have the polynomial $x^5+1$. This polynomial has $-1$ as a zero, meaning $(x+1) \mid (x^5+1)$. Substituting $x=10^4$ back into this statement, we get $(10^4+1) \mid ((10^4)^5+1)=(10^{20}+1)$. Thus, $10^4+1$ is a factor of $10^{20}+1$, so the number is composite.

Notice how the factor had to be odd. Otherwise, if we have an even factor $n$, then $x^n+1$ would not have had $-1$ as a zero. This is a very common technique in math competitions that I have used several times before, so it will come in handy.

• Very smart !, does this works too if for every number with the form $10^n + a$ . "I know that n has to be odd" – DeltaWeb May 5 '16 at 19:55
• It works for $10^n+1$ where $n$ is not a power of $2$ (meaning that $n$ has an odd factor). Also, $10^n-1$ for any integer $n$ is composite because it has $9=3^2$ as a factor. There are also other forms of $10^n+a$ for integers $n, a$ where the number is always composite that can be found by converting the number into some polynomial form. – Noble Mushtak May 5 '16 at 20:00
• @DeltaWeb Also for numbers in the form $10^n-a^n$, and $a^n$ is a perfect $n$th power number. In this case, $n$ can be odd or even, and $a$ can be positive or negative, but $10-a\ne 1$. E.g. $100-9$ is divisible by $7$, and $1000-(-27)$ is divisible by $13$. – peterwhy May 5 '16 at 21:21
• Well and all polynomial are base x numbers. So, interestingly enough... This works for any number raised to a power plus one. – user64742 May 6 '16 at 6:24
• @samhocevar Yes. One can also make the factorization explicit. Then it is clear that the quotient is an integer polynomial as well, and from the alternating nature of it we also see why it works only for an odd exponent. Here it is: $x^5+1=(x+1)(x^4-x^3+x^2-x+1)$. – Jeppe Stig Nielsen May 6 '16 at 10:24

$x^5+1 = (x+1)(x^4 - x^3 + x^2 - x + 1)$ (and this will work for any odd power. replace $x$ with $10^4$

$10^4+1$ divides $10^{20}+1$