Contents Principal Ideal Domain and Unique Prime Factorization

GAUSSIAN INTEGERS

HUNG HO

Abstract. We will investigate the ring of "Gaussian integers" Z[i] = {a + bi | a, b Z}. First we will show that this ring shares an important property with the ring of integers: every element can be factored into a product of finitely many "primes". This result is the key to all the remaining concepts in this paper, which includes the ring Z[i]/Z[i], analogous statements of famous theorems in Z, and quadratic reciprocity laws.

Contents

1. Principal Ideal Domain and Unique Prime Factorization

1

2. The ring Z[i]

6

3. Some Applications of Unique Prime Factorization in Z[i]

8

4. Congruence Classes in Z[i]

11

5. Some important theorems and results

13

6. Quadratic Reciprocity

18

Acknowledgement

22

References

22

1. Principal Ideal Domain and Unique Prime Factorization

Definition 1.1. A ring R is called an integral domain, or domain, if 1 = 0 and whenever a, b R and ab = 0, then either a = 0 or b = 0.

Example 1.2. Z, Q, R, C are all integral domains.

Example 1.3. The ring Z[i] = {a + bi : a, b Z} is an integral domain.

Example 1.4. The ring Z/nZ is a domain if and only if n is a prime. This is because if n is not a prime then we can write n = ab where a, b Z \ {1} and thus ab = 0 in Z/nZ. Conversely, if n is a prime then n divides ab if and only if n divides either a or b, so a = 0 or b = 0 in Z/nZ.

Definition 1.5. An ideal I of a commutative ring R is principal if it is generated by a single element a of R through multiplication by every element of R. In other words, I = Ra = {ra : r R}. It is common to denote the ideal generated by a as (a).

Example 1.6. The set of even integers is a principal ideal of Z generated by 2.

Definition 1.7. A principal ideal domain is a domain in which every ideal is principal.

1

2

HUNG HO

Definition 1.8. Let a, b be elements of the commutative ring R. If there exists x R such that a = bx then we say that b divides a, or a is divisible by b and write b | a. b is called a divisor of a and a is a multiple of b. Elements a and b of an integral domain are associates if a | b and b | a. An element u is a unit if u divides every element of R, or equivalently, u divides 1.

We can restate the above claims about divisibility and unit in terms of principal ideals. From now on, we always assume R to be a commutative ring and an integral domain.

Proposition 1.9. Let a, b R, then b divides a if and only if (a) (b).

Proof. If b divides a, we write a = bx for some x R. Then for any y (a), we have y = at for some t R, or y = bxt and thus y (b). Conversely, if (a) (b), then obviously a (b) so a = bx for some x R, so b divides a.

Corollary 1.10. An element u is a unit if and only if (u) = (1) = R.

Corollary 1.11. The following are equivalent:

(1) a and b are associates. (2) a = bu for some unit u. (3) (a) = (b).

Definition 1.12. An element p of the commutative ring R is called prime if p {0, 1} and whenever p divides ab for a, b R, then either p divides a or p divides b.

Definition 1.13. A non-zero non-unit element p in an integral domain is irreducible if it is not the product of two non-zero units.

In the ring of integers Z, prime and irreducible elements are equivalent and are

called interchangeably as prime numbers. In general, however, these two definitions do not coincide. For example, consider the ring Z -5 = {a + b -5 : a, b Z}.

It is easy to check that this ring is an integral domain (because it is a subset of

the complexnumbers). The element 2 is irreducible b -5)(c+d -5), taking absolute value of both sides

in Z yields

-5 4=

