2

5

as

√ √

n n

1 1+ 5 1’ 5

Fn = √ ’ . This will be shown later.

2 2

5

1.6 Prime Numbers

A natural number p is a prime iff p > 1 and p has no proper divisors.

Theorem 1.3. Any natural number n > 1 is a prime or a product of primes.

Proof. If n is a prime then we are ¬nished. If n is not prime then n = n1 · n2 with n1

and n2 proper divisors. Repeat with n1 and n2 .

Theorem 1.4 (Euclid). There are in¬nitely many primes.

Proof. Assume not. Then let p1 , p2 , . . . , pn be all the primes. Form the number N =

p1 p2 . . . pn + 1. Now N is not divisible by any of the pi ” but N must either be prime

or a product of primes, giving a contradiction.

This can be made more precise. The following argument of Erd¨ s shows that the k th

o

k’1

smallest prime pk satis¬es pk ¤ 4 + 1. Let M be an integer such that all numbers

¤ M can be written as the product of the powers of the ¬rst k primes. So any such

number can be written

m2 pi1 pi2 . . . pik ,

12 k

√ √

with i1 , . . . , ik ∈ {0, 1}. Now m √ M , so there are at most M 2k possible num-

¤

bers less than M . Hence M ¤ 2k M , or M ¤ 4k . Hence pk+1 ¤ 4k + 1.

A much deeper result (which will not be proved in this course!) is the Prime Num-

ber Theorem, that pk ∼ k log k.

1.7. APPLICATIONS OF PRIME FACTORISATION 7

1.6.1 Uniqueness of prime factorisation

Lemma 1.9. If p | ab, a, b ∈ N then p | a and/or p | b.

Proof. If p a then (p, a) = 1 and so p | b by theorem (1.2).

Theorem 1.5. Every natural number > 1 has a unique expression as the product of

primes.

Proof. The existence part is theorem (1.3). Now suppose n = p1 p2 . . . pk = q1 q2 . . . ql

with the pi ™s and qj ™s primes. Then p1 | q1 . . . ql , so p1 = qj for some j. By renumber-

ing (if necessary) we can assume that j = 1. Now repeat with p2 . . . pk and q2 . . . ql ,

which we know must be equal.

There are perfectly nice algebraic systems where the decomposition into primes

√ √

is not unique, for instance Z ’5 = {a + b ’5 : a, b ∈ Z}, where 6 = (1 +

√ √ √

’5)(1 ’ ’5) = 2 — 3 and 2, 3 and 1 ± ’5 are each “prime”. Or alternatively,

2Z = {all even numbers}, where “prime” means “not divisible by 4”.

1.7 Applications of prime factorisation

√

Lemma 1.10. If n ∈ N is not a square number then n is irrational.

√

Proof. Suppose n = a , with (a, b) = 1. Then nb2 = a2 . If b > 1 then let p be a

b

prime dividing b. Thus p | a2 and so p | a, which is impossible as (a, b) = 1. Thus

b = 1 and n = a2 .

√ √

This lemma can also be stated: “if n ∈ N with n ∈ Q then n ∈ N”.

De¬nition. A real number θ is algebraic if it satis¬es a polynomial equation with co-

ef¬cients in Z.

Real numbers which are not algebraic are transcendental (for instance π and e).

Most reals are transcendental.

If the rational a ( with (a, b) = 1 ) satis¬es a polynomial with coef¬cients in Z

b

then

cn an + cn’1 an’1 b + . . . bn c0 = 0

so b | cn and a | c0 . In particular if cn = 1 then b = 1, which is stated as “algebraic

integers which are rational are integers”.

Note that if a = p±1 p±2 . . . p±k and b = pβ1 pβ2 . . . pβk with ±i , βi ∈ N0 then

1 2 12

k k

γ1 γ2 γk δk

δ1 δ2

(a, b) = p1 p2 . . . pk and [a, b] = p1 p2 . . . pk , γi = min{±i , βi } and δi =

max{±i , βi }.

Major open problems in the area of prime numbers are the Goldbach conjecture

(“every even number greater than two is the sum of two primes”) and the twin primes

conjecture (“there are in¬nitely many prime pairs p and p + 2”).

CHAPTER 1. INTEGERS

8

1.8 Modular Arithmetic

De¬nition. If a and b ∈ Z, m ∈ N we say that a and b are “congruent mod(ulo) m”

if m | a ’ b. We write a ≡ b (mod m).

It is a bit like = but less restrictive. It has some nice properties:

• a ≡ a (mod m),

• if a ≡ b (mod m) then b ≡ a (mod m),

• if a ≡ b (mod m) and b ≡ c (mod m) then a ≡ c (mod m).

Also, if a1 ≡ b1 (mod m) and a2 ≡ b2 (mod m)

• a1 + a2 ≡ b1 + b2 (mod m),

• a1 a2 ≡ b1 a2 ≡ b1 b2 (mod m).

Lemma 1.11. For a ¬xed m ∈ N, each integer is congruent to precisely one of the

integers

{0, 1, . . . , m ’ 1}.

Proof. Take a ∈ Z. Then a = qm + r for q, r ∈ Z and 0 ¤ r < m. Then a ≡ r

(mod m).

If 0 ¤ r1 < r2 < m then 0 < r2 ’ r1 < m, so m r2 ’ r1 and thus r1 ≡ r2

(mod m).

Example. No integer congruent to 3 (mod 4) is the sum of two squares.

Solution. Every integer is congruent to one of 0, 1, 2, 3 (mod 4). The square of any

integer is congruent to 0 or 1 (mod 4) and the result is immediate.

Similarly, using congruence modulo 8, no integer congruent to 7 (mod 8) is the

sum of 3 squares.

1.9 Solving Congruences

We wish to solve equations of the form ax ≡ b (mod m) given a, b ∈ Z and m ∈ N

for x ∈ Z. We can often simplify these equations, for instance 7x ≡ 3 (mod 5)

reduces to x ≡ 4 (mod 5) (since 21 ≡ 1 and 9 ≡ 4 (mod 5)).

This equations are not always soluble, for instance 6x ≡ 4 (mod 9), as 9 6x ’ 4

for any x ∈ Z.

How to do it

The equation ax ≡ b (mod m) can have no solutions if (a, m) b since then m ax’b

for any x ∈ Z. So assume that (a, m) | b.

We ¬rst consider the case (a, m) = 1. Then we can ¬nd x0 and y0 ∈ Z such

that ax0 + my0 = b (use the Euclidean algorithm to get x and y ∈ Z such that

ax + my = 1). Then put x0 = bx so ax0 ≡ b (mod m). Any other solution is

congruent to x0 (mod m), as m | a(x0 ’ x1 ) and (a, m) = 1.

So if (a, m) = 1 then a solution exists and is unique modulo m.

1.10. EULER™S PHI FUNCTION 9

1.9.1 Systems of congruences