Prove that $2^{66}-1$ is not a prime number

Your proof is correct.

Just a little tip - for a problem like this, you don't need to have such a complex proof. It should just suffice to show that $$2^{66}-1=(2^{33}+1)(2^{33}-1)$$ and then show that $$2^{33}+1 \ne 1 \ne 2^{33}-1$$ $$2^{33}+1 \ne 2^{66}-1 \ne 2^{33}-1$$ Which should be fairly simple.

But your proof seems fine to me!

Edit: There's one thing that you missed, as @AndrewD.Hwang pointed out in the comments - you have not actually shown that $2^{66}-1$ can be factored in the way that you decided to use.

But that's okay, it's a quick fix!


Beware: overkill. I hope an interesting overkill.
Let $\omega(n)$ be the number of distinct prime factors of $n$ and $\nu_3(n)=\max\{m\in\mathbb{N}: 3^m\mid n\}$.


$$2^{66}-1 = (2^{33}-1)(2^{33}+1),\qquad \gcd(2^{33}+1,2^{33}-1)=\gcd(2^{33}+1,2)=1 $$ hence $\omega(2^{66}-1) = \omega(2^{33}-1)+\omega(2^{33}+1)$. Additionally $$ 2^{33}-1 = (2^{11}-1)(2^{22}+2^{11}+1),$$ $$ \gcd(2^{22}+2^{11}+1,2^{11}-1)=\gcd(3,2^{11}-1)=1 $$ from which $\omega(2^{33}-1)\geq 2$. In a similar way $$ 2^{33}+1 = (2^{11}+1)(2^{22}-2^{11}+1),$$ $$ \gcd(2^{22}-2^{11}+1,2^{11}+1)=3$$ and since $\nu_3(2^{33}+1)=2$ we also have $\omega(2^{33}+1)\geq 3$ and $$\boxed{ 2^{66}-1\text{ has at least }\color{red}{5}\text{ distinct prime factors}.} $$


Actually $2^{66}-1$ has $8$ distinct prime factors, and the smallest of them, $\{3,7,23, 67,89\}$, are not difficult to recognize. $2,6,22,66$ are divisors of $66$, so $\{3,7,23,67\}$ are prime divisors of $2^{66}-1$ by Fermat's little theorem. $89$ is a divisor since $89\mid(2^{11}-1)\mid(2^{66}-1)$.


Your proof is correct but I have three critiques.

1) You never actually answer the question whether $2^{66} -1$ is prime or not.

Somewhere you need to state that if $n = 2^{33}$ than $2^{66}-1 = n^2 -1$ which isn't prime. Yes, it's obvious. But you never actually indicated how what you were proving applies to the question at hand.

(I know... it was obvious and was abundantly clear to you.... but nonetheless, it should be stated.)

2) Adding the variables $a,b,c$ simply obfuscates.

It's more direct to simply say $n^2 - 1 = (n+1)(n-1)$. So if $n+1$ and $n-1$ are natural number other than $1$ (i.e. $n > 2$) then $(n+1)(n-1) = n^2 -1$ is composite and not prime.

3) You don't actually have to state or prove that $x^2 - 1$ is not prime for $x > 2$. It's enough to use it as a hint.

The proof can be done in one sentence:

$2^{66} = (2^{33} + 1)(2^{33} -1)$ so $2^{66} -1$ has factors other than itself and $1$ so it is not prime. QED.