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? 

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$.
