# How to prove that $10^{3n}+1$ is not a prime number?

Show that the number 100...01, that include $3n-1$ zeros ($n\in N$) is not a prime number.

I found out that I could say $10^{3n}+1$ is the same as the requested proof but I don't know how to continue.

As you probably know, you simply need to factor the number in question to show its composite-ness.

In this case, there is a nice little factoring formula for two cubic numbers added together: $$a^3+b^3=(a + b)(a^2 - ab + b^2)$$ Thus: $$10^{3n}+1=(10^n+1)(10^{2n}-10^n + 1).$$ Therefore, both $10^n+1$ and $10^{2n}-10^n+1$ divide $10^{3n}+1$.

Additionally we must show that these two numbers are not $1$ or $10^{3n}+1$ itself, but I will leave this task to you.

• Simple and effective. +1 – Cornman Nov 7 '17 at 15:38
• Clean! +1 $\,$ – Zubin Mukerjee Nov 7 '17 at 18:56

Express the number as $(10^n)^3 + 1^3$. Now the formula for $a^3+b^3$ gives a factorization showing that this number is not a prime number (of course you have to check none the terms in the factorization is $1$).

For odd $n$ it is easy to see, that $11|10^{3n}+1$ because of the alternating checksum, which is equal to $0$.

For even $n$ it is n=2m for natural $m\geq 1$ and we get:

$10^{6m}+1=10^{6m}-10^{4m}+10^{2m}+10^{4m}-10^{2m}+1=(10^{2m}+1)(10^{4m}-10^{2m}+1)$