Number Theory: An Introduction to Mathematics

86 II Divisibility It follows from Proposition 4 that ifcn=ab,where(a,b)=1, thena=dnand b=enfor somed,e∈N. The greatest common d ...

1 Greatest Common Divisors 87 Proof We show first that ifa=a 1 ···anandd|a,thend=d 1 ···dn,wheredi|ai ( 1 ≤i ≤n). We may suppose ...

88 II Divisibility Another example, which we will meet in§4 of Chapter VI, is the valuation ringR of a non-archimedean valued fi ...

1 Greatest Common Divisors 89 It should be noted that factorization into primes would not be unique if we admit- ted 1 as a prim ...

90 II Divisibility 6 = 2 × 3 =( 1 + √ − 5 )( 1 − √ − 5 )has two essentially distinct factorizations into irreducibles, and thus ...

2TheB ́ezout Identity 91 For example, ifa 1 ,...,anare given elements ofZ, then the set of all linear com- binationsa 1 x 1 +··· ...

92 II Divisibility integers. Since( 0 ,b)=b, we may assumea=0. Then there exist integersq,rsuch that b=qa+r, |r|<|a|. Puta 0 ...

2TheB ́ezout Identity 93 Binomial coefficients have other arithmetic properties. Hermite observed thatm+nCn is divisible by the ...

94 II Divisibility Similarly, since am+ 1 Am+ 1 ,n=am+n+ 1 Am,n, am+ 1 Am+ 1 ,n− 1 =anAm,n, am+ 1 divides (an,am+n+ 1 )Am,nand, ...

2TheB ́ezout Identity 95 chosen vertices is equal to the greatest common divisor of the remaining three vertices. Hillman and Ho ...

96 II Divisibility It follows from the remarks at the end of Section 1 that a principal ideal domain is factorial, i.e. any elem ...

3 Polynomials 97 It is easily verified that, for all polynomialsf,g, |f+g|≤max{|f|,|g|}, |fg|=|f||g|. Since|f|≥0, with equality ...

98 II Divisibility then (q−q 1 )f=r 1 −r, |r 1 −r|<|f|, which is only possible ifq=q 1. Ideals inK[t] can be defined in the s ...

3 Polynomials 99 We now consider the connection between polynomials in the sense of algebra (polynomial forms) and polynomials i ...

100 II Divisibility Proposition 16Let R be a GCD domain and K its field of fractions. Let f=a 0 +a 1 t+···+antn be a polynomial ...

3 Polynomials 101 Consequently we can replacedby a proper divisord′, again not a unit, for which m′+n′>m+n. Since there exist ...

102 II Divisibility whereg=b 0 +b 1 t+···, then by equating constant coefficients we would obtain a 0 b 0 =1, which is a contrad ...

3 Polynomials 103 {( 1 +t)p− 1 }/t=tp−^1 +pCp− 1 tp−^2 +···+pC 2 t+p satisfies the hypotheses of Proposition 19. For any fieldK, ...

104 II Divisibility 4 EuclideanDomains.......................................... An integral domainRis said to beEuclideanif it ...

4 Euclidean Domains 105 Suppose now that (i) and (ii) both hold. Thenδ( 1 )≤δ(a)for anya=0, since a= 1 a.Furthermore,δ(a)=δ(ae) ...