HOW IT SHOULD BE

Published by

  • mémoire
1
  • tidy bundle on the back seat
  • stretch of country road
  • monotony of evening television
  • local dealer at a fraction of the prices
  • brake pedal
  • halt at the foot of a willow tree
  • moist surface with remarkable tenacity
  • straight of road
Published : Monday, March 26, 2012
Reading/s : 18
Origin : imomath.com
Number of pages: 7
See more See less
c2007 The Author(s) and The IMO Compendium Group
Contents
1
1 2 3 4
Arithmetic in Extensions ofQ
DuˇsanDjukic´
General Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Arithmetic in the Gaussian IntegersZ[i]. . . . . . . . . . . . . . . . . . . . . . . . Arithmetic in the ringZ[w]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Arithmetic in other quadratic rings . . . . . . . . . . . . . . . . . . . . . . . . . . .
General Properties
1 4 5 6
What makes work with rational numbers and integers comfortable are the essential properties they have, especially the unique factorization property (the Main Theorem of Arithmetic). However, the might of the arithmetic inQThus, some polynomials, although they have zeros,is bounded. cannot be factorized into polynomials with rational coefficients. Nevertheless, such polynomials can 2 always be factorized in a wider field. For instance, the polynomialx+1 is irreducible overZor Q, but over the ring of the so calledGaussian integersZ[i] ={a+bi|a,bZ}it can be factorized as(x+i)(xi). Sometimes the wider field retains many properties of the rational numbers. In particular, it will turn out that the Gaussian integers are a unique factorization domain, just like the (rational) integersZ. We shall first discuss some basics of higher algebra.
n n1 a Definition 1.A numberCisalgebraicif there is a polynomial p(x) =anx+an1x+∙ ∙ ∙+a0 with integer coefficients such that p(a) =0. If an=1, thenais analgebraic integer. Further, p(x)is theminimal polynomialofaif it is irreducible overZ[x]be written(i.e. it cannot as a product of nonconstant polynomials with integer coefficients).
2 Example 1.The number i is an algebraic integer, as it is a root of the polynomial x+1which is also its minimal polynomial. Number2+3is also an algebraic integer with the minimal polynomial 4 2 x10x+1(verify!).
Example 2.The minimal polynomial of a rational number q=a/b (aZ, bN,(a,b) =1) is bxa. By the definition, q is an algebraic integer if and only if b=1if and only if q is an, i.e. integer.
n n1 a Definition 2.an algebraic integer and pLet be (x) =x+an1x+∙ ∙ ∙+a0(aiZ) be its minimal polynomial. Theextensionof a ring A by the elementais the set A[a]of all complex numbers of the form n1 a a c0+c1+∙ ∙ ∙+cn1(ciA),()
with all the operations inherited from A. Thedegreeof the extension is the degree n of the polynomial p(x).
2
Olympiad Training Materials, www.imomath.com
The theme of this text are extensions of the ringZof degree 2, so calledquadratic extensions. 2 2 Thus, for example, the polynomialsx+1 andx+x+1 determine the extensionsZ[i]andZ[w], 1+3 wherew=(this notation will be used later). 2 All elements of a quadratic extension ofZare algebraic integers with the minimal polynomial of second degree. Two elements having the same minimal polynomials are said to beconjugates. Each nonrational elementzof the quadratic extension has exactly one conjugate, called the conjugate ofz and denotedz. For a rational integerzwe definez=z.
Definition 3.Thenormof an element z of a quadratic extension ofZis N(z) =zz.
The norm is always an integer. Roughly speaking, it is a kind of equivalent of the absolute value in the set of integersZ.
2 2 Example 3.If zZ[d], z=a+b d (a,bZ), then z=ab d and N(z) =adb . 2 2 particular, inZ[i]the norm of element a+bi (a,bN) is N(a+bi) =a+b . 2 2 If z=a+bwZ[w](a,bZ), then z=abbwand N(z) =aab+b . In every complex quadratic field the conjugation corresponds to the complex conjugation.
The following two propositions follow directly from definition.
In
Theorem 1.for arbitrary elements zThe conjugation is multiplicative, i.e. 1,z2of a quadratic ex-tension ofZit holds that z1z2=z1z2.2
Theorem 2.The norm is multiplicative, i.e. for arbitrary elements z1,z2of a quadratic extension of Zit holds that N(z1z2) =N(z1)N(z2).2
′ ′ An elementeZ[a]is called aunitif there existseZ[a]such thate e=1. In that case N(e)N(e) =N(1) =1, soN(e) =±1. In fact,eis a unit if and only if its norm is±1: indeed, if N(e) =±1 thene=±1 by definition.
Example 4.The only units inZare±1. 2 2 Let us find the units inZ[i]a. If +bi (a,bZ) is a unit, then N(a+bi) =a+b=±1, which implies a+bi∈ {±1,±i}. 2 2 All units inZ[w]are±1,±w,±(1+w)if a. Indeed, +bwis a unit then aab+b=1, i.e. 2 2 2 (2ab) +3b=4and he result follows. Note thatwequals(1+w).
p1 2 Problem 1.Let p be a prime number and N= (k+1)the remainder of N upon. Determine Õ k=1 division by p.
p1 Solution.DenoteP(x) = (1+x)(2+x). . .(p1+x)know that. We P(x) =x1+pQ(x)for some polynomialQ(x)with integer coefficients. 2 Sincek+1= (k+i)(ki)for eachk, we immediately obtain that     p1p1 N=P(i)P(i) =i1+pQ(i) (i)1+pQ(i) 4,ifp3 (mod 4); ≡ △ 0,otherwise.
The divisibility and congruences in an extensionKof the ringZis defined in the usual way: xKis divisible byyK(denotedy|x) if there existszKsuch thatx=yz, andxy(modz) if z|xy. Since every element of a quadratic ring is divisible by every unit, the definition of the notion of a prime must be adjusted to the new circumstances.
DusˇanDjukic´:ArithmeticinExtensionsofQ
3
Definition 4.An element y of a quadratic ring K isadjointto element x (denoted yx) if there exists a unitesuch that y=ex.
Definition 5.A nonzero element xK which is not a unit isprimeif it has no other divisors but the units and elements adjoint to itself.
We have the following simple proposition.
Theorem 3.Let xK. If N(x)is a prime, then x is prime.
Proof.Suppose thatx=yz,y,zK. ThenN(x) =N(y)N(z), so at least one ofN(y),N(z)equals ±1, i.e. eitheryorzis a unit, while the other is (by definition) adjoint tox.2 The converse does not hold, as 3 is a prime inZ[i], butN(3) =9 is composite. Of course, the elements conjugate or adjoint to a prime are also primes. Therefore the smallest positive rational integer divisible by a primezequalszz=N(z). Consider an arbitrary nonzero and nonunit elementxK. Ifxis not prime then there are nonunit elementsy,zKsuch thatyz=x. HerebyN(y)N(z) =N(x)andN(y),N(z)>1. HenceN(y),N(z)< N(x)this procedure we end up with a factorization. Continuing x=x1x2∙ ∙ ∙xkin which all elements are prime. This shows that:
Theorem 4.Every nonzero and nonunit xK can be factorized into primes.2
Problem 2.Given a nonzero and nonunit element zK, find the number of equivalence classes in K modulo z.
2 Solution.LetK=Z[a], wherea=pa+q,p,qZ, and letz=a+ba(a,bZ). Ifb=0 then 2 a1+b1aa2+b2a(modz) if and only ifa1a2andb1b2(modzthere are). Thus N(z) =z equivalence classes. Now suppose thatb6=0 and that(a,b) =d. Thenaz= (a+pb)a+qb. Since(a+pb,b) =d, the coefficient atainxz(xK) can be any integer divisible bydMoreover,and no other integer. the smallest natural number divisible byzis|(a+ba)(a+ba)|/d=|N(z)|/d. We conclude that for everyxKthere is a uniqueX=A+BaKwithA,BZ, 0A<|N(z)|/d, 0B<dsuch that xX(modz). Therefore the required number of equivalence classes equals|N(z)|.
Naturally, we would like to know when the factorization into primes is unique, i.e. when the Fundamental Theorem of Arithmetic holds. But let us first note that, by the above definition, the primes ofZare±2,±3,±5, etc, so the factorization into primes is not exactly unique, as e.g. 23= (2)(3). Actually, in this case the uniqueness of factorization is true in the following wording.
Definition 6.FTA, or ”The Fundamental Theorem of Arithmetic” means: Each nonzero and nonunit element ofZor of its quadratic extension K can be written as a product of primes. This factorization is unique up to the order of the factors and adjoining between corresponding factors.
The division with remainder in a quadratic extensionKofZcan be formulated as follows:
Definition 7.DWR means: For each a,bK with b6=0there exist p,qK such that a=pb+q and N(q)<N(b).
Obviously, such a division, if it exists, is not necessarily unique - it is not so even inZitself. Moreover, it does not exist in some quadratic extensions, as we shall see later. The significance of the existence of a division with remainder, however, lies in the fact that it implies the uniqueness of factorization:
Theorem 5.If the division with remainder in a quadratic ring K is always possible, then FTA holds in K.
4
Olympiad Training Materials, www.imomath.com
Proof.If the division with remainder is possible inK, then the Euclidean algorithm ends in a finite number of steps. A simple implication of the Euclidean algorithm is that ifpis a prime,a,bKand p|ab, thenp|aorp|b. The uniqueness of factorization into primes (FTA) now easily follows.2 There are quadratic rings in which FTA holds despite the nonexistence of a division with remain-der. However, FTA is an exception rather than a rule.
Example 5.FTA is false inZ[5], as 9 has two factorizations into primes:9=33= (2+ 5)(2− −5), which are not equivalent since2± −56∼3.
Example 6.The factorizations of the element4winZ[w]as(1w)(3+w) = (23w)(1+2w) are considered the same, since1+2w=w(1w)1wand23w=(1+w)(3+w)3+w. We shall show later that FTA is true inZ[w].
2 Arithmetic in the Gaussian IntegersZ[i] 2 2 We have already seen that the norm of elementa+biZ[i](a,bZ) isN(a+bi) =a+band the units are±1 and±i. Therefore, all divisors of a prime elementpZ[i]are±1,±i,±p,±ip.
Theorem 6.The Fundamental Theorem of Arithmetic (FTA) holds in the set of Gaussian integers Z[i].
Proof.Based on theorem 5, it is enough to show that for alla,bZ[i]withb6=0 there exists an elementpZ[i]such thatN(apb)<N(b). Lets,tRbe such thata/b=s+ti, and lets,tZbe such that|ss| ≤1/2 and|tt| ≤1/2. Settingp=s+tiyieldsapb= (s+ti)bpb= [(ss) + (tt)i]b, which implies
2 2 N(apb) =N[(ss) + (tt)i]N(b) = [(ss) + (tt) ]N(b)N(b)/2<N(b).
This proves the theorem.2 The following proposition describes all prime elements in the set of Gaussian integers.
Theorem 7.An element xZ[i]is prime if and only if N(x)is a prime or|x|is a prime integer of the form4k1, kN.
Proof.Consider an arbitrary primex=a+biZ[i](a,bZ). Elementxis prime also (indeed, if x=yz, thenx=y z), soN(x)factorizes into primes asxx. Suppose thatN(x)is composite,N(x) =mnfor some two natural numbersm,n>1. It follows fromxx=mnand the FTA thatxmorxn, so we may suppose w.l.o.g. thatxis a prime integer. Ifx=2 orx1 (mod 4), then there exist integersa,bZsuch thatN(a+bi) = (a+bi)(abi) = 2 2 a+b=x; hencexis composite inZ[i]the other hand, if. On xis a prime integer withx3 (mod 4), thenxis also prime inZ[i]if. Indeed, x=uvfor some nonunit elementsu,vZ[i], then 2 x=N(x) =N(u)N(v)impliesN(u) =N(v) =xwhich is impossible. This proves our claim.2
5 2 Problem 3.Solve the equation x1=y in integers.
5 Solution.Rewrite the equation in the formx= (y+i)(yi). Note thatxis not even, as otherwise 2 y≡ −Thus1 (mod 4). yis even and consequently the elementsy+iandyiare coprime in Z[i]. Since(y+i)(yi)is a fifth power, it follows thaty+iandyiare both fifth powers. Let 5 4 2 2 4 4 2 2 4 a,bZbe such thaty+i= (a+bi) =a(a10a b+5b) +b(5a10a b+b)i. It holds that 4 2 2 4 b(5a10a b+b) =1, and thereforeb=±1. It is easily seen that in both cases we havea=0; hencey=0,x=±1 are the only solutions.
2 Problem 4.Suppose that x,y and z are natural numbers satisfying xy=z+1that there. Prove 2 2 2 2 exist integers a,b,c,d such that x=a+yb , =c+zd and =ac+bd.
DuˇsanDjuki´c:ArithmeticinExtensionsofQ
5
Solution.IfWe use the following important fact: m,n,p,qare elements of a unique factorization domainK(in this case,K=Z[i]) satisfyingmn=pq, then there existu1,u2,v1,v2Ksuch thatm= u1v1,n=u2v2,p=u1v2,q=u2v1. The proof of this fact is the same as in the case ofm,n,p,qZ and follows directly from the factorizations ofm,n,p,qinto primes. 2 Sincexy=z+1= (z+i)(zi), the above fact gives us
x=u1v1
(1),
y=u2v2
(2),
z+i=u1v2
(3),
zi=u2v1
(4)
for someu1,u2,v1,v2Z[i]. The numbersx,yare real, and thereforev1=q1u1,v2=q2u2for some rational numbersq1,q2. From (3) and (4) we easily conclude thatq1=q2=putting1. Now 2 2 2 2 u1=a+bi,u2=c+diyieldsx=u1u1=a+b,y=c+dandz=ac+bd.
3 Arithmetic in the ringZ[w] Herewdenotes a primitive cubic root of unity. Then the norm of an elementa+bwZ[w](a,bZ) 2 2 2 isN(a+bw) =aab+band the units are±1,±wand±(1+w) =w.
Theorem 8.FTA holds in the ringZ[w].
Proof.By the theorem 5, it suffices to show that a division with remainder is possible, i.e. for all a,bZ[w],b6=0 there existpZ[w]such thatN(apb)<N(b). Like in the proof for the Gaussian integers, lets,tRbe such thata/b=s+ti, and lets,tZ be such that|ss| ≤1/2 and|tt| ≤1/2. Settingp=s+tigives usN(apb)3N(b)/4<N(b), implying the theorem.2
Problem 5.If p1(mod 6) is a prime number, prove that there exist a,bZsuch that p= 2 2 aab+b .
Solution.It suffices to show thatpis composite inZ[w]. Indeed, if there is a prime element z=a+bwZ[w](a,bZ) that dividesp, then alsoz|p=pthat. Note zandzare coprime; otherwisez|z, so there exists a unit elementewithz=ez, and hencez(1w)|3, which is false. 2 2 2 2 Thereforeaab+b=zz|p, which impliesaab+b=p. Thus we need to prove thatpis composite inZ[w]follows from the condition on. It pthat -3 is a quadratic residue modulop, so there existm,nZwhich are not divisible bypsuch that 2 2 2 2 p|(2mn) +3n=4(mmn+n), i.e.p|(mnw)mnw. However,pdoes not divide any of the elements(mnw),mnw, so it must be composite.
Theorem 9.Element xZ[w]is prime if and only if N(x)is prime or|x|is a prime integer of the form3k1, kN.
Proof.Numberx=3 is composite, asN(1w) = (1w)(2+w) =3. Moreover, by problem 4, every prime integerp1 (mod 6) is composite inZ[w]. The rest of the proof is similar to the proof of Theorem 7 and is left as an exercise.2 Maybe the most famous application of the elementary arithmetic of the ringZ[w]is the Last Fer-3 3 mat Theorem for the exponentn=3. This is not unexpected, having in mind thatx+yfactorizes overZ[w]into linear factors:
3 3 2 2 2 x+y= (x+y)(x+wy)(x+wy) = (x+y)(wx+wy)(wx+wy).
The proof we present was first given by Gauss.
Theorem 10.The equation 3 3 3 x+y=z has no nontrivial solutions inZ[w], and consequently has noneZeither.
(1)
()
Be the first to leave a comment!!

12/1000 maximum characters.