Any number of the form
\[4k+3\]
is divisible by a prime number of this form.Proof
The Division Algorithm tells us that any integer is one of the forms
\[4q, \; 4q+1, \; 4q+2, \; 4q+3\]
. \[4q\]
and \[4q+2\]
are even so for \[q \ge 1\]
these numbers are composite. \[4k+3\]
is odd so not divisible by primes of the form \[4q\]
or \[4q+2\]
.Suppose then that it is only divisible by primes of the form
\[4q+1\]
. But then since \[(4s+1)(4q+1)=4(4sq+s+q)+1\]
the number would then be of this form (and not \[4k+3\]
), so by elimination, \[4k+3\]
must be divisible by a prime of this form.