2
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Feb 22, 2015 at 4:43
  • $\begingroup$ 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. $\endgroup$
    – Nolohice
    Feb 22, 2015 at 4:45
  • 2
    $\begingroup$ Mmm, it's not about the way you define them rather than what you know about them. Right? $\endgroup$ Feb 22, 2015 at 4:53
  • $\begingroup$ I understand what you want but am not sure if there is any way to concretely define a prime that achieves the same result as how we might define even and odd numbers for proofs...In the same way that defining a rational as $\frac{p}{q}$ for some $p,q$ \in mathbb{Z}$ allows us to prove that $sqrt{2}$ is irrational very easily. I don't think its exactly what you want, but using the fact that every number is either prime or the product of primes can be incredibly powerful for many problems you'll likely encounter. I'm afraid that tidbit doesn't match this particular problem, however. $\endgroup$
    – 123
    Feb 22, 2015 at 4:54

3 Answers 3

2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .