x ≡ a mod m

x ≡ b mod n.

Our main tool will be the Chinese Remainder Theorem.

Theorem 1.6 (Chinese Remainder Theorem). Assume m, n ∈ N are coprime and

let a, b ∈ Z. Then ∃x0 satisfying simultaneously x0 ≡ a (mod m) and x0 ≡ b

(mod n). Moreover the solution is unique up to congruence modulo mn.

Proof. Write cm + dn = 1 with m, n ∈ Z. Then cm is congruent to 0 modulo m

and 1 modulo n. Similarly dn is congruent to 1 modulo m and 0 modulo n. Hence

x0 = adn + bcm sati¬es x0 ≡ a (mod m) and x0 ≡ b (mod n). Any other solution

x1 satis¬es x0 ≡ x1 both modulo m and modulo n, so that since (m, n) = 1, mn |

x0 ’ x1 and x1 ≡ x0 (mod mn).

Finally, if 1 < (a, m) then replace the congruence with one obtained by dividing

by (a, m) ” that is consider

a b m

x≡ mod .

(a, m) (a, m) (a, m)

Theorem 1.7. If p is a prime then (p ’ 1)! ≡ ’1 (mod p).

Proof. If a ∈ N, a ¤ p ’ 1 then (a, p) = 1 and there is a unique solution of ax ≡ 1

(mod p) with x ∈ N and x ¤ p ’ 1. x is the inverse of a modulo p. Observe that

a = x iff a2 ≡ 1 (mod p), iff p | (a + 1)(a ’ 1), which gives that a = 1 or p ’ 1.

Therefore the elements in {2, 3, 4, . . . , p’2} pair off so that 2—3—4—· · ·—(p’2) ≡ 1

(mod p) and the theorem is proved.

1.10 Euler™s Phi Function

De¬nition. For m ∈ N, de¬ne φ(m) to be the number of nonnegative integers less

than m which are coprime to m.

1

φ(1) = 1. If p is prime then φ(p) = p ’ 1 and φ(pa ) = pa 1 ’ .

p

Lemma 1.12. If m, n ∈ N with (m, n) = 1 then φ(mn) = φ(m)φ(n). φ is said to be

multiplicative.

Let Um = {x ∈ Z : 0 ¤ x < m, (x, m) = 1, the reduced set of residues or set of

invertible elements. Note that φ(m) = |Um |.

Proof. If a ∈ Um and b ∈ Un then there exists a unique x ∈ Umn . with c ≡ a

(mod m) and c ≡ b (mod n) (by theorem (1.6)). Such a c is prime to mn, since it

is prime to m and to n. Conversely, any c ∈ Umn arises in this way, from the a ∈ Um

and b ∈ Un such that a ≡ c (mod m), b ≡ c (mod n). Thus |Umn | = |Um | |Un | as

required.

CHAPTER 1. INTEGERS

10

An immediate corollary of this is that for any n ∈ N,

1

φ(n) = n 1’ .

p

p|n

p prime

Theorem 1.8 (Fermat-Euler Theorem). Take a, m ∈ N such that (a, m) = 1. Then

aφ(m) ≡ 1 (mod m).

Proof. Multiply each residue ri by a and reduce modulo m. The φ(m) numbers thus

obtained are prime to m and are all distinct. So the φ(m) new numbers are just

r1 , . . . , rφ(m) in a different order. Therefore

r1 r2 . . . rφ(m) ≡ ar1 ar2 . . . arφ(m) (mod m)

≡ aφ(m) r1 r2 . . . rφ(m) (mod m).

Since (m, r1 r2 . . . rφ(m) ) = 1 we can divide to obtain the result.

Corollary (Fermat™s Little Theorem). If p is a prime and a ∈ Z such that p a then

ap’1 ≡ 1 (mod p).

This can also be seen as a consequence of Lagrange™s Theorem, since Um is a group

under multiplication modulo m.

Fermat™s Little Theorem can be used to check that n ∈ N is prime. If ∃a coprime

to n such that an’1 ≡ 1 (mod n) then n is not prime.

1.10.1 Public Key Cryptography

Private key cryptosystems rely on keeping the encoding key secret. Once it is known

the code is not dif¬cult to break. Public key cryptography is different. The encoding

keys are public knowledge but decoding remains “impossible” except to legitimate

users. It is usually based of the immense dif¬culty of factorising suf¬ciently large

numbers. At present 150 “ 200 digit numbers cannot be factorised in a lifetime.

We will study the RSA system of Rivest, Shamir and Adleson. The user A (for

Alice) takes two large primes pA and qA with > 100 digits. She obtains NA = pA qA

and chooses at random ρA such that (ρA , φ(NA )) = 1. We can ensure that pA ’ 1 and

qA ’ 1 have few factors. Now A publishes the pair NA and ρA .

By some agreed method B (for Bob) codes his message for Alice as a sequence of

numbers M < NA . Then B sends A the number M ρA (mod NA ). When Alice wants

to decode the message she chooses dA such that dA ρA ≡ 1 (mod φ)(NA ). Then

M ρA dA ≡ M (mod NA ) since M φ(NA ) ≡ 1. No-one else can decode messages to

Alice since they would need to factorise NA to obtain φ(NA ).

If Alice and Bob want to be sure who is sending them messages, then Bob could

send Alice EA (DB (M )) and Alice could apply EB DA to get the message ” if it™s

from Bob.

Chapter 2

Induction and Counting

2.1 The Pigeonhole Principle

Proposition (The Pigeonhole Principle). If nm + 1 objects are placed into n boxes

then some box contains more than m objects.

Proof. Assume not. Then each box has at most m objects so the total number of objects

is nm ” a contradiction.

A few examples of its use may be helpful.

Example. In a sequence of at least kl+1 distinct numbers there is either an increasing

subsequence of length at least k+1 or a decreasing subsequence of length at least l+1.

Solution. Let the sequence be c1 , c2 , . . . , ckl+1 . For each position let ai be the length

of the longest increasing subsequence starting with ci . Let dj be the length of the

longest decreasing subsequence starting with cj . If ai ¤ k and di ¤ l then there are

only at most kl distinct pairs (ai , dj ). Thus we have ar = as and dr = ds for some

1 ¤ r < s ¤ kl + 1. This is impossible, for if cr < cs then ar > as and if cr > cs

then dr > ds . Hence either some ai > k or dj > l.

Example. In a group of 6 people any two are either friends or enemies. Then there

are either 3 mutual friends or 3 mutual enemies.

Solution. Fix a person X. Then X has either 3 friends or 3 enemies. Assume the

former. If a couple of friends of X are friends of each other then we have 3 mutual

friends. Otherwise, X™s 3 friends are mutual enemies.

Dirichlet used the pigeonhole principle to prove that for any irrational ± there are

in¬nitely many rationals p satisfying ± ’ p < q12 .

q q

2.2 Induction

Recall the well-ordering axiom for N0 : that every non-empty subset of N0 has a least

element. This may be stated equivalently as: “there is no in¬nite descending chain in

N0 ”. We also recall the (weak) principle of induction from before.

11

CHAPTER 2. INDUCTION AND COUNTING

12

Proposition (Principle of Induction). Let P (n) be a statement about n for each n ∈

N0 . Suppose P (k0 ) is true for some k0 ∈ N0 and P (k) true implies that P (k + 1) is

true for each k ∈ N. Then P (n) is true for all n ∈ N0 such that n ≥ k0 .

The favourite example is the Tower of Hanoi. We have n rings of increasing radius