# Infinitely many primes p that are not congruent to 1 mod 5

Argue that there are infinitely many primes p that are not congruent to 1 modulo 5.

I find this confusing. Is this saying $p_n \not\equiv 1 \pmod{5}$?

To start off I tried some examples.

$3 \not\equiv 1 \pmod{5}$

$5 \not\equiv 1 \pmod{5}$

$7 \not\equiv 1 \pmod{5}$

$11 \equiv 1 \pmod{5}$

$13 \not\equiv 1 \pmod{5}$

$17 \not\equiv 1 \pmod{5}$...

If this is what the question is asking i've come to the conclusion that this is true. Either way, i've got no clue how to write this as a proof.

-
Surely $11 \equiv 1 \bmod{5}$. – lhf Nov 6 '12 at 18:43
Maybe this is like using a steam-hammer to crack nuts, but you can derive it from this theorem: en.wikipedia.org/wiki/… – Dan Shved Nov 6 '12 at 18:51
@lhf Wow. That was foolish of me. Thank's for pointing that out. – maroon.elephants Nov 6 '12 at 18:53

You can follow the Euclid proof that there are an infinite number of primes. Assume there are a finite number of primes not congruent to $1 \pmod 5$. Multiply them all except $2$ together to get $N \equiv 0 \pmod 5$. Consider the factors of $N+2$, which is odd and $\equiv 2 \pmod 5$. It cannot be divisible by any prime on the list, as it has remainder $2$ when divided by them. If it is prime, we have exhibited a prime $\not \equiv 1 \pmod 5$ that is not on the list. If it is not prime, it must have a factor that is $\not \equiv 1 \pmod 5$ because the product of primes $\equiv 1 \pmod 5$ is still $\equiv 1 \pmod 5$$- I don't think you can get away easily by adding$2$or$3$because they ARE divisible by primes that are not$1 \bmod 5$. – fretty Nov 6 '12 at 18:52 @fretty I second that. I don't immediately see how to deal with 2 and 3. – Dan Shved Nov 6 '12 at 18:53 You would have to show that this number is not a perfect power of the number you added. – fretty Nov 6 '12 at 18:55 @fretty still don't see how this is enough. What if it is a product of the number I added and several other primes that are 1 mod 5? – Dan Shved Nov 6 '12 at 18:57 Well we can discard the prime$2$and consider only odd primes, it doesn't change the outcome of the theorem. – fretty Nov 6 '12 at 19:09 Hint$\rm\ \ 5n^2\!-n\: $has a larger set of prime factors$\rm\not\equiv 1\ mod\ 5\:$than does$\rm\:n.$- This uses$\rm\:5n\!-\!1\:$(vs. Ross'$\rm\:5n\!+\!2)\:$to get a new prime$\rm\not\equiv 1\pmod 5\ \ \$ – Bill Dubuque Nov 6 '12 at 23:07