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? 
 A: One way to prove the existence of something is to exhibit an example.  That is what your text is doing by saying $2^{11}-1$ is composite.  There are many more examples of primes $p$ such that $2^p-1$ is composite, but I don't know an easy way to prove there is one besides trial.  It is not the case that you need the "right" definition of primes to prove this.  For composites you have the theorem that if $c=ab, 2^a-1$ divides $2^c-1$.
A: You can't define a prime number so you won't have to rely on trial and error, since there are prime numbers $p$ for which $2^p-1$ is prime. 
Well, unless you are willing to accept a definition of prime number which excludes $2$ and $3$ and $5$ and $7$ and several other numbers that are prime by the usual definition. 
A: The fact that $2^{11}-1$ is not prime is not quite an accident. Let $p$ be a prime of the form $4k+3$, and suppose that $q=2p+1$ is prime. Then $q$ is a divisor of $2^p-1$. In particular, $11$ is a prime of the form $4k+3$, and $2(11)+1$  is prime, so $23$ divides $2^{11}-1$.
We prove the general result. First note that $2$ is a quadratic residue of the prime $q$. This is because in fact $2$ is a quadratic residue of any prime of the form $8k\pm 1$, and $q$ is of the form $8k-1$. 
By Euler's Criterion, it follows that $2^p\equiv 1\pmod{q}$, that is, $q$ divides $2^p-1$. 
Note that $23$ is of the form $4k+3$ and $2(23)+1$ is prime. So we can also conclude that $47$ divides the Mersenne number $2^{23}-1$.   
