# HOW IT SHOULD BE

Published by

### iwle0

- mémoire

- 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 coefﬁcients. Nevertheless, such polynomials can 2 always be factorized in a wider ﬁeld. For instance, the polynomialx+1 is irreducible overZor Q, but over the ring of the so calledGaussian integersZ[i] ={a+bi|a,b∈Z}it can be factorized as(x+i)(x−i). Sometimes the wider ﬁeld 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 ﬁrst discuss some basics of higher algebra.

n n−1 a Deﬁnition 1.A number∈Cisalgebraicif there is a polynomial p(x) =anx+an−1x+∙ ∙ ∙+a0 with integer coefﬁcients 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 coefﬁcients).

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 x−10x+1(verify!).

Example 2.The minimal polynomial of a rational number q=a/b (a∈Z, b∈N,(a,b) =1) is bx−a. By the deﬁnition, q is an algebraic integer if and only if b=1if and only if q is an, i.e. integer.

n n−1 a Deﬁnition 2.an algebraic integer and pLet be (x) =x+an−1x+∙ ∙ ∙+a0(ai∈Z) be its minimal polynomial. Theextensionof a ring A by the elementais the set A[a]of all complex numbers of the form n−1 a a c0+c1+∙ ∙ ∙+cn−1(ci∈A),(∗)

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 deﬁnez=z.

Deﬁnition 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 z∈Z[d], z=a+b d (a,b∈Z), then z=a−b d and N(z) =a−db . 2 2 particular, inZ[i]the norm of element a+bi (a,b∈N) is N(a+bi) =a+b . 2 2 If z=a+bw∈Z[w](a,b∈Z), then z=a−b−bwand N(z) =a−ab+b . In every complex quadratic ﬁeld the conjugation corresponds to the complex conjugation.

The following two propositions follow directly from deﬁnition.

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 elemente∈Z[a]is called aunitif there existse∈Z[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 deﬁnition.

Example 4.The only units inZare±1. 2 2 Let us ﬁnd the units inZ[i]a. If +bi (a,b∈Z) 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 a−ab+b=1, i.e. 2 2 2 (2a−b) +3b=4and he result follows. Note thatwequals−(1+w).

p−1 2 Problem 1.Let p be a prime number and N= (k+1)the remainder of N upon. Determine Õ k=1 division by p.

p−1 Solution.DenoteP(x) = (1+x)(2+x). . .(p−1+x)know that. We P(x) =x−1+pQ(x)for some polynomialQ(x)with integer coefﬁcients. 2 Sincek+1= (k+i)(k−i)for eachk, we immediately obtain that p−1p−1 N=P(i)P(−i) =i−1+pQ(i) (−i)−1+pQ(−i) 4,ifp≡3 (mod 4); ≡ △ 0,otherwise.

The divisibility and congruences in an extensionKof the ringZis deﬁned in the usual way: x∈Kis divisible byy∈K(denotedy|x) if there existsz∈Ksuch thatx=yz, andx≡y(modz) if z|x−y. Since every element of a quadratic ring is divisible by every unit, the deﬁnition of the notion of a prime must be adjusted to the new circumstances.

DusˇanDjukic´:ArithmeticinExtensionsofQ

3

Deﬁnition 4.An element y of a quadratic ring K isadjointto element x (denoted y∼x) if there exists a unitesuch that y=ex.

Deﬁnition 5.A nonzero element x∈K 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 x∈K. If N(x)is a prime, then x is prime.

Proof.Suppose thatx=yz,y,z∈K. 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 deﬁnition) 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 elementx∈K. Ifxis not prime then there are nonunit elementsy,z∈Ksuch 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 x∈K can be factorized into primes.2

Problem 2.Given a nonzero and nonunit element z∈K, ﬁnd the number of equivalence classes in K modulo z.

