# Show that there are infinitely many primes which are $\pm 1 \mod 5$

Show that there are infinitely many primes which are $\pm 1 \mod 5$.

HINT: Suppose that there are finitely many such primes, and let these primes be $q_i$ for $1 \leq i \leq n$. Let

$$N = \prod_{i = 1}^nq_i$$ and let $p$ be any primes dividing $N^2 - 5$. Show that $p \equiv \pm 1 \mod 5$, using question $3$ or otherwise, and that $p \neq q_i$ for any $1 \leq i \leq n$.

Question $3$ was show that (Legendre Symbol) $\left( \frac{5}{p} \right)= 1$ if and only if $p \equiv \pm 1 \pmod 5$ (which I have done).

What I have done for this question is that I said

$$p \mid N^2 - 5 \implies N^2 - 5 \equiv 0 \pmod p \implies N^2 \equiv 5 \pmod p.$$

Now I'm stuck on what to do as $5$ isn't a square number and so $N^2 \equiv 5 \mod p$ isn't a quadratic residue and so I can't use question $3$ to help.

Can someone help show that there are infintely many primes which are $\pm 1 \mod 5$ please.

-

Let $p$ be a prime dividing $N^{2} - 5$. Thus $N^{2} \equiv 5 \pmod{p}$, so by the very definition $5$ is a quadratic residue modulo $p$, so $p \equiv \pm 1 \pmod{5}$.

If $p = q_{i}$ for some $i$, then $p$ divides $N$, and since $p$ divides $N^2 - 5$, we have that $p$ divides $5$, a contradiction.

-
Ok, I'm slightly confused on the definition of a quadratic residue. I have written down that $n$ is a quadratic residue $\mod p$ if $n \equiv x^2 \mod p$, for some $x$ coprime with $p$. Is this the same thing? – Kaish Apr 26 '13 at 18:53
@Kaish, looks ok, so $5 \equiv N^{2} \pmod{p}$ fits in. – Andreas Caranti Apr 26 '13 at 18:58
Also, why is $p$ dividing $5$ a contradiction? – Kaish Apr 26 '13 at 19:02
@Kaish, $p \equiv \pm 1 \pmod{5}$, so $p \ne 5$. – Andreas Caranti Apr 26 '13 at 19:03
@Kaish, yes, it divides $N$, thus $N^{2}$, and it divides and $N^{2} - 5$, so it divides $5 = N^{2} - (N^{2} - 5)$. – Andreas Caranti Apr 26 '13 at 19:40

This is another way that I quite like. Let $n$ be an integer and $p$ a prime that divides $n^2+n-1$, then either $p = 5$ or $p \equiv \pm 1$ ($\bmod$ $5$). Indeed a root of $X^2-nX+1$ ($\bmod$ $p$) is either $1$ (in which case $p=5$) or a primitive fifth root of unity and in the latter case $5\mid p^2-1$.

It is not difficult to show that there are in fact infinitely many $p$ equal to $-1$ ($\bmod$ $5$) by considering only $n$ that are $0$ or $4$ ($\bmod$ $5$).

-