Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
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
1  
@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
1  
@Kaish, $p \equiv \pm 1 \pmod{5}$, so $p \ne 5$. –  Andreas Caranti Apr 26 '13 at 19:03
1  
@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$).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.