Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
In my discrete math book, I was tasked with finding a counterexample for this:
If $n$ is prime, then $2^n-1$ is prime.
Does there exist a counterexample for such a statement? Also, am I wrong in thinking that when something asks for a counterexample, is it looking for some logic that proves the original statement to be false?
Any help is appreciated, as I've got a test on subjects like this tomorrow.
A counter-example is one instance in which the statement does not hold to be true. Let n=11. $2^{11} - 1$ is a composite number.
$2^{11}-1=2047 = 23 \cdot 89$
$2^n-1\in\mathbb P\implies n\in\mathbb P$
This is true because if $n\not\in\mathbb P$, then $n=kl$ for some $k,l\in\mathbb Z_{\ge 2}$ and so
$$2^n-1=2^{kl}-1=(2^k-1)(2^{kl-k}+2^{kl-k-1}+\cdots +1)$$
And this is composite, since both $2^k-1$ and $2^{kl-k}+2^{kl-k-1}+\cdots +1$ are integers larger than $1$.
Primes of the form $2^n-1$ are called Mersenne primes. It is not known whether there are infinitely many of them.
The implication is not true the other way around.
I.e., $n\in\mathbb P\not\implies 2^n-1\in\mathbb P$
The smallest counterexample is $n=11$.
If $n=11$, then $n\in\mathbb P$, but $2^{11}-1=23\cdot 89\not\in\mathbb P$.
The statement says $2^n-1$ is prime for all primes $n$. A counterexample would be a prime number $n$ such that $2^n-1$ is not prime.
No, it's not. Among the first twenty thousand primes $p$, only thirty-one of them give primes when plugged into the formula $2^p - 1$. In fact, you could have your computer give you a pseudorandom prime number $p < 10^7$ and I would wager you \$100 that $2^p - 1$ is composite.
For a counterexample, at least the ones that are easy to find, you don't really need logic, you just need a single example to counter the assertion. Try $$\frac{2^{23} - 1}{47}.$$ But like I suggested, there are plenty more where those came from, see Sloane's A054723.
The primes $p$ that do give prime $2^p - 1$ are sometimes called "Mersenne primes" (though some use the term for the prime $2^p - 1$ rather than for $p$, calling that a "Mersenne exponent") after a medieval French math amateur who correctly identified some and incorrectly identified others.
Without computers, it was very tough going finding Mersenne primes. Barely a dozen of them were known prior to World War II. But even with our fancy computers, we know less than fifty of them, see http://www.mersenne.org/primes/ for a lot more info than I can give here.
Here's a related question for which you do need logic: prove that if $n$ is composite, then $2^n - 1$ is also composite.
That's false. But if it makes you feel any better, you're making a mistake very similar to Fermat's. In 1650, Fermat conjectured that all numbers of the form $2^{2^n} + 1$ are prime. They didn't have computers back then, so it was very difficult to find that $2^{2^5} + 1 = 641 \times 6700417$.
But back then it was easier to find that $2^{11} - 1 = 23 \times 89$. That's just one counterexample to the assertion that $2^n - 1$ is prime whenever $n$ is prime; in fact, most prime $n$ lead to composite $2^n - 1$. A few more counterexamples: $n = 23, 29, 37, 41, 43, 47, 53, 59, 67, 71, 73, 79, 83, 97$. These are getting a little too large to test by hand. In fact, Marin Mersenne also made some mistakes: for example, he said $2^{67} - 1$ is prime when it is in fact composite, and he skipped over $2^{61} - 1$, which is prime (or maybe his "1" looked like a "7"?--he made other mistakes, though).
When "something asks for a counterexample," you just need to produce one example to show the assertion is wrong. But "some logic that proves the original statement to be false" can be very helpful, especially when the first counterexample is quite large and not readily accessible to manual computation, or for some reason not immediately obvious.
