Can a prime have a specified remainder?
The usual proof that there are infinitely many primes starts by imagining a finite list and constructing a number not divisible by any prime on the list. A more refined question asks whether infinitely many primes have a particular remainder on division by four. We will prove this for remainder three.
This argument uses only integer divisibility, prime factorization and remainders modulo four. It is an application of those methods, not a proof that every arithmetic progression contains infinitely many primes.
Definition
(Congruence modulo four)
For integers , write when divides . Every integer is congruent modulo four to exactly one of , its remainder. Congruences can be multiplied: if and , then , because .
An odd integer has remainder one or three modulo four. The next lemma supplies the prime divisors that the construction needs.
Lemma
(Every integer above one has a prime divisor)
If is an integer, then some prime number divides .
Proof
(The least divisor above one is prime)
The set of divisors of is nonempty, since belongs to it, so it has a least element . If were not prime, we could write with . Then divides , hence divides , and , contradicting the minimality of . So is a prime divisor of .
Applying the lemma repeatedly to the cofactor shows that every is a product of primes, counted with repetition.
The residue observation that makes the construction work
Theorem
(An odd number congruent to three has a prime divisor congruent to three)
If and , at least one prime divisor of satisfies .
Proof
(A product of factors congruent to one stays congruent to one)
Since , is odd, so none of its prime factors is 2. Every prime factor is therefore odd and has remainder one or three modulo four. Factor into primes, counting repetitions. If all those prime factors were congruent to one modulo four, then multiplying the congruences one factor at a time shows their product is congruent to one modulo four. That product is , which contradicts , because does not divide . At least one prime factor must have remainder three.
Proof X-ray
Where each hypothesis of the residue theorem is used
The argument is a contrapositive in disguise: a number whose prime factors are all one modulo four is itself one modulo four, so a number that is three modulo four cannot have only such factors. Three hypotheses carry the weight. First, already forces to be odd, which removes the prime 2, the only prime whose remainder is neither one nor three; without that, a third remainder class would break the two-case split. Second, multiplicativity of congruences is the engine: it passes from the factors to the product, and it needs the factorization to be finite, which is why repetitions are counted. Third, ensures a factorization with at least one prime exists; the integer is congruent to three modulo four yet has no prime divisor.
The conclusion is only existential. The proof shows that not all factors can be one, and says nothing about the remaining ones.
Common mistake
(Every prime factor of a number congruent to three need not be congruent to three)
The theorem does not say every prime factor of is three modulo four. For example, has the prime factor 13 congruent to one. Nor does it say that a number congruent to three must itself be prime: is composite. What survives is the weaker statement that some prime factor is congruent to three.
Rule out every finite list
Theorem
(Infinitely many primes are congruent to three modulo four)
There are infinitely many primes with .
Proof
(Construct an odd number with the right remainder and no listed divisor)
Suppose instead that there are only finitely many such primes, and list all of them as . The list is nonempty because 3 is one such prime. Let
We have and . By the preceding theorem, has a prime divisor . For each listed , since divides ,
Thus does not divide . In particular is not any listed prime. But is a prime congruent to three modulo four, contradicting the assumption that the list was complete. Therefore no finite list contains all such primes.
The two roles of are different and both are needed: guarantees a prime factor of the desired kind, while excludes every listed prime. The proof neither computes in advance nor assumes is prime.
Proof X-ray
Why the factor four and the sign matter in the construction
The proof has the shape of the usual argument for infinitely many primes but cannot copy it. The number of that argument has an uncontrolled remainder modulo four, and a residue theorem such as the one above only helps when . The factor 4 fixes this: whatever is, is a multiple of four, so . In the sample we have , so itself would not have given the remainder three.
The minus sign does a second job. Subtracting one makes modulo each listed prime, which is a nonzero remainder, so no listed prime divides . The step that closes the contradiction is the combination of the two: the prime exists by the residue theorem, and it is unlisted because every listed prime leaves remainder . Neither fact alone suffices.
Worked example
(A constructed number can be composite)
Starting only with the sample primes , form
Here and ; 71 is prime and is not on the sample list. The factor 71 is a new prime of the desired form even though 923 is composite. A short check of the prime candidates proves 71 is prime, since .
A finite sample is not an assumption that the displayed primes are all such primes. The general contradiction assumes a complete finite list and applies the construction to that hypothetical list.
Worked example
(Finding the prime factor congruent to three)
Take . Since , we have . Factoring, , with remainders modulo four. The product of the remainders is , as it must be, and the factor is the prime of the promised kind. Only one of the three prime factors is congruent to three here.
The smallest case is itself: it is prime, so and there is no other prime factor to look for.
Worked example
(A constructed number that is itself prime)
With the sample list , we get and . Since , it suffices to test : is odd, its digit sum is not a multiple of 3, it does not end in 0 or 5, and . So 83 is prime. Also , and 83 is not on the list .
Here the new prime is itself, so the factor of the theorem is . Both this case and the composite case are covered by the same proof; it never decides which one occurs.
Counterexample mode
Changing the sign loses the residue guarantee
Claim: replace by , and the same argument still produces an unlisted prime congruent to three modulo four. Test the claim on the sample list , so . Then . Both prime factors are one modulo four ( and ), and indeed . Neither is congruent to three, so the claim fails: this number yields no prime of the required kind, listed or not.
This does not contradict the theorem. The number 85 is one modulo four, which is outside the hypothesis of the residue theorem. The repair is the original construction: with the same list, is prime and congruent to three.
Common mistake
(Assuming the constructed number is prime)
It is tempting to write “ is a prime congruent to three that is not on the list”. The case shows this is false in general. All the proof needs is a prime divisor of with the right remainder, which the residue theorem supplies without computing it.
Exercises with solutions
Quick check
(Starting with the sample list containing only 3, calculate and find a new prime congruent to three modulo four.)
Take .
Solution · Answer
, so . The number 11 is prime, is , and is not 3.
Quick check
(Why can no listed prime divide ?)
Compare with .
Solution · Answer
It divides ; if it also divided , it would divide their difference , which is impossible. Equivalently, the constructed number has remainder modulo .
Quick check
(Does imply every prime divisor of has remainder three?)
Try a small composite number.
Solution · Answer
No. is three modulo four, while 13 is one modulo four. At least one prime divisor of the desired form suffices.
Quick check
(Why is not a substitute in this proof?)
Compute its remainder modulo four.
Solution · Answer
It has remainder one modulo four, so its prime factors can all be one modulo four. With , the result is ; neither factor is three modulo four.
A good contradiction construction must satisfy the property that produces the object we want and simultaneously exclude every object on the supposed complete list.