2 Solution.LetK=Z[a], wherea=pa+q,p,q∈Z, and letz=a+ba(a,b∈Z). Ifb=0 then 2 a1+b1a≡a2+b2a(modz) if and only ifa1≡a2andb1≡b2(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 coefﬁcient atainxz(x∈K) 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 everyx∈Kthere is a uniqueX=A+Ba∈KwithA,B∈Z, 0≤A<|N(z)|/d, 0≤B<dsuch that x≡X(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 ﬁrst note that, by the above deﬁnition, the primes ofZare±2,±3,±5, etc, so the factorization into primes is not exactly unique, as e.g. 2∙3= (−2)(−3). Actually, in this case the uniqueness of factorization is true in the following wording.

Deﬁnition 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:

Deﬁnition 7.DWR means: For each a,b∈K with b6=0there exist p,q∈K 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 signiﬁcance 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 ﬁnite number of steps. A simple implication of the Euclidean algorithm is that ifpis a prime,a,b∈Kand 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=3∙3= (2+ −5)(2− −5), which are not equivalent since2± −56∼3.

Example 6.The factorizations of the element4−winZ[w]as(1−w)(3+w) = (−2−3w)(1+2w) are considered the same, since1+2w=w(1−w)∼1−wand−2−3w=−(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+bi∈Z[i](a,b∈Z) isN(a+bi) =a+band the units are±1 and±i. Therefore, all divisors of a prime elementp∈Z[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,b∈Z[i]withb6=0 there exists an elementp∈Z[i]such thatN(a−pb)<N(b). Lets,t∈Rbe such thata/b=s+ti, and lets,t∈Zbe such that|s−s| ≤1/2 and|t−t| ≤1/2. Settingp=s+tiyieldsa−pb= (s+ti)b−pb= [(s−s) + (t−t)i]b, which implies

2 2 N(a−pb) =N[(s−s) + (t−t)i]N(b) = [(s−s) + (t−t) ]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 x∈Z[i]is prime if and only if N(x)is a prime or|x|is a prime integer of the form4k−1, k∈N.

Proof.Consider an arbitrary primex=a+bi∈Z[i](a,b∈Z). 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 thatx∼morx∼n, so we may suppose w.l.o.g. thatxis a prime integer. Ifx=2 orx≡1 (mod 4), then there exist integersa,b∈Zsuch thatN(a+bi) = (a+bi)(a−bi) = 2 2 a+b=x; hencexis composite inZ[i]the other hand, if. On xis a prime integer withx≡3 (mod 4), thenxis also prime inZ[i]if. Indeed, x=uvfor some nonunit elementsu,v∈Z[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 x−1=y in integers.

5 Solution.Rewrite the equation in the formx= (y+i)(y−i). Note thatxis not even, as otherwise 2 y≡ −Thus1 (mod 4). yis even and consequently the elementsy+iandy−iare coprime in Z[i]. Since(y+i)(y−i)is a ﬁfth power, it follows thaty+iandy−iare both ﬁfth powers. Let 5 4 2 2 4 4 2 2 4 a,b∈Zbe such thaty+i= (a+bi) =a(a−10a b+5b) +b(5a−10a b+b)i. It holds that 4 2 2 4 b(5a−10a 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,v2∈Ksuch thatm= u1v1,n=u2v2,p=u1v2,q=u2v1. The proof of this fact is the same as in the case ofm,n,p,q∈Z and follows directly from the factorizations ofm,n,p,qinto primes. 2 Sincexy=z+1= (z+i)(z−i), the above fact gives us

x=u1v1

(1),

y=u2v2

(2),

z+i=u1v2

(3),

z−i=u2v1

(4)

for someu1,u2,v1,v2∈Z[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+bw∈Z[w](a,b∈Z) 2 2 2 isN(a+bw) =a−ab+band the units are±1,±wand±(1+w) =∓w.

Theorem 8.FTA holds in the ringZ[w].

Proof.By the theorem 5, it sufﬁces to show that a division with remainder is possible, i.e. for all a,b∈Z[w],b6=0 there existp∈Z[w]such thatN(a−pb)<N(b). Like in the proof for the Gaussian integers, lets,t∈Rbe such thata/b=s+ti, and lets,t∈Z be such that|s−s| ≤1/2 and|t−t| ≤1/2. Settingp=s+tigives usN(a−pb)≤3N(b)/4<N(b), implying the theorem.2

Problem 5.If p≡1(mod 6) is a prime number, prove that there exist a,b∈Zsuch that p= 2 2 a−ab+b .

Solution.It sufﬁces to show thatpis composite inZ[w]. Indeed, if there is a prime element z=a+bw∈Z[w](a,b∈Z) that dividesp, then alsoz|p=pthat. Note zandzare coprime; otherwisez|z, so there exists a unit elementewithz=ez, and hencez∼(1−w)|3, which is false. 2 2 2 2 Thereforea−ab+b=zz|p, which impliesa−ab+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,n∈Zwhich are not divisible bypsuch that 2 2 2 2 p|(2m−n) +3n=4(m−mn+n), i.e.p|(m−nw)m−nw. However,pdoes not divide any of the elements(m−nw),m−nw, so it must be composite.△

Theorem 9.Element x∈Z[w]is prime if and only if N(x)is prime or|x|is a prime integer of the form3k−1, k∈N.

Proof.Numberx=3 is composite, asN(1−w) = (1−w)(2+w) =3. Moreover, by problem 4, every prime integerp≡1 (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 ﬁrst 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!!

You may also like

### How psychoanalysis evolves ou La psychanalyse au risque du Figaro

from Une-Universite-de-la-Psychanalyse

### De vandrande djäknarne

from sojis

### Biology Answer Sheet

from iwle0

next