because if 2 = (a + (a2 +5b2)(c2 +5d2).

This is only possible if b = d = 0, hence |ac| =2, where a, c Z, so either |a| or |c| must be 1. Therefore either a + b -5 or c + d -5 is a unit inZ -5. On the other hand, 2 is not a prime in Z -5 since 2 divides 4 = (-1 + -5)(1 + -5) but 2 neither divides 1 + -5 nor -1 + -5 (an integer divides a number a + b -5 in Z -5 if and only if it divides both a and b).

The example above shows that in an integral domain, irreducible elements are not

necessarily primes, but what about the reverse statement? The following theorem

addresses this issue.

Theorem 1.14. If p is a prime element in an integral domain R, then p is irreducible.

Proof. Assume p = 0 is a prime but not irreducible in R, then there exists x, y R that are not units such that p = xy. Since p is a prime element, it follows that p | x or p | y. Without loss of generality, suppose p | x, then x = pt for some t R. Thus, we can write p = pty. Since R is an integral domain and p = 0, we deduce that ty = 1, or y divides 1, so y is a unit, a contradiction.

If R is a principal ideal domain, then the reverse direction is also true. However, before tackling this property, we need some more notions.

GAUSSIAN INTEGERS

3

Definition 1.15. Let a, b be two nonzero elements of R. An element d R is called a greatest common divisor of a and b if d is a divisor of both a and b, and any common divisor of a and b divides d.

Later on we will show that any two greatest common divisors of two elements are associates of each other, hence from now on we will use the notation gcd(a, b) and the term "the greatest common divisor" to denote any of those associates. However, in a general integral domain, two elements need not have a greatest common divisor. In fact, a domain in which every two elements have a greatest common divisor is called a GCD domain. We will show that every principal ideal domain is also a GCD domain. For elements a1, a2, . . . , an R, we define (a1, a2, . . . , an) = Ra1+Ra2+. . .+Ran =

n

{ riai | ri R}. It is easy to see that (a1, a2, . . . , an) is also an ideal of R .

i=1

Theorem 1.16. Let R be a principal ideal domain and a, b be nonzero elements of R. Then there exists d = gcd(a, b) and (a, b) = (d).

Proof. Let I = (a, b) be an ideal of R. Since R is a principal ideal domain, we have I = (d) for some d R. Because (a), (b) (a, b) = (d), we deduce that d divides both a and b. Now let d be any common divisor of a and b and write a = d a , b = d b . Since d (a, b), we can also write d = au + bv for some u, v R. Thus, we have d = d (a u + b v), so d | d. Therefore, d is the greatest common divisor of a and b.

Two elements a and b may have more than one greatest common divisor. If d and d are both greatest common divisors of a and b, we can deduce from the definition that d | d and d | d. Hence, any two greatest common divisors are associates of each other. If gcd(a, b) = u, where u is a unit, then a and b are relatively prime. It follows from theorem 1.16 that if a and b are relatively prime, then (a, b) = R.

Corollary 1.17. Let a, b, c R and a | bc. If (a, b) = R, then a | c.

Proof. Since (a, b) = R, there exists x, y R such that ax + by = 1. We have

bc = ak

ybc = yak

c(1 - ax) = yak

c = a(cx + yk).

Thus, a divides c.

Corollary 1.18. If p is irreducible in a principal ideal domain R, then p is a prime element.

Proof. Suppose p divides ab for some a, b R. Let pa = gcd(p, a). If pa is a unit, then p and a are relatively prime and we conclude from corollary 1.17 that p divdes b. If pa is not a unit, we write p = pau and since p is irreducible, it follows that u is a unit. So p and pa are associates, hence p divides a.

From now on, we will not distinguish irreducible and prime elements.

Recall that every positive integer can be uniquely factored into a product of primes (we only consider positive primes). We want to prove a similar result in a

4

HUNG HO

principal ideal domain, that is, every element can be factored into product of prime elements. However, this factorization, provided it exists, may not be unique as we can see via this simple example in Z: 4 = 2 ? 2 = (-2) ? (-2). But this example also shows that in Z, if a number can be factored into different products of primes, then we can find corresponding primes in these products that are associates of each other (2 and -2 in the above example). Therefore, when talking about unique prime factorization in a general principal ideal domain, we understand that it is "unique up to associates". We will now go on to prove that every element in a principal ideal domain can be factored into irreducible (or prime) elements. The intuition is as followed. Given any element a, if a is irreducible then we are done. If not, then we can write a = bc, where b, c are non-units. Now if either b or c is not irreducible, we proceed similarly to factor that element into another two elements. Eventually, if this process terminates after finitely many steps, we have our desired factorization. However, if this process goes on forever, then we have a problem. We will prove that this cannot happen.

Proposition 1.19. Let a be a non-zero non-unit element of a principal ideal domain R. Then a can be factored into a product of finitely many irreducible elements.

Proof. First we show that every non-zero non-unit element x has an irreducible

divisor. Assume otherwise, then obviously x is not irreducible itself, so we can

write x = x1y1. Since x has no irreducible divisor, we can again factor x1 = x2y2, where x2, y2 are also not irreducible. Proceed inductively, we have two infinite sequences of (xn) and (yn) in R such that all of the terms are not irreducible and xn-1 = xnyn. Thus, (x1) (x2) . . . (the strict subset sign is due to the fact that yn is not irreducible for all n, so an is not an associate of an-1).

Now let I = . We claim that I is an ideal of R. Indeed, it is obvious that (I, +)

n=1

is a subgroup of (R, +). For any t I, r R, since t belongs to (xi) for some i, so does rt, hence rt I. Thus, I is an ideal and we deduce from the fact that R is a

principal ideal domain that I = (b) for some b R. Since xn (b) = I, we have b divides xn for all n. On the other hand, b (xk) for some k, or xk divides b. Hence, b and xk are associates. But then this implies that xk divides xk+1, which implies (xk+1) (xk) (xk+1), a contradiction. So every non-zero non-unit element has an irreducible divisor.

Now consider an arbitrary non-zero non-unit a R. If a is irreducible, we are done.

If not, we can factor a = a1b1, where a1 is irreducible. Since a is not irreducible, b1 is not a unit (otherwise a and a1 are associates), hence b1 has an irreducible divisor a2. We write b1 = a2b2, and apply the same argument for b2. Proceed inductively, if bn is not a unit, we factor it into an+1bn+1, where an+1 is irreducible. Eventually, if we stop at some N0 where bN0 is a unit, then bN0-1 is irreducible and a = a1a2 . . . aN0-1bN0-1 is our desired factorization. Otherwise, if we do not stop at some N0, then we have an infinite sequence of ideals (b1), (b2), . . . such that (b1) (b2) . . . (an is non-unit for all n so bn-1 and bn are not associates). Now repeat the proof as above, we have a contradiction, so we must stop after finitely

many steps, and thus a can be factored into a product of irreducible elements.

GAUSSIAN INTEGERS

5

Now we know that any non-zero non-unit element can be factored into a product of irreducibles. To prove that his factorization is unique up to associates, we need the following simple lemma.

Lemma 1.20. Let a, b be two irreducible elements of a principal ideal domain R. Then a and b are relatively prime if and only if they are not associates.

Proof. The forward direction is obvious because two associates divide each other. For the reverse direction, assume a and b are not relatively prime, let d be their greatest common divisor. Write a = da and b = db . Since a and b are irreducibles and d is not a unit, it follows that a and b are units. Thus, d is an associate of both a and b, so a and b are associates, a contradiction.

From now on, if a and b are not associates, we say that a and b are distinct.

Theorem 1.21. Let a be a non-zero element of a PID R. Then we can write

k

a = u pi i ,

i=1

where u is a unit, pi's are pairwise distinct irreducibles that are unique up to associates, and the exponents i's are uniquely determined.

Proof. The existence of such factorization follows from proposition 1.19. Now as-

k

l

sume that we have two factorizations a = u pi i = v qii . For each i =

i=1

i=1

l

1, 2, . . . , k, pi divides qii , so from lemma 1.20 and corollary 1.18, there must

i=1

exists j {1, 2, . . . , l} such that qj and pi are associates. Thus, we can map each

pi to its associate qj, and apparently this is a one-to-one map because two distinct

irreducibles have distinct associates. But we can also repeat the argument and

deduce that for any qj, there exists a corresponding associate pi, hence our map is

an isomorphism. Therefore, k = l, and Without loss of generality, we can assume

that pi and qi are associates for i = 1, 2, . . . , k.

It remains to show that i = i for every i. Assume otherwise and without loss

of generality, there exists i0 such that i0 > i0 . Since R is an integral domain,

we deduce that u

p p i i0 -i0

i i0

=v

qii , so pi0 divides qj for some j = i0, a

i=i0

i=i0

contradiction. Therefore, i = i for all i, and thus the theorem is proven.

Definition 1.22. An Euclidean domain R is an integral domain equipped with a function f from R \ {0} to {0, 1, 2, . . . , } such that if a, b R and b is nonzero, then we can write a = bq + r for q R, and either r = 0 or f (r) < f (b).

The main reason to define Euclidean domain is the following proposition.

Proposition 1.23. Assume R be an Euclidean domain. Then R is a principal ideal domain.

Proof. Let I be an ideal of R, we shall prove that there exists a R such that I = Ra. Indeed, let a be a nonzero element of I such that f (a) is minimum (the existence of such element follows from the fact that the function f takes values on the set of non-negative integers). Now, consider any b I, we can write b = aq + r with q, r R. Since f (a) is minimum, we cannot have f (r) < f (a), so for all b I,

6

HUNG HO

b = aq for some q R and thus I Ra. On the other hand, obviously Ra I because I is an ideal. Hence, I = Ra.

Proposition 1.23 is important because we may show a ring R is a PID by first proving it is an Euclidean domain. We will conclude the first section with an important result: the Chinese remainder theorem.

Definition 1.24. Two ideals I and J are coprime if there exists i I and j J such that i + j = 1.

Remarks 1.25. By theorem 1.16, we know that in a principal ideal domain R, two ideals (a) and (b) are coprime if and only if a and b are relatively prime.

Theorem 1.26. Let I1, I2, . . . , Ik be ideals of a ring R that are pairwise coprime.

k

Denote I = Ii. We have the isomorphism

i=1

R/I R/I1 ? . . . ? R/Ik

x + I (x + I1, . . . , x + Ik).

Proof. It suffices to prove for k = 2, as the general case can be proved similarly using induction. We want to show that for any x1, x2 R one can find x I such that x x1 mod I1 and x x2 mod I2. Since I1 and I2 are coprime, there exists y1 I1 and y2 I2 such that -y1 + y2 = x1 - x2. Let z = y1 + x1 = y2 + x2, then apparently z R and z - x1 I1, z - x2 I2. Thus z x1 mod I1 and z x2 mod I2.

2. The ring Z[i]

Most of this paper is devoted to reproduce many well-known concepts and results from Z in the ring Z[i] = {a + bi | a, b Z}. First and foremost, we will show that Z[i] is a principal ideal domain and thus inherits the unique prime factorization property.

Proposition 2.1. Z[i] is a Euclidean domain.

Proof. For each = a + bi Z[i] \ {0}, we define f () = = a2 + b2. Take an

arbitrary = c + di Z[i], we will show that = + for Z[i] and either

= 0 or f () < f ().

Indeed,

let

=

r + si,

where

r, s

Q.

Let

k

be

the

closest

integer

to

r

and

l

be

the

closest

integer

to

s,

i.e.

|k - r|

1 2

and

|l - s|

1 2

.

Let

=

k+li, m

=

r-k, n

=

s-l

and = (a + bi)(m + ni), we have:

c + di = (a + bi)(r + si) = (a + bi)(k + li) + (a + bi)(m + ni)

= + .

If = 0 then = , as desired. Otherwise, we have f () = = (a2 + b2)(m2 +

n2)

(a2

+

b2)(

1 4

+

1 4

)

<

f ().

Thus, Z[i] is a Euclidean domain with the function f defined as f () = .

Proposition 2.1 is fundamental to the study of the ring Z[i] as we can relate many results and properties in Z[i] to their counterparts in Z. However, after we proved that Z[i] is a unique prime factorization domain, a natural question arises:

GAUSSIAN INTEGERS

7

"What are primes in Z[i]?. Primes in Z[i] may have some similarities with primes in Z but apparently they are not the same, as we can see, for instance, that 5 is a prime in Z but not a prime in Z[i] because 5 = (2 - i)(2 + i).

Lemma

2.2.

Let

p

=

4k + 1

be

a

positive

prime,

then

(

p-1 2

)!2

+

1

is

divisible

by

p.

Proof. Since for any x {0, 1, . . . , 2k}, x (-1)(p - x) mod p, it follows that

( p - 1 )! (-1)2k(p - 1)(p - 2) . . . (p + 1) mod p.

2

2

Hence

(

p-1 2

)!2

(p

-

1)!

-1

mod p (the second congruence is due to Wilson's

theorem).

Lemma 2.3. Let p = 4k + 3 be a positive prime and a, b N such that a2 + b2 is divisible by p. Then both a and b are divisible by p.

Proof. We have a2 -b2

a2(2k+1) (-b2)(2k+1) ap-1 -bp-1

mod p mod p mod p.

Now if a is not divisible by p, so is b because a2 + b2 is divisible by p. But then by the Fermat's little theorem, ap-1 bp-1 1 mod p. Thus, by the above congruence equations, it follows that 2ap-1 is divisible by p, or a is divisible by p,

a contradiction. Thus both a and b are divisible by p.

Corollary 2.4. Let p be a prime in Z, then there exists x Z such that x2 + 1 is divisible by p if and only if |p| = 4k + 1.

Theorem 2.5. A Gaussian integer = a + bi is a prime if and only if it falls in one of the following categories:

(1) a = 0 and |b| is a prime number of the form 4k + 3. (2) b = 0 and |a| is a prime number of the form 4k + 3. (3) a2 + b2 is a prime number.

Proof. First, we prove that all Gaussian integers described in (1), (2), (3) are prime.

(1) We will prove for the case b > 0, the case b < 0 is proved similarly. Let b = 4k + 3 (k 0) be a prime and assume is not a prime in Z[i]. Then we can write bi = (u + vi)(x + yi), where u + vi and x + yi are not units. We deduce that b2 = (u2 + v2)(x2 + y2). Since b is a prime, either u2 + v2 or x2 + y2 is divisible by b. Without loss of generality, assume u2 + v2 is divisible by b. Now because b = 4k + 3, it follows from lemma 2.3 that both u and v are divisible by b. But then both u2 and v2 are divisible by b2, and thus u2 + v2 b2. Now we can conclude from x2 + y2 > 1 that (u2 + v2)(x2 + y2) > b2, a contradiction. Hence is a prime.

(2) The proof is similar to that of (1).

8

HUNG HO

(3) Assume that is not a prime, then by similar argument we can write a + bi = (u + vi)(x + yi), where u2 + v2 and x2 + y2 are both greater than 1. We also have a2 + b2 = (u2 + v2)(x2 + y2), which implies that (u2 + v2)(x2 + y2) is a prime number. However, this is impossible because the product of two numbers greater than 1 can never be a prime number in Z, thus must be a prime in Z[i].

Conversely, we prove that every prime element of Z[i] belongs to one of the above three categories. Observe that = a + bi is a prime in Z[i] if and only if = a - bi is also a prime in Z[i] (because a + bi = (u + vi)(x + yi) a - bi = (u - vi)(x - yi), where u2 + v2 and x2 + y2 are both greater than 1). Also, it is obvious that if both a and b are nonzero, they must be relatively prime in Z[i]. Now we look at q = a2 + b2 = (a + bi)(a - bi). Consider the following cases:

(a) q is even. We have (a + bi)(a - bi) is divisible by 2 = (1 + i)(1 - i). Note that both 1 + i and 1 - i are primes due to our proof for (3) above. So either a + bi or a - bi is divisible by 1 + i, and because they are all primes in Z[i], we must have a + bi = u(1 + i), where u is a unit. Thus, a - bi = u(1 - i) and finally a2 + b2 = 2, which is a prime. So falls in category 3.

(b) q has a prime divisor p with absolute value of the form 4k + 3. Then by lemma 2.3, both a and b are divisible by p and thus, a2 + b2 is divisible by p2 (in both Z and Z[i]). Since both a + bi and a - bi are primes in Z[i], each of them cannot be divisible by p2, so we deduce that both a + bi and a - bi are divisible by p. However, this implies that their sum 2a, and their difference 2bi, are also divisible by p in Z[i]. Since 2 and p are relatively prime in Z[i] because p = 4k + 3, it follows that both a and b are divisible by p. This is impossible if a and b are coprime, so one of them must be zero. If a = 0, let b = pk, then for = pki to be a prime in Z[i], |k| must be equal to 1, hence is in category 1. Similarly, if b = 0 then we can also deduce that is in category 2.

(c) All prime divisors of q have absolute values of the form 4k + 1. First we show that if |p| is a prime in Z of the form 4k + 1, then p is not a prime in Z[i]. Indeed, assume othrewise, p is also a prime in Z[i]. according to corollary 2.4, there exists x Z such that p | x2 + 1 = (x + i)(x - i). Since p is a prime, it follows that either x + i or x - i is divisible by p in Z[i]. Without loss of generality, assume x + i = p(r + si), then we deduce that 1 = ps, a contradiction, hence p is not a prime in Z[i]. Now assume for the sake of contradiction that q is not a prime itself, then there exist primes p1, p2 in Z (p1 and p2 are not necessarily distinct) such that q is divisible by p1p2. Because both p1 and p2 are of the form 4k + 1 and hence are not primes in Z[i], we know that p1p2 is a product of at least four primes in Z[i]. This is impossible because p1p2 divides (a + bi)(a - bi), which is a product of two primes. Therefore, q = a2 + b2 is a prime in Z.

3. Some Applications of Unique Prime Factorization in Z[i]

An important corollary of theorem 2.5 is the following theorem that characterize the necessary and sufficient condition to express a prime as a sum of two squares in N.

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download