Multiplying With Remainders

The following proposition is a critical step in the proof that there are infinitely many primes of the form 4k + 3.

Proposition: Every positive integer N of the form 4k + 3 has a prime factor of the same form.

Proof: If N itself is prime, then we have nothing to prove. So, we can proceed by induction. We assume that the result is true for all positive integers of this form that are less than N. We can also assume that N is not prime. So, it factors. Since N is odd, it must factor as a product of two odd numbers. There are three potential possibilities for the forms of the factorization.

1. N = (4a + 1)(4b + 1) = 4(4ab + a + b) + 1.
2. N = (4a + 1)(4b + 3) = 4(4ab + 3a + b) + 3.
3. N = (4a + 3)(4b + 3) = 4(4ab + 3a + 3b + 2) + 1.

Notice, however, that cases (1) and (3) are impossible, since when you multiply them out, you get a number of the form 4k + 1. Thus, the only case that can actually occur when factoring N is case (2). But in this case, one of the factors has the same form. By the inductive hypothesis, we get a prime factor of the same form, as desired.

[Home Page] [Bioinformatics] [Mathematics] [Creative Efforts]

[HOME] [PREVIOUS] [NEXT] [UP] [DOWN]