Topics_In_Number_Theory.pdf

Course 311: Michaelmas Term 1999

Part I: Topics in Number Theory

D. R. Wilkins

Contents

1 Topics in Number Theory 2

1.1 Subgroups of the Integers . . . . . . . . . . . . . . . . . . . . 2

1.2 Greatest Common Divisors . . . . . . . . . . . . . . . . . . . . 2

1.3 The Euclidean Algorithm . . . . . . . . . . . . . . . . . . . . . 3

1.4 Prime Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.5 The Fundamental Theorem of Arithmetic . . . . . . . . . . . . 5

1.6 The Innitude of Primes . . . . . . . . . . . . . . . . . . . . . 6

1.7 Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.8 The Chinese Remainder Theorem . . . . . . . . . . . . . . . . 8

1.9 The Euler Totient Function . . . . . . . . . . . . . . . . . . . 9

1.10 The Theorems of Fermat, Wilson and Euler . . . . . . . . . . 11

1.11 Solutions of Polynomial Congruences . . . . . . . . . . . . . . 13

1.12 Primitive Roots . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.13 Quadratic Residues . . . . . . . . . . . . . . . . . . . . . . . . 16

1.14 Quadratic Reciprocity . . . . . . . . . . . . . . . . . . . . . . 21

1.15 The Jacobi Symbol . . . . . . . . . . . . . . . . . . . . . . . . 22

1 Topics in Number Theory

1.1 Subgroups of the Integers

A subset S of the set Z of integers is a subgroup of Z if 0 2 S, x 2 S and

x + y 2 S for all x 2 S and y 2 S.

It is easy to see that a non-empty subset S of Z is a subgroup of Z if and

only if xy 2 S for all x 2 S and y 2 S.

Let m be an integer, and let mZ = fmn : n 2 Zg. Then mZ (the set of

integer multiples of m) is a subgroup of Z.

Theorem 1.1 Let S be a subgroup of Z. Then S = mZ for some non-

negative integer m.

Proof If S = f0g then S = mZ with m = 0. Suppose that S 6= f0g. Then S

contains a non-zero integer, and therefore S contains a positive integer (since

x 2 S for all x 2 S). Let m be the smallest positive integer belonging to S.

A positive integer n belonging to S can be written in the form n = qm + r,

where q is a positive integer and r is an integer satisfying 0 r < m. Then

qm 2 S (because qm = m+m++m). But then r 2 S, since r = nqm.

It follows that r = 0, since m is the smallest positive integer in S. Therefore

n = qm, and thus n 2 mZ. It follows that S = mZ, as required.

1.2 Greatest Common Divisors

Denition Let a 1 ;a 2 ;:::;a r be integers, not all zero. A common divisor

of a 1 ;a 2 ;:::;a r is an integer that divides each of a 1 ;a 2 ;:::;a r The greatest

common divisor of a 1 ;a 2 ;:::;a r is the greatest positive integer that divides

each of a 1 ;a 2 ;:::;a r . The greatest common divisor of a 1 ;a 2 ;:::;a r is denoted

by (a 1 ;a 2 ;:::;a r ).

Theorem 1.2 Let a 1 ;a 2 ;:::;a r be integers, not all zero. Then there exist

integers u 1 ;u 2 ;:::;u r such that

(a 1 ;a 2 ;:::;a r ) = u 1 a 1 + u 2 a 2 + + u r a r :

where (a 1 ;a 2 ;:::;a r ) is the greatest common divisor of a 1 ;a 2 ;:::;a r .

Proof Let S be the set of all integers that are of the form

n 1 a 1 + n 2 a 2 + + n r a r

for some n 1 ;n 2 ;:::;n r 2 Z. Then S is a subgroup of Z. It follows that

S = mZ for some non-negative integer m (Theorem 1.1). Then m is a

common divisor of a 1 ;a 2 ;:::;a r , (since a i 2 S for i = 1; 2;:::;r). Moreover

any common divisor of a 1 ;a 2 ;:::;a r is a divisor of each element of S and is

therefore a divisor of m. It follows that m is the greatest common divisor

of a 1 ;a 2 ;:::;a r . But m 2 S, and therefore there exist integers u 1 ;u 2 ;:::;u r

such that

(a 1 ;a 2 ;:::;a r ) = u 1 a 1 + u 2 a 2 + + u r a r ;

as required.

Denition Let a 1 ;a 2 ;:::;a r be integers, not all zero. If the greatest com-

mon divisor of a 1 ;a 2 ;:::;a r is 1 then these integers are said to be coprime.

If integers a and b are coprime then a is said to be coprime to b. (Thus a is

coprime to b if and only if b is coprime to a.)

Corollary 1.3 Let a 1 ;a 2 ;:::;a r be integers, not all zero, Then a 1 ;a 2 ;:::;a r

are coprime if and only if there exist integers u 1 ;u 2 ;:::;u r such that

1 = u 1 a 1 + u 2 a 2 + + u r a r :

Proof If a 1 ;a 2 ;:::;a r are coprime then the existence of the required integers

u 1 ;u 2 ;:::;u r follows from Theorem 1.2. On the other hand if there exist

integers u 1 ;u 2 ;:::;u r with the required property then any common divisor

of a 1 ;a 2 ;:::;a r must be a divisor of 1, and therefore a 1 ;a 2 ;:::;a r must be

coprime.

1.3 The Euclidean Algorithm

Let a and b be positive integers with a > b. Let r 0 = a and r 1 = b. If b

does not divide a then let r 2 be the remainder on dividing a by b. Then

a = q 1 b + r 2 , where q 1 and r 2 are positive integers and 0 < r 2 < b. If r 2

does not divide b then let r 3 be the remainder on dividing b by r 2 . Then

b = q 2 r 2 + r 3 , where q 2 and r 3 are positive integers and 0 < r 3 < r 2 . If

r 3 does not divide r 2 then let r 4 be the remainder on dividing r 2 by r 3 .

Then r 2 = q 3 r 3 + r 4 , where q 3 and r 4 are positive integers and 0 < r 4 < r 3 .

Continuing in this fashion, we construct positive integers r 0 ;r 1 ;:::;r n such

that r 0 = a, r 1 = b and r i is the remainder on dividing r i2 by r i1 for

i = 2; 3;:::;n. Then r i2 = q i1 r i1 + r i , where q i1 and r i are positive

integers and 0 < r i < r i1 . The algorithm for constructing the positive

integers r 0 ;r 1 ;:::;r n terminates when r n divides r n1 . Then r n1 = q n r n for

some positive integer q n . (The algorithm must clearly terminate in a nite

number of steps, since r 0 > r 1 > r 2 > > r n .) We claim that r n is the

greatest common divisor of a and b.

Any divisor of r n is a divisor of r n1 , because r n1 = q n r n . Moreover if

2 i n then any common divisor of r i and r i1 is a divisor of r i2 , because

r i2 = q i1 r i1 + r i . If follows that every divisor of r n is a divisor of all the

integers r 0 ;r 1 ;:::;r n . In particular, any divisor of r n is a common divisor of

a and b. In particular, r n is itself a common divisor of a and b.

If 2 i n then any common divisor of r i2 and r i1 is a divisor of r i ,

because r i = r i2 q i1 r i1 . It follows that every common divisor of a and b

is a divisor of all the integers r 0 ;r 1 ;:::;r n . In particular any common divisor

of a and b is a divisor of r n . It follows that r n is the greatest common divisor

of a and b.

There exist integers u i and v i such that r i = u i a + v i b for i = 1; 2;:::;n.

Indeed u i = u i2 q i1 u i1 and v i = v i2 q i1 v i1 for each integer i between 2

and n, where u 0 = 1, v 0 = 0, u 1 = 0 and v 1 = 1. In particular r n = u n a+v n b.

The algorithm described above for calculating the greatest common di-

visor (a;b) of two positive integers a and b is referred to as the Euclidean

algorithm. It also enables one to calculate integers u and v such that (a;b) =

ua + vb.

Example We calculate the greatest common divisor of 425 and 119. Now

425 = 3 119 + 68

119 = 68 + 51

68 = 51 + 17

51 = 3 17:

It follows that 17 is the greatest common divisor of 425 and 119. Moreover

17 = 68 51 = 68 (119 68)

= 2 68 119 = 2 (425 3 119) 119

= 2 425 7 119:

1.4 Prime Numbers

Denition A prime number is an integer p greater than one with the prop-

erty that 1 and p are the only positive integers that divide p.

Let p be a prime number, and let x be an integer. Then the greatest

common divisor (p;x) of p and x is a divisor of p, and therefore either (p;x) =

p or else (p;x) = 1. It follows that either x is divisible by p or else x is coprime

to p.

Theorem 1.4 Let p be a prime number, and let x and y be integers. If p

divides xy then either p divides x or else p divides y.

Proof Suppose that p divides xy but p does not divide x. Then p and x

are coprime, and hence there exist integers u and v such that 1 = up + vx

(Corollary 1.3). Then y = upy + vxy. It then follows that p divides y, as

required.

Corollary 1.5 Let p be a prime number. If p divides a product of integers

then p divides at least one of the factors of the product.

Proof Let a 1 ;a 2 ;:::;a k be integers, where k > 1. Suppose that p divides

a 1 a 2 a k . Then either p divides a k or else p divides a 1 a 2 a k1 . The

required result therefore follows by induction on the number k of factors in

the product.

1.5 The Fundamental Theorem of Arithmetic

Lemma 1.6 Every integer greater than one is a prime number or factors as

a product of prime numbers.

Proof Let n be an integer greater than one. Suppose that every integer m

satisfying 1 < m < n is a prime number or factors as a product of prime

numbers. If n is not a prime number then n = ab for some integers a and

b satisfying 1 < a < n and 1 < b < n. Then a and b are prime numbers or

products of prime numbers. It follows that n is a prime number or a product

of prime numbers. The required result therefore follows by induction on

An integer greater than one that is not a prime number is said to be a

composite number.

Let n be an composite number. We say that n factors uniquely as a prod-

uct of prime numbers if, given prime numbers p 1 ;p 2 ;:::;p r and q 1 ;q 2 ;:::;q s

such that

n = p 1 p 2 p r = q 1 q 2 :::;q s ;

the number of times a prime number occurs in the list p 1 ;p 2 ;:::;p r is equal

to the number of times it occurs in the list q 1 ;q 2 ;:::;q s . (Note that this

implies that r = s.)

Theorem 1.7 (The Fundamental Theorem of Arithmetic) Every composite

number greater than one factors uniquely as a product of prime numbers.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: