Results 1 to 9 of 9

Math Help - infinite primes

  1. #1
    Junior Member
    Joined
    Oct 2007
    Posts
    37
    Awards
    1

    infinite primes

    Prove that there are infinitely many primes of the form 6x-1.

    I have been fighting this proof for an hour. I have no idea how to get started or on how to finish. Any help would be greatly appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Aryth's Avatar
    Joined
    Feb 2007
    From
    USA
    Posts
    651
    Thanks
    1
    Awards
    1
    All integers can be represented as:

    n = 6k + m

    Where:

    m \in \{0,1,2,3,4,5\} and

    k \in \mathbb{Z}

    Now, first we try to find the statements for which this is seemingly prime:

    \text{For } m = 0

    n = 6k

    It's immediately clear that this is divisible by 6.

    \text{For } m = 1

    n = 6k + 1

    This has no immediate factors, MAY be prime.

    \text{For } m = 2

    n = 6k + 2 = 2(3k + 1)

    It is immediately clear that it is divisible by two.

    \text{For } m = 3

    n = 6k + 3 = 3(2k + 1)

    It is immediately clear that it is divisible by three.

    \text{For } m = 4

    n = 6k + 4 = 2(3k + 2)

    Immediately clear that it is divisible by two.

    \text{For } m = 5

    n = 6k + 5

    It has no immediate factors. MAY be prime.

    The only candidates for primacy are:

    q = 6k + 1

    Or

    p = 6k + 5

    But, 6k + 5 = 6m - 1 for m = k + 1

    Therefore, all integers that are candidates for primacy are:

    p = 6n \pm 1

    Since it has already been proven that there are infinitely many primes, then there are also infinitely many primes represented by each:

    q = 6n + 1

    and

    p = 6n - 1

    Thus, there are infinitely many primes represented by p = 6x - 1

    Q.E.D.

    I know it may not be as good as you need. But you can use it to build your own proof if you would like.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote Originally Posted by Aryth View Post
    Therefore, all integers that are candidates for primacy are:

    p = 6n \pm 1

    Since it has already been proven that there are infinitely many primes, then there are also infinitely many primes represented by each:

    q = 6n + 1

    and

    p = 6n - 1

    Thus, there are infinitely many primes represented by p = 6x - 1

    Q.E.D.
    Excuse me, but this part is wrong, you have not shown that there are infinitely many primes of the form p=6k-1. Maybe there are infinetely many prime numbers of the form p=6k+1 and a finite number of primes of the form p=6k-1

    Indeed, suppose there's a finite number of primes of the form p=6l-1, let a_1,a_2,...,a_m be all the primes of that form

    Let x=6\cdot{a_1\cdot{a_2\cdot{...\cdot{a_m}}}}-1

    This number must have a prime factor of the form p\equiv{-1}(\bmod.6), but it is not divisible by any prime of the form p=6l-1 (by our assumption). This is absurd, therefore there have to be infnitely prime numbers of the form p=6k-1
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    We can generalize this result. Let p \equiv - 1(\bmod n). Suppose that all the (odd) primes are either p\equiv \pm 1(\bmod n). Then there are infinitely many primes p\equiv -1(\bmod n). And the proof is similar. Suppose there are finitely many and define m = n (p_1\cdot ...\cdot p_k) - 1. Now any prime divisior of m has form p\equiv \pm 1(\bmod n). It cannot be that all have form p\equiv 1(\bmod n) because then m would have that form too. So it must mean that one of the prime factors of m satisfies p\equiv -1(\bmod n) but then the LHS is divisible by p but not the RHS.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2008
    Posts
    55
    Quote Originally Posted by PaulRS View Post
    This number must have a prime factor of the form p\equiv{-1}(\bmod.6)...
    How come?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member star_tenshi's Avatar
    Joined
    Jan 2009
    Posts
    32

    Question

    Quote Originally Posted by PaulRS View Post
    This number must have a prime factor of the form p\equiv{-1}(\bmod.6), but it is not divisible by any prime of the form p=6l-1 (by our assumption). This is absurd, therefore there have to be infnitely prime numbers of the form p=6k-1
    I have a similar type of problem on an assignment, but with 4n+3 instead. However, I'm not allowed to use modular arithmetic. Using the 6k-1 example, I was just wondering if I could restate this last part as:

    By the Fundamental Theorem of Arithmetic, there must be a prime of form p=6k-1 such that p|x. But x is not divisible by any prime of form 6l-1 by our assumption. This is a contradiction, thus, there must exist infinitely many primes of the form 6k-1.

    Such a proof should also hold for the case of primes in the form of 4n+3 too right?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by star_tenshi View Post
    I have a similar type of problem on an assignment, but with 4n+3 instead. However, I'm not allowed to use modular arithmetic. Using the 6k-1 example, I was just wondering if I could restate this last part as:

    By the Fundamental Theorem of Arithmetic, there must be a prime of form p=6k-1 such that p|x. But x is not divisible by any prime of form 6l-1 by our assumption. This is a contradiction, thus, there must exist infinitely many primes of the form 6k-1.

    Such a proof should also hold for the case of primes in the form of 4n+3 too right?
    That is what post #4 says.

    All odd primes are either: 4k+1,4k+3.
    If there are finitely many such primes of form 4k+3 it means we can form N = 4p_1...p_n - 1.

    This number N factors into odd primes. Say all these primes where of form 4k+1. Then N would be of form 4k+1 which is a contradiction. Thus, there exists q, and odd prime divisor of form 4k+3. But that forces q|1 which is a contradiction. Thus, there are infinitely many such primes.

    And the same argument works for primes of form 3k+2 also.

    Note: In case you are wondering proving that there are infinitely many primes of forms 4k+1 is more difficult.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member star_tenshi's Avatar
    Joined
    Jan 2009
    Posts
    32
    Awesome, thanks!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Jan 2009
    Posts
    6
    Would this work?

    Numbers at 6n-1 are prime unless one of their factors is at 6n-1. If x is the highest prime at 6n-1 then every number > x at 6n-1 has a product at 6n-1 < x. It must be easy to show that this is impossible.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Infinite Primes Proof is complete ?
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 2nd 2009, 04:49 AM
  2. infinite primes?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 13th 2007, 04:42 PM
  3. Primes in an Infinite Sequence
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 27th 2007, 12:25 AM
  4. my last question-infinite number of primes
    Posted in the Number Theory Forum
    Replies: 15
    Last Post: December 28th 2006, 10:12 AM
  5. Infinite Primes Proof
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: April 11th 2005, 08:40 AM

Search Tags


/mathhelpforum @mathhelpforum