How to prove that a very large number is not prime

Solution 1:

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.

Solution 2:

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