09 Oct '08 12:11

Prove that there are infinite primes of the form 4k+3.

Note: No, you are

Note: No, you are

*not*allowed to use the "twin prime" theorem, as it had not been proven...- Joined
- 26 Nov '07
- Moves
- 1085

- Joined
- 15 Feb '07
- Moves
- 667

09 Oct '08 13:412 editsI 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..)- Joined
- 15 Feb '07
- Moves
- 667

09 Oct '08 21:54Hmm, 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.- Joined
- 26 Nov '07
- Moves
- 1085

10 Oct '08 09:23

That's*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.*very*nice. I didn't think of multiplying by 4 - that makes it a lot less convoluted.