Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. 09 Oct '08 12:11
    Prove that there are infinite primes of the form 4k+3.

    Note: No, you are not allowed to use the "twin prime" theorem, as it had not been proven...
  2. 09 Oct '08 13:41 / 2 edits
    I have a fairly simply proof.

    For it, I keep a running product, starting with 4. I then look at the number just before the running product, in this case 3.

    Now 3 is 4*0 + 3, and it happens to be prime, so I multiply my product by 3 so that the next number in my series isn't divisible by 3.

    So now my product is 12, and the next number of the form 4k+3 is 11. Also prime, and I multiply it into the product.

    Now, for each number in the series, I know it isn't divisible by any of the primes I found before. That leaves 2 possibilities.

    1) The number is prime.
    2) The number is equal to a NEW prime of the form 4k+3 multiplied by a number of the form 4k+1. (Modulo arithmetic)

    Either way, I can examine the number to arrive at a new 4k+3 prime, which then gets multiplied into the product for one more prime of the form 4k+3.

    As I can do this indefinitely, there must therefore be an infinite number of 4k+3 primes.

    Pardon the ugliness of the proof, but it works as far as I can see.

    (It doesn't, however, work for 4k+1 primes, as a 4k+1 value can be the product of 2 4k+3 values..)
  3. 09 Oct '08 21:54
    Hmm, found a more succinct way to argue my proof.

    Let P be the product of 4 and every known 4k+3 prime.

    P-1 would be a 4k+3 number relatively prime to P.

    If P-1 is prime, then it has to be a NEW 4k+3 prime.

    If P-1 is not prime, then modulo arithmetic dictates that one of its factor is a smaller 4k+3 number. This factor could be analyzed to arrive at a similar conclusion based on the same facts, as well as any 4k+3 factors it may have.

    The end result, however, is that P-1 is divisible by at least 1 4k+3 prime not yet in the set of known 4k+3 primes (else P and P-1 would not be relatively prime).

    As we can keep repeating this process and always find at least one more 4k+3 prime, there must be an infinite number of them.
  4. 10 Oct '08 09:23
    Originally posted by geepamoogle
    Hmm, found a more succinct way to argue my proof.

    Let P be the product of 4 and every known 4k+3 prime.

    P-1 would be a 4k+3 number relatively prime to P.

    If P-1 is prime, then it has to be a NEW 4k+3 prime.

    If P-1 is not prime, then modulo arithmetic dictates that one of its factor is a smaller 4k+3 number. This factor could be analyzed to a ...[text shortened]... process and always find at least one more 4k+3 prime, there must be an infinite number of them.
    That's very nice. I didn't think of multiplying by 4 - that makes it a lot less convoluted.