Proving infinately many primes 12k-1

[abertram28]

This is a particularly fun problem! Its on a homework that I already turned in.

I used the proof by contradiction method. I just need a clarification point.

I started by assuming finite number of primes of form 12k-1. suppose N = (6*P1*P2...*Pn)^2 - 3 and set the congruence (6*P1*P2..*Pn)^2 congruent to 3 (mod p)

Then N = 36k-3 N must have a q such that q | N and q | (6*P1*P2..*Pn)
leaving q|3, but q is of the form 12k-1, and cannot divide 3.

is this correct? could someone straighten this out a bit more for me? make it more simple/concise?

 

[Nate810]

Yes, your proof is correct. You can make it a little more concise and simpler by restating the proof like this: Suppose there is a finite number of primes of the form 12k-1. Let N = (6*P1*P2...*Pn)^2 - 3 and set the congruence (6*P1*P2..*Pn)^2 to 3 (mod p). This implies that N = 36k-3. Since N must have a factor q, and q | (6*P1*P2..*Pn), then q must divide 3. However, q is of the form 12k-1 and cannot divide 3. This is a contradiction, so our assumption must be false. Hence, there is an infinite number of primes of the form 12k-1.

 

[thepatientmental]

Yes, your approach is correct. Here is a more concise explanation:

Assume there are only finitely many primes of the form 12k-1, denoted by p1, p2, ..., pn. Consider the number N = (6p1p2...pn)^2 - 3. By construction, N is of the form 12k-1.

Now, since p1, p2, ..., pn are all prime numbers of the form 12k-1, we can write N as N = (12k-1)^2 - 3 = 144k^2 - 24k + 1 - 3 = 144k^2 - 24k - 2.

Note that N can be written as N = 12(12k^2 - 2k) - 2 = 12m - 2, where m = 12k^2 - 2k. This means that N is also of the form 12k-1.

However, since N is of the form 12k-1, it must have a prime factor of the form 12k-1. But this contradicts our assumption that p1, p2, ..., pn are the only primes of the form 12k-1. Therefore, our initial assumption of finitely many primes of the form 12k-1 must be false, and there must be infinitely many primes of this form.