# Thread: Show there are infinitely many primes in A.

1. ## Show there are infinitely many primes in A.

Let A = {1, 4, 7, 10, 13, 16, ...} the set of all positive integers congruent to 1 (mod 3). Show that there are infinitely many primes in A. [Note: the number 1 is never a prime in any such set A.]

2. ## Re: Show there are infinitely many primes in A.

Hey azollner95.

Can you show us what you have tried?

3. ## Re: Show there are infinitely many primes in A.

Originally Posted by azollner95
Let A = {1, 4, 7, 10, 13, 16, ...} the set of all positive integers congruent to 1 (mod 3). Show that there are infinitely many primes in A. [Note: the number 1 is never a prime in any such set A.]
Assume contrary. Let *p_m* be the largest prime in *A*. Define *q=p_1p_2 \cdot p_m +6*, then *q* is not divided by *p_1,p_2, \cdot p_m*. We can write *q* as *q=3k+1+6=3(k+2)+1 \in A*.
So *q* is another prime in A larger than *p_m*.

4. ## Re: Show there are infinitely many primes in A.

wps,

Your proof is incomplete. Why is q a prime? The problem is a special case of Dirichlet's theorem. https://en.wikipedia.org/wiki/Dirich...c_progressions This is a very old result, but the proof is really advanced number theory. Special cases can be easily proved with a Euclidean type proof. For example: there are infinitely many primes congruent to 2 mod 3.

Suppose there are only finitely many primes congruent to 2 mod 3, say $p_1,p_2,\cdots,p_n$. Let $N=p_1^2p_2^2\cdots p_n^2+1$. Then N is congruent to 2 mod 3. Not every prime divisor of N is 1 mod 3 (since otherwise N would be 1 mod 3). So there is a prime divisor of N which is 2 mod 3. This prime divisor then must be one of the $p_i$, but this is impossible since N is prime to all of the $p_i$.

I don't see how to give an elementary proof for the OP's question. I would like to see such if you or any one can do it.

5. ## Re: Show there are infinitely many primes in A.

johng, I am following along with your logic for 2 mod 3 for the most part. Since I am attempting to show this logic for 1 mod 3, could I just use this sort of "contradiction" and say that since it is impossible of N to be 1 mod 3, then thus there are infinitely many primes?

6. ## Re: Show there are infinitely many primes in A.

I've thought about this, but I just don't see a way to modify the "Euclidean" argument. There may well be such, but I'm not seeing it.

7. ## Re: Show there are infinitely many primes in A.

johng, is there a way that I could use the Euclidean argument to get me my answer, or at least close to it?