Results 1 to 7 of 7
Like Tree6Thanks
  • 1 Post By chiro
  • 1 Post By wps
  • 3 Post By johng
  • 1 Post By johng

Thread: Show there are infinitely many primes in A.

  1. #1
    Member
    Joined
    Feb 2017
    From
    N/A
    Posts
    91

    Exclamation 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.]
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    6,577
    Thanks
    1711

    Re: Show there are infinitely many primes in A.

    Hey azollner95.

    Can you show us what you have tried?
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    wps
    wps is offline
    Newbie
    Joined
    Feb 2017
    From
    Earth
    Posts
    9
    Thanks
    2

    Re: Show there are infinitely many primes in A.

    Quote Originally Posted by azollner95 View Post
    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*.
    Thanks from azollner95
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    1,118
    Thanks
    467

    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.
    Thanks from wps, topsquark and azollner95
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Feb 2017
    From
    N/A
    Posts
    91

    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    1,118
    Thanks
    467

    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.
    Thanks from Plato
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Feb 2017
    From
    N/A
    Posts
    91

    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?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Infinitely many primes in Q[Sqrt(d)]
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: Oct 13th 2010, 09:52 AM
  2. Infinitely many primes
    Posted in the Number Theory Forum
    Replies: 11
    Last Post: Jun 4th 2010, 06:43 AM
  3. infinitely many primes of the form 6k + 5 and 6K + 1
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Oct 22nd 2009, 06:25 AM
  4. Infinitely Many Primes
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Jun 24th 2009, 07:12 PM
  5. infinitely many primes
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: Nov 18th 2008, 08:07 AM

/mathhelpforum @mathhelpforum