Proof that there are infinitely many prime numbers of the form $3k+1$.
Solution 1:
The usual proof of this uses the fact that any prime dividing a number of the form $f(n)=n^2+n+1$ has to be congruent to $0$ or $1$ modulo $3$. If $p\mid f(n)$ and $p\ne3$ then $n^3\equiv1\pmod p$ but $n\not\equiv1\pmod p$. This will contradict Lagrange's theorem applied to the multiplicative group $\Bbb F_p^\times$ of integers not divisible by $p$ modulo $p$.
Now do the usual trick of considering the prime factorisation of $f(n)$ when $n$ has a lot of prime factors you want to avoid.