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.]
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.
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?