# Prove the existence of a prime $p$ such that $2^p -1$ is composite, without trial and error

In my discrete mathematics book under existence proofs it has

Prove that there exists a prime $p$ such that $2^p -1$ is composite.

It then goes on to say by trial and error we find $2^{11}-1$ proves the statement

For even numbers we have some integer $n$ is even if it is twice the product of an integer, $n = 2k$. Similarly for odd numbers $m$ is odd if $m = 2b+1$, but how would I go about defining a prime number so that I wouldn't have to rely on trial and error to prove the above statement?

How would I mathematically define its negation?

• I don't understand, you want to think of a way of proving certain theorems or propositions, such as the last one, without relying on trial and error? Or you want to know how to define prime numbers? Feb 22, 2015 at 4:43
• The intersection of what you just said. I want to know how to define prime numbers so that in this case I wouldn't have to rely on trial and error. Feb 22, 2015 at 4:45
• Mmm, it's not about the way you define them rather than what you know about them. Right? Feb 22, 2015 at 4:53