26
$\begingroup$

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 .

$\endgroup$
13
  • 4
    $\begingroup$ Which is it? $10^{20}+1$ or $10^{21}+1$? $\endgroup$
    – almagest
    May 5, 2016 at 19:23
  • 2
    $\begingroup$ Looks like $10^{21}+1$, divisible by $11$. $\endgroup$
    – André Nicolas
    May 5, 2016 at 19:24
  • 3
    $\begingroup$ $10^{20}+1$ has the factor $10001$, $10^{21}+1$ is even easier it has many factors (including $7,11,13$). $\endgroup$
    – almagest
    May 5, 2016 at 19:25
  • 4
    $\begingroup$ 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$. $\endgroup$
    – peterwhy
    May 5, 2016 at 19:28
  • 4
    $\begingroup$ @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. $\endgroup$
    – Bill Dubuque
    May 5, 2016 at 19:47

2 Answers 2

Reset to default
57
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ Very smart !, does this works too if for every number with the form $10^n + a$ . "I know that n has to be odd" $\endgroup$
    – DeltaWeb
    May 5, 2016 at 19:55
  • $\begingroup$ 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. $\endgroup$
    – Noble Mushtak
    May 5, 2016 at 20:00
  • $\begingroup$ @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$. $\endgroup$
    – peterwhy
    May 5, 2016 at 21:21
  • $\begingroup$ The case where this does not work, when $10^n+1$ has an exponent $n=2^m$, is called a generalized Fermat number (GFN) of base 10. Here it is not known if infinitely many such numbers are prime (it is conjectured that only $11$ ($2^m=2^0$) and $101$ ($2^m=2^1$) are primes). The page GFN10 factoring status lists known factors of these numbers. The notation $F_m(10) = 10^{2^m}+1$ is used there. See also Wikipedia: Fermat number § Generalized Fermat numbers. $\endgroup$
    – Jeppe Stig Nielsen
    May 6, 2016 at 9:02
  • 2
    $\begingroup$ @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)$. $\endgroup$
    – Jeppe Stig Nielsen
    May 6, 2016 at 10:24
5
$\begingroup$

$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$

$\endgroup$

You must log in to answer this question.

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