An abstract algebraic proof that if for some positive integer $n$, $2^n - 1$ is prime, then so is $n$. I was wondering if there exists a proof from abstract algebra of this theorem. It seems like there should be. In fact, I've tried to come up with one and it always seems I'm coming close, but I can't do it.
Could you provide one?
 A: If $n$ is not prime, then $2^n - 1$ is not prime.
Suppose that $n = ab$ for integers $a,b\geq2$.  Then note that we can factor
$$
x^n - 1 = (x^a)^b - 1 = (x^a - 1)([\text{stuff}])
$$
which means that
$$
2^n - 1 = (2^a)^b - 1 = (2^a - 1)([\text{stuff}])
$$
where stuff is, notably, an integer and bigger than $1$. It follows that $2^n-1$ is not prime.
A: Hint $\,\ a^{\large k}\!-\!1\mid a^{\large kn}\!-\!1\ $ by $\ {\rm mod}\,\ \color{#c00}{a^{\large k}\!-\!1}\!:\,\  a^{\large kn}\equiv \overbrace{(\color{#c00}{a^{\large  k}})^{\large n}\equiv \color{#c00}1^{\large n}}^{\Large (\color{#c00}{a^k\,\ \equiv\,\ 1})^{\Large n}}\equiv 1\,$ by Congruence Rules.
This is a special case of the Factor Theorem $\ b\!-\!1\mid f(b)-f(1)\,$ for $\,f(x)\,$ an integer coef polynomial, since, like above $\ {\rm mod}\,\ b\!-\!1\!:\,\ \color{#c00}{b\equiv 1}\,\Rightarrow\, f(\color{#c00}b)\equiv f(\color{#c00}1).\, $ In the OP $\ f = x^{\large n},\ \ b = a^{\large k}.\ $ The prior implication is a special case of one of the linked Congruence Rules, namely the Polynomial Congruence Rule. whereas the OP is simply the special case when the polynomial is a power $\,f(x) = x^n\,$ (Power Congruence Rule) - clear from the overbraced powering in the proof. 
Thus the proof follows very naturally from the viewpoint of modular arithmetic or congruences. They have the advantage that one doesn't need to compute any quotients (only remainders, or congruent numbers), which greatly simplifies many proofs.
Remark $\ $ One can prove further that $\, (a^{\large k}\!-\!1,a^{\large j}\!-\!1) = a^{\large (k,j)}\!-\!1\,$ where $\,(x,y):=\gcd(x,y).\,$ This is a special case of a strong divisibility sequence.
