The following example shows a primetest for Mersenne numbers.
It's based on two theorems:
1) The largest prime devider of a number n is $\lfloor\sqrt{n} \rfloor$.
2) Divisor of $M_{17}$ for example are of the form $2*17k+1$.
Example:
Why do we only have to check the divisors of the form $2*13k+1$ less than $\lfloor\sqrt{n}\rfloor$ that are prime?