2
$\begingroup$

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.

  • 0
    @lhf Wow. That was foolish of me. Thank's for pointing that out.2012-11-06

2 Answers 2

8

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

  • 0
    @BillDubuque: is this what you were thinking?2012-11-06
1

Hint $\rm\ \ 5n^2\!-n\: $ has a larger set of prime factors $\rm\not\equiv 1\ mod\ 5\:$ than does $\rm\:n.$

  • 0
    This uses $\rm\:5n\!-\!1\:$ (vs. Ross' $\rm\:5n\!+\!2)\:$ to get a new prime $\rm\not\equiv 1\pmod 5\ \ $2012-11-06