Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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:… – 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
up vote 8 down vote accepted

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$$

share|cite|improve this answer
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.$

share|cite|improve this answer
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

Your Answer


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.