Results 1 to 9 of 9

Math Help - Infinitely many primes with either 4n-1 or 4n+1 ... Questions ...

  1. #1
    Banned
    Joined
    Apr 2009
    Posts
    96

    Infinitely many primes with either 4n-1 or 4n+1 ... Questions ...

    Hello All,

    My book says that "There are infinitely many primes of the form 4n-1 and 4n+1". The problem is my book doesn't provide proof that this is true.


    I've done some research, and it seems like Dirichlet's Theorem is plausible, but there should be an easier way to understand this that covers both examples.

    Can anyone prove both of these in an easy way?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by 1337h4x View Post
    Hello All,

    My book says that "There are infinitely many primes of the form 4n-1 and 4n+1". The problem is my book doesn't provide proof that this is true.


    I've done some research, and it seems like Dirichlet's Theorem is plausible, but there should be an easier way to understand this that covers both examples.

    Can anyone prove both of these in an easy way?
    4n-1

    4n+1
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by chiph588@ View Post

    I looked there and other places google had spat out. I'm looking to see if there is an easier way of explaining it, and also a better way of formatting it as well...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by 1337h4x View Post
    I looked there and other places google had spat out. I'm looking to see if there is an easier way of explaining it, and also a better way of formatting it as well...
    First I'll do  4n+3 :

    -------

    Lemma: The product of two integers  4n+1 and  4m+1 is an integer of the form  4k+1

    Proof:  (4n+1)(4m+1)=16nm+4n+4m+1=4(4nm+n+m)+1=4k+1 , as we choose to define  k=4nm+n+m .

    -------

    Now suppose there are finitely many primes of the form  4n+3 where the list is  \{p_0=3,\; p_1=7,\; p_2,\; \ldots,\; p_k \} where  p_k is the largest prime of the form  4n+3 .

    Define  N=4p_1p_2\cdots p_k+3 (note that  N is odd and we're leaving out  p_0 from  N ). Since  N is of the form  4n+3 ,  N>p_k \implies N is composite. So let's look at its prime factors. If all prime factors were of the form  4m+1 then by the Lemma above,  N would also have the form  4m+1 . This means we know there is at least one prime of the form  4n+3 that divides  N .

    Suppose  3\mid N \implies 3\mid N-3 \implies 3\mid 4p_1p_2\cdots p_k . Since  3 can't divide  4p_1p_2\cdots p_k we see  3 doesn't divide  N .

    Now suppose  p_i\mid N for some  p_i\in \{p_1,\; p_2,\ldots,\;p_k\} , then  p_i\mid N\implies p_i\mid N-4p_1p_2\cdots p_k = 3 , but clearly  p_i can't divide  3 .

    Thus since no prime in our list divides  N and we know there is a prime of the form  4n+3 that does divide  N , we see that we've left a prime out of the list. This means our list is incomplete.

    Now observe that this implies there are an infinite amount since if we add in our missing prime to our list, we can do this whole process again and see we're missing another prime again, and so on and so on...

    I'll do the primes of the form  4n+1 for you soon.
    Last edited by chiph588@; May 28th 2010 at 07:35 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Here's  4n+1 :

    Again, assume there are only finitely many primes of the form  4n+1 . Define  N=(2p_1p_2\cdots p_k)^2+1 , where  \{p_1,\;p_2,\;\ldots,\;p_k\} is the set of the primes of the form  4n+1 . Since  N is of the form  4n+1 ,  N>p_k \implies N is composite.

    Let  p\mid N . Since  N is odd,  p\neq2 . Thus  (2p_1p_2\cdots p_k)^2+1\equiv0\bmod{p}\implies (2p_1p_2\cdots p_k)^2\equiv-1\bmod{p}\implies x^2\equiv-1\bmod{p} is solvable. By your post here, we see that this implies  p\equiv1\bmod{4}\implies p is of the form  4n+1 .

    Therefore  p\in\{p_1,\;p_2,\;\ldots,\;p_k\}\implies p\mid(2p_1p_2\cdots p_k)^2 . So  p\mid N-(2p_1p_2\cdots p_k)^2=1 which is a contradiction. Using the same reasoning as in the above post, we see that there are an infinite amount of primes of the form  4n+1 .
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by chiph588@ View Post
    Here's  4n+1 :

    Again, assume there are only finitely many primes of the form  4n+1 . Define  N=(2p_1p_2\cdots p_k)^2+1 , where  \{p_1,\;p_2,\;\ldots,\;p_k\} is the set of the primes of the form  4n+1 . Since  N is of the form  4n+1 ,  N>p_k \implies N is composite.

    Let  p\mid N . Since  N is odd,  p\neq2 . Thus  (2p_1p_2\cdots p_k)^2+1\equiv0\bmod{p}\implies (2p_1p_2\cdots p_k)^2\equiv-1\bmod{p}\implies x^2\equiv-1\bmod{p} is solvable. By your post here, we see that this implies  p\equiv1\bmod{4}\implies p is of the form  4n+1 .

    Therefore  p\in\{p_1,\;p_2,\;\ldots,\;p_k\}\implies p\mid(2p_1p_2\cdots p_k)^2 . So  p\mid N-(2p_1p_2\cdots p_k)^2=1 which is a contradiction. Using the same reasoning as in the above post, we see that there are an infinite amount of primes of the form  4n+1 .

    So how is this manipulated similarly to show 4n-1 primes?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by 1337h4x View Post
    So how is this manipulated similarly to show 4n-1 primes?
     4n+3=4(n+1)-1

    Thus my proof for  4n+3 works for  4n-1
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by chiph588@ View Post
     4n+3=4(n+1)-1

    Thus my proof for  4n+3 works for  4n-1
    I would like to understand how this works. I understand how you did 4n+3 = 4(n+1)-1 because that is 4n+4-1= 4n+3, but are you essentially treating (n+1) as a specific (n) and then stating that 4(n)-1 works for all primes ?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by 1337h4x View Post
    I would like to understand how this works. I understand how you did 4n+3 = 4(n+1)-1 because that is 4n+4-1= 4n+3, but are you essentially treating (n+1) as a specific (n) and then stating that 4(n)-1 works for all primes ?
    A number of the form  4n+3 is of the form  4m-1 .

    A number of the form  4n-1 is of the form  4m+3 .

    Thus these two forms are equivalent.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Infinitely many primes
    Posted in the Number Theory Forum
    Replies: 11
    Last Post: June 4th 2010, 06:43 AM
  2. Infinitely many primes of the sequence 3n + 2
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: November 11th 2009, 03:32 AM
  3. infinitely many primes of the form 6k + 5 and 6K + 1
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 22nd 2009, 06:25 AM
  4. Infinitely Many Primes
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 24th 2009, 07:12 PM
  5. infinitely many primes
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: November 18th 2008, 08:07 AM

Search Tags


/mathhelpforum @mathhelpforum