1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Show that the primes of the form 4n-1 and 4n +1 are infinite

  1. Mar 26, 2012 #1
    1. The problem statement, all variables and given/known data
    Show that the number of primes of the form 4n-1 and 4n +1 are infinite

    2. Relevant equations

    3. The attempt at a solution
    I am able to show this for 4n -1 but I am having trouble doing it for primes of the other form. ( I am hoping to do it without using modular arithmetic)

    For primes of the form 4n-1 I used the same argument that was used in Euclid proof by showing that I can always generate a new prime of that form :

    Let 4a-1, 4b-1, 4c-1,...,4k-1 be all the primes of the above form
    let x = 4[(4a-1)(4b-1)(4c-1)...(4k-1)] -1
    1. x has a prime divisor that is not part of the above list because if it was it would have to divide 1 which would make it not prime
    2. the prime divisor is odd so it is of the form 4y+1 or 4y-1
    3. because (4y+1)(4z+1) = 16yz + 4z + 4y + 1 = 4(4yz+y+z) +1 , not all the prime divisors can be of the form 4y+1, one must be of the form 4y-1 so there is a prime divisor that can always be generated in this manner therefore there are an infinite number of primes of the form 4n-1.

    When i try to prove there are an infinite number of primes of the form 4n+1 and I get to the part ( 3. from previous proof)
    I get (4y-1)(4z-1)= 16yz -4y -4z +1 =4(yz -y -z) +1 which doesn't tell me that all the factors are not of the form 4y-1 so i can't make the conclusion that one must be of the form 4y +1. What other way should I approach this.
  2. jcsd
  3. Mar 26, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper

    You probably don't want to avoid modular arithmetic, it is harder than the other case. Think about (2*p1*p2*...*pk)^2+1, where p1, p2..., pk are your finite set of primes of the form 4n+1. If it's divisible by a prime p, then (2*p1*p2*...*pk)^2=(-1) mod p. Using quadratic reciprocity, what sort of prime must p be?
  4. Mar 27, 2012 #3
    I am not familiar with quadratic reciprocity. ( I believe my class will cover that topic soon) The reason I wanted to do it without modular arithmetic is because I am currently taking an intro number theory class and the book went into modular mathematics and and the study of primes without really discussing the theory of divisibility and other elementary concepts I found helpful in other NT books. so I got a another book to study with that does not introduce modular arithmetic before going over the theory of divisibility and a study of prime number( to the extent it can be studied without mod). So the book that I am currently studying with doesn't expect I know any mod arithmetic when asking this question because the topic hasn't been covered yet.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook