Prove that $2^{66}-1$ is not a prime number I just started studying Discrete Mathematics and one of the exercises asks to prove that:
$$2^{66} - 1 \textrm{ is not a prime number}$$
The author suggests to use the well know relation: 
$$x^2 - 1 = (x + 1)(x - 1)$$
My proof goes as such (please forgive me — and do correct me — if I use any wrong symbol or term). Let's define the set $X$ as:
$$X=\{n\in\mathbb{N}\;|\;n>2\}$$
$\forall x\in X$ we define two numbers:
$$\begin{align}a & = x+1\\ b & = x-1\end{align}$$
Because $x>2$, then $a>1$ and $b>1$. Therefore we have
$$c=a\cdot b$$
which cannot be a prime number, because:
$$\frac{c}{a}=b \quad \textrm{or} \quad \frac{c}{b}={a}$$
This, in my view, is the proof of the theorem. 
Could you please let me know if my proof is correct, or if not, how do I prove the theorem?
Thank you very much!
Valerio
Edit: As cited in the comments/answers below, I didn't show the factorisation, so here we go:
$$2^{66}-1=(2^{33}+1)(2^{33}-1)$$
Now I understand I didn't need to use all the steps above, but I was trying to give a general proof, not just for the specific case.
Anyway, thank you all for your answers and showing interest in my question. I didn't expect it to create so much debate! :-)
 A: 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)$.
A: 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.
A: I'm surprised that there hasn't been a single mention of the term "Mersenne prime" or at least "Mersenne number" in the answers so far. I admit that aside from that detail, the answer I'm going to give is hardly different from the others.
It is a well-known fact that if $2^n - 1$ is prime (a Mersenne prime), then $n$ must itself be prime. And it is also well known that if $n$ is prime, then $2^n - 1$ is not necessarily prime.
In fact, it's much more likely to be composite. $2^{74207281} - 1$ is believed to be the $49$th Mersenne prime, and $74207281$ is itself the $4350601$st prime overall. Suppose they find a hundred Mersenne prime exponents between $37156667$ and $74207281$. That's unlikely, but it would still mean that less than $1\%$ of primes up to $74207281$ are Mersenne prime exponents.
The fact that composite $n$ means $2^n - 1$ is also composite has been known since before Marin Mersenne's time. To use the hint that was given to you, note that $$2^{2m} = (2^m)^2.$$ Since $66 = 2 \times 33$, it follows that $$2^{66} - 1 = (2^{33} - 1)(2^{33} + 1).$$ Clearly $1 < 2^{33} - 1 < 2^{33} + 1 < 2^{66} - 1$, meaning that $2^{66} - 1$ is divisible by positive integers other than $1$ and itself.
A: 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!
A: Hint:
Start with let $2^{66}-1$, Then factor it as follows:
$$2^{66}-1=(2^{33})^2-1=(2^{33}+1)(2^{33}-1).$$
Now proceed from here.
