1
$\begingroup$

While trying to solve answer a question, I discovered one that I felt to be remarkably similar. The question I found is 'Argue that there are infinitely many primes $p$ that ar enot congruent to $1$ modulo $5$. I believe this has been proven. (brief summary of this proof follows).

Following the Euclid Proof that there are an infinite number of primes.
First, Assume that there are a finite number of primes not congruent to $1 \pmod 5$.
I then multiply them all except $2$ together to get $N \equiv 0 \pmod 5$.
Considering 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$.
This is because the product of primes $\equiv 1 \pmod 5$ is still $\equiv 1 \pmod 5$.

I can't take credit for much of any of the above proof, because nearly all of it came from \href {http://math.stackexchange.com/questions/231534/infinitely-many-primes-p-that-are-not-congruent-to-1-mod-5}${\text {Ross Millikan}}$. Either way I'm trying to use this proof to answer the following question. I'm having a very difficult time doing so.


My question:

I wish to prove that there are infinitely many primes p which are not congruent to $-1$ modulo $19$.

  • 0
    a) Euclid's proof is not by contradiction; he did not assume that there are finitely many primes; he showed that given any finite set of primes there must be a further prime. b) Could you say more specifically where you see an obstacle to applying the method you describe to this case?2012-11-10

1 Answers 1

2

Let $p_1,p_2,\dots,p_n$ be any collection of odd primes, and let $n=19p_1p_2\cdots p_n+2$. A prime divisor of $n$ cannot be one of the $p_i$. And $n$ has at least one prime divisor which is not congruent to $-1$ modulo $19$, else we would have $n\equiv \pm 1\pmod{19}$.

Remark: Not congruent is generally far easier to deal with than congruent.