Is a counterexample considered a rigorous proof that a property is not true? This is my follow-up question to my own query earlier:

How can I algebraically prove that $2^n - 1$ is not always prime?

Almost half of the answers said that I provided my own proof by giving the counterexample. Although, I was not satisfied through those answers since they didn't provide a complete view of the situation and how there exist algebraic factors.
Is disproving an algebraic statement necessarily the same as introducing a case where it is not true? I agree with Nameless's statement found here, but I am not sure as to how that contributes to a rigorous algebraic  proof.
Remark: I agree that I didn't ask for an algebraic proof earlier, but I did expect a better proof.
 A: Generally statements of the form "$2^n-1$ is always a prime" are translated to "$\forall n\in\mathbb N: 2^n-1$ is a prime".
To show that a statement of the form $\forall x\varphi(x)$ is false it is enough to show one counterexample. That is we prove the negation of the statement, which translates to $\exists x\lnot\varphi(x)$. To prove that there is some number with property $\lnot\varphi(x)$ it is enough to exhibit one which does.
A: To show that a statement about all objects of a certain kind is not true, it suffices to give a counter-example. For example, to show that all boys have names John is not true, it suffices to show that there is a boy named Jack.
A: I'd like to add a small remark to the other (excellent) answers, because it touches on what I think is the source of your discomfort with the proof by counterexample. As already noted, the negation of a universally quantified formula is logically equivalent to the existentially quantified negated formula.
And explicitly providing an example is one way to prove an existential statement. (So the following is not specific to counterexamples.) 
The key point here is that for this it is not enough to just give an object ("$n=4$"), but one needs to prove that this object indeed has the desired properties ("Then $2 ^4-1 = 15$ is not prime, since it is divisible by $3$"). The elementary nature of this concrete example (and some of the language used when talking about a proof by (counter)example) can hide this, but it is what makes it a proof (and can in fact be quite involved). 
(And if I am allowed to give some advice: If asked for an example - especially on a test, - never just state one, but always explain why it is one, even if it just takes a half-sentence.)
A: As I said before, a counterexample is enough to disprove a statement. This is because of the equivalency 
$$\neg (\forall n\in \mathbb{N})(2^n-1\in \mathbb{P})\iff (\exists n\in \mathbb{N})\neg (2^n-1\in \mathbb{P})\iff (\exists n\in \mathbb{N})(2^n-1\notin \mathbb{P})$$
Now, if you had asked "when is $2^n-1$ prime" things would be very different
A: The statements that are relevant here are called universal statements (because they involve a universal quantifier). These are the statements of the form "for all foos, statement(foo) is true." Many things you will be asked to prove in mathematics are universal statements, but we are also interested in non-universal statements. 
The negation of a universal statement is an existential statement (because it involves an existential quantifier). More precisely, the negation of the universal statement "for all foos, statement(foo) is true" is the existential statement "there exists a foo such that statement(foo) is false."
Disproving a universal statement means proving its negation, which is an existential statement. To prove an existential statement, it is sufficient to provide a single example. This is more or less what an existential statement means. That is, if I want to prove that there exists a foo such that statement(foo) is false, all I have to do is find one and show it to you. 
A: Yes, a single counterexample is a rigorous proof that an assertion is false. One can often say more, of course: it might be possible, for instance, to exhibit a whole class of counterexamples, or even to show exactly when the assertion is true and when it’s false. It might be possible to show that if the hypotheses are strengthened slightly, the assertion is true. But all it takes to refute the assertion is one counterexample.
A: As an addendum to the other answers, I wanted to point out that theorems of the form

If $P(x)$, then $Q(x)$

are usually implicit universal assertions of the sort “for all $x$, if $P(x)$, then $Q(x)$”.
So, to prove an implication is not a theorem, it suffices to find a counter-example: a single object $x$ for which “if $P(x)$ then $Q(x)$” is not true, which is equivalent to saying that “$P(x)$ is true but $Q(x)$ is false”.
