Number Theory: An Introduction to Mathematics

106 II Divisibility Heilbronn and Linfoot (1934) showed that there was at most one additional negative value ofdfor whichOdis a ...

5 Congruences 107 equality (but coincides with it ifm=0). The corresponding equivalence classes are calledresidue classes.Theset ...

108 II Divisibility Since the distinct squares inZ( 4 )are 0 and 1, it follows that an integera≡3mod4 cannot be represented as t ...

5 Congruences 109 Proposition 22The setZ×(m)is a commutative group under multiplication. Proof By Proposition 3(iv),Z×(m)is clos ...

110 II Divisibility In other words, φ(m)=m ∏ p|m ( 1 − 1 /p). The functionφ(m)was first studied by Euler and is known as Euler’s ...

5 Congruences 111 (a+b)p= ∑p k= 0 pCkakbp−k, where the binomial coefficients pC k=(p−k+^1 )···p/^1 ·^2 ·····k are integers. More ...

112 II Divisibility then xn− 1 =f ̄(x)g ̄(x)h ̄(x), g ̄(xp)=f ̄(x)k ̄(x). Butg ̄(xp)= ̄g(x)p,sinceFp[x] is a ring of characteris ...

5 Congruences 113 Proof Ifais a quadratic residue ofp,thena≡c^2 modpfor some integercand hence, by Fermat’s little theorem, a(p− ...

114 II Divisibility (ii)for any k∈N,akhas order d/(k,d); (iii)H={ 1 ,a,...,ad−^1 }is a subgroup of G and d divides n. Proof Anyk ...

5 Congruences 115 The same argument shows that, for an arbitrary fieldK, any finite subgroup of the multiplicative group ofKis c ...

116 II Divisibility The general case of Proposition 34 was first proved by Warning (1936), after the particular case had been pr ...

5 Congruences 117 Any Carmichael numbernmust be odd, since it has an odd prime factorpsuch that p−1dividesn−1. Furthermore a Car ...

118 II Divisibility Proposition 36 can be considerably generalized: Proposition 37For any integers m 1 ,...,mnand a 1 ,...,an, t ...

6 Sums of Squares 119 Corollary 38 can also be proved by an extension of the argument used to prove Proposition 36. Both Proposi ...

120 II Divisibility ThenN(γ)≥0, with equality if and only ifγ=0, andN(γ 1 γ 2 )=N(γ 1 )N(γ 2 ).If γ∈G,thenN(γ)is an ordinary int ...

6 Sums of Squares 121 Evidentlyγ ∈H if and only if it can be written in the formγ=a 0 h+a 1 i+ a 2 j+a 3 k,wherea 0 ,a 1 ,a 2 ,a ...

122 II Divisibility Putα= 1 +ai+bj.ThenpdividesN(α)=αα ̄= 1 +a^2 +b^2 inZand hence also inH.However,pdoes not divide eitherαorα ...

7 Further Remarks 123 By the results stated above,g(k)=w(k)fork= 2 , 3 ,4 and this has been shown to hold also fork=5 by Chen (1 ...

124 II Divisibility refinement theorem and the Jordan–H ̈older theorem may be viewed as generalizations of Propositions 6 and 7. ...

7 Further Remarks 125 a square or−1, then it is a primitive root for infinitely many primesp. (A quantitative form of the conjec ...