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

  • $\begingroup$ 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? $\endgroup$ – joriki Nov 10 '12 at 6:11

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.