Number Theory: An Introduction to Mathematics

134 III More on Divisibility

Proof Suppose first thata=−1. Since(− 1 /p)=(− 1 )(p−^1 )/^2 ,wewishtoshow

that there are infinitely many primesp≡3 mod 4. Clearly 7 is such a prime. Let

{p 1 ,...,pm}be any finite set of such primes greater than 3. Adapting Euclid’s proof

of the infinity of primes (which is reproduced at the beginning of Chapter IX), we put

b= 4 p 1 ···pm+ 3.

Thenbis odd, but not divisible by 3 or by any of the primesp 1 ,...,pm.Since

b≡3 mod 4, at least one prime divisorqofbmust satisfyq≡3 mod 4. Thus the

set{ 3 ,p 1 ,...,pm}does not contain all primesp≡3 mod 4.

Suppose next thata=±2. Then(a/ 5 )=−1. Let{p 1 ,...,pm}be any finite set

of primes greater than 3 such that(a/pi)=− 1 (i= 1 ,...,m)and put

b= 8 p 1 ···pm± 3 ,

where the±sign is chosen according asa=±2. Thenbis not divisible by 3 or

by any of the primesp 1 ,...,pm.Sinceb≡±3 mod 8, we have( 2 /b)=−1and

(a/b)=−1 in both cases. Ifb=q 1 ···qnis the representation ofbas a product of

primes (repetitions allowed), then

(a/b)=(a/q 1 )···(a/qn)

and hence(a/qj)=−1 for at least onej. Consequently the result holds also in this

case.

Consider now the general case. We may assume thatais square-free, since if

a = a′b^2 ,wherea′is square-free, then(a/p) = (a′/p)for every primepnot

dividinga. Thus we can write

a=ε 2 er 1 ···rh,

whereε=± 1 ,e=0or1,andr 1 ,...,rhare distinct odd primes. By what we have
already proved, we may assumeh≥1.
Let{p 1 ,...,pm}be any finite set of odd primes not containing any of the primes
r 1 ,...,rh. By Proposition 6, there exists an integercsuch that(c/r 1 )=−1. Since the
moduli are relatively prime in pairs, by Corollary II.38 the simultaneous congruences

x≡1mod8, x≡1modpi(i= 1 ,...,m),

x≡cmodr 1 , x≡1modrj(j= 2 ,...,h),

have a positive solutionx =b.Thenbis not divisible by any of the odd primes

p 1 ,...,pmorr 1 ,...,rh. Moreover(− 1 /b)=( 2 /b)=1, sinceb≡1 mod 8. Since

(rj/b)=(b/rj)for 1≤j≤h, it follows that

(a/b)=(ε/b)( 2 /b)e(r 1 /b)···(rh/b)

=(b/r 1 )(b/r 2 )···(b/rh)=(c/r 1 )( 1 /r 2 )···( 1 /rh)=− 1.

As in the special case previously considered, this implies that(a/q)=−1forsome

primeqdividingb, and the result follows.