Primes...

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...

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..)

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.

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.