Prove that there exist infinitely many primes of the form 4x+1 and infinitely many primes of the form 4x-1.

(In reply to re(2): Too simplistic? by Math Man)

Thanks for the clarification, Math Man. Accordingly:

Introduction           
           
I Every number is either prime, or if compound, can be uniquely factored into primes.    
II We call two numbers co-prime if they do not share any prime factors; even if one or both are compound.

III That there are infinitely many primes:

Assume,  that there is just one known prime, 2. Multiply 2 by 2 and deduct 1. Now we have a number that is not divisible by 2, hence cannot be factored by any known prime. So there must exist some new prime number or numbers (in fact 3, which happens to be prime).          
 
Multiply (2*3) and deduct 1. Now we have a number that is not divisible by any of our known primes, 2, and 3, hence cannot be factored by any known prime. So there must exist some new prime number or numbers (in fact 5, which happens to be prime). We can do this indefinitely; since every new number in the sequence is co-prime to all its predecessors, the sequence generates an infinite number of different primes.  
        
It follows that there are infinitely many primes, only one of which, 2 is even. Hence all other primes are either type (4x+1) or (4x-1). The 'multiplying and adding or taking away a little bit' approach will be used throughout below.

Proof 

We have 3 possibilities when  types (4x+1) and (4x-1) are multiplied together:       

(4x+1)(4y+1)=4(4xy+x+y)+1=, say, 4a+1, or type A
(4x-1)(4y-1)=4(4xy-x-y)+1=, say, again, 4a+1, or type A       
(4x+1)(4y-1)=4(4xy-x+y)-1=, say,  say, 4b-1, or type B   

Multiplying the compound types together:

A*A=A           
B*B=A           
A*B=B           
           
We start with 5 since we know it is the smallest prime of type A, and 3 since it is the smallest prime of form B. We know their product will be type B, in fact 15. We deduct 2 from that: 15-2 =13, which happens to be prime, and is of type A, as we would expect. (3*5)*13= 195, from which we deduct 2 again to produce 193, a number of type A, which again happens to be prime. And so on; as above, since the number we are producing each time differs by 2 from a multiple of every earlier multiplicand in the series, either it is prime,  or each of its prime factors is a hitherto unknown new prime:           
(3), 5, 13, 193, 37633, 1416317953, ...           

Every number in this sequence, with the exception of 3, must be of form A. It must therefore either have an even number of new prime factors of form B, or at least one new prime factor of form A. Since we can't yet guarantee which, we will come back to this later. 

4k-1

Instead of 3, we could have used 3^2 (since B*B=A). Now we have (5,9,),43,1933,3740353,13990248045313, ...           
and with the exception of 5,9, every number in this sequence must be of form B. But we know from the 3 listed possibilities that the prime factors of any such number must include at least one new prime of form B, since only A*B=B           
So there must be an infinitude of new primes of form B.  

4k+1
           
Last but not least, we consider numbers of the form A*A=A. If we start with 5,13,61,3961, then 15705361 has the prime factors 7×2243623, i.e B*B, not A*A, so a more refined method is needed. Odd primes worth 1 mod 4 are of the form (2x)^2+(2y-1)^2, a necessary but not sufficient condition (e.g. 3^2+4^2=5^2, which is not prime).  

         
This is however reminiscent of Pythagoras: a=v^2-u^2, b=2uv, c=u^2+v^2, with u and v coprime and u-v odd gives a primitive Pythagorean triple, as has been shown elsewhere.

Every prime factor of c must be of the form 4k+1, if the triple is primitive. Now let u=2k-1 and v=2k, guaranteeing primitiveness, so that c=8k^2+4k+1, and we can inject this back repeatedly into the triple formula:           
8k^2+4k+1           
128k^4+128k^3+48k^2+8k+1         
32768 k^8+65536 k^7+57344 k^6+28672 k^5+8960 k^4+1792 k^3+224 k^2+16 k+1
13,313,195313,76293945313,...
etc. in confidence that every term will be co-prime to all its predecessors, for which an infinite stock of primes of the form (4k+1) is needed, as was to be proved. 
   

 

Edited on December 11, 2012, 1:25 am

Posted by broll on 2012-12-10 11:43:31