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.

  • 6
    Surely $11 \equiv 1 \bmod{5}$.2012-11-06
  • 1
    Maybe this is like using a steam-hammer to crack nuts, but you can derive it from this theorem: http://en.wikipedia.org/wiki/Dirichlet%27s_theorem_on_arithmetic_progressions2012-11-06
  • 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
    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$.2012-11-06
  • 0
    @fretty I second that. I don't immediately see how to deal with 2 and 3.2012-11-06
  • 0
    You would have to show that this number is not a perfect power of the number you added.2012-11-06
  • 0
    @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?2012-11-06
  • 0
    I think there is also a problem with this number being divisible by $5$.2012-11-06
  • 0
    @Dan Shved: That is not a problem, the contradiction comes from $p_i |2$ or $p_i|3$ for some $i$. You thus have to show that the constructed number is NOT JUST divisible by such a prime.2012-11-06
  • 0
    My advice is to prove something stronger using Ross' advice. Prove that there are infinitely many primes congruent to $4 \bmod 5$.2012-11-06
  • 0
    @fretty Could you expand on that (about powers of 2)? I took the product $N$ of all the primes who are not congruent to 1 (mod 5). Now I am looking at the number $N+2$, which is congruent to 2 (mod 5). Then I should look at the prime factors of $N+2$. And what do I do about them, how do I proceed?2012-11-06
  • 0
    Well the way the usual proof goes is that you want there to exist a prime factor of N+2 that is not $1 \bmod 5$, then it must be one of the primes on your finite list and so divides $2$. The "and so it divides 2" bit is usually the contradiction but here your prime could actually be 2 for all you know!2012-11-06
  • 0
    Oh but I have been silly because we may assume N+2 to be odd!2012-11-06
  • 0
    It's actually even.2012-11-06
  • 1
    Well we can discard the prime $2$ and consider only odd primes, it doesn't change the outcome of the theorem.2012-11-06
  • 0
    @fretty OK, that seems to work.2012-11-06
  • 0
    @fretty: right you are. I have updated it.2012-11-06
  • 0
    $N+2$ might actually be $1$ ($\bmod$ $5$).2012-11-06
  • 0
    @WimC: no, because $N \equiv 0 \pmod 5$ as 5 is a prime.2012-11-06
  • 0
    @RossMillikan: fair enough.2012-11-06
  • 0
    @Ross I think you should add further details to the proof. I cannot tell which way you intend it to be completed.2012-11-06
  • 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