CHAPTER 1 Prime factorisation

Question 1

Motivation: Diophantine eq

Answer 1

x^n +y^n=z^n

has only trivial solutions for n>=3

how many integer solutions?

x^2+y^2=z^2 has integer solutions 3^2+4^2=5^2

Question 2

N

Answer 2

N := {0, 1, 2, . . . }

Question 3

integers

Answer 3

Z := {. . . , −2, −1, 0, 1, . . .}.

Question 4

Definition 1.1.1 (Divisibility)

Answer 4

Let n, d ∈ Z. We say that d is a factor n, or d is a divisor of n, or that d divides n if there is some q ∈ Z such that n = qd. When this is the case, we write d | n, otherwise we write d ∤ n.

Question 5

d divides n if

Answer 5

Take n,d in Z
d| n if there is k in Z s.t nk=d
d is a divisor/factor of n
12|24 8 doesnt divide 15
10|10a+20b

Question 6

Example 1.1.2. 5 | 10, 5 ∤ 11, −5 ∤ 10. Moreover, note that n | 0 for all n ∈ Z. When is it
true that 1 | n? And what about 0 | n?

Answer 6

The number 1 divides n for any n ∈ Z because n = n · 1. On the other
hand, 0 | n only when n = 0, because n = q · 0 implies n = 0.

Question 7

5|0?

Answer 7

yes 0 = 5 x 0

Question 8

n|0?

Answer 8

Every n|0 including 0 itself

.

Question 9

1|n?

Answer 9

for every n in N n=n x 1

The number 1 divides n for any n ∈ Z because n = n · 1.

Question 10

0|n?

Answer 10

On the other
hand, 0 | n only when n = 0, because n = q · 0 implies n = 0

Question 11

d|a and d|b then

Answer 11

d| (a+b)
a=dxk b =d x c
a+b = d(k+c) by def k+c in integers

more generally d|(ax+by) for every x,y in Z. if we write a = qd, b = rd, then ax + by = (qx + ry)d.

Question 12

a | b, b | c imply that a | c

Answer 12

TRANSITIVE

Question 13

a | b, b | c imply that a | c

Answer 13

• It is reflexive: n | n because n = n · 1.
• It is transitive: suppose that n | m and m | k. This means that m = nq, k = mr for some q, r ∈ Z. Then k = n(qr), so n | k.
• It is not symmetric: for instance, 2 | 4 but 4 ∤ 2.

An additional detail: within N, divisibility is antisymmetric. Indeed, if a | b | a,
there are k, ℓ ∈ N such that b = ka, a = ℓb, so a = kℓa, hence k = ℓ = 1, therefore a = b. This makes | a partial order on N.

Question 14

gcd definition 1.1.4

Answer 14

Let a, b ∈ Z not both zero. The highest common factor or greatest common divisor of a and b is the largest positive integer d such that d divides both a and b.

It is denoted gcd(a, b) := d, or sometimes (a, b) := d. We also set gcd(0, 0) := 0.

Question 15

coprime

Answer 15

If gcd(a, b) = 1, then we say that a and b are coprime or relatively prime

Question 16

gcd(8, 12) =
gcd(9, 0) =

Answer 16

gcd(8, 12) = 4, gcd(9, 0) = 0,

Question 17

gcd(0,0)

Answer 17

=0

as common divisors are all naturals so can we take a max?

Question 18

are 7 and 9 coprime?

Answer 18

gcd(7, 9) = 1 (hence 7 and 9 are coprime).

Question 19

Exercise 1.1.6. What is gcd(n, n)?

Answer 19

1,n are definitely common divisors
gcd(n, n) = |n|

By def gcd(0,0)=0 so consider case
n ̸= 0:
|n| divides n, since |n|=n or |n|=-n so gcd(n,n) ≥ |n|.

Moreover, if d ≥ 0 divides n, meaning that n = qd for some q, then |n| = |q||d|, thus |d| ≤ |n| because |q| ≥ 1, hence gcd(n, n) ≤ |n|.

It follows that gcd(n, n) = |n|.

Question 20

remark lcm

Answer 20

lcm(a, b) := ab/gcd(a,b) is
the ‘least upper bound’ of a, b (where lcm(a, b) = 0 when one of a, b is zero).

Question 21

Lemma 1.1.7 DIVISION ALGORITHM

Answer 21

Let a, b ∈ Z, where b≠ 0. Then there exist unique q,r ∈ Z (respectively quotient, remainder) such that
a = qb + r and 0 ≤ r < |b|.

Question 22

PROOF
Lemma 1.1.7 DIVISION ALGORITHM

Answer 22

Differs from notes

Proof. Suppose that b > 0. The set Q = {q′: q′b ≤ a} is bounded from above (for
instance, Q ≤ |a|), so it has a maximum q.

Note in particular that a < (q + 1)b. Let r = a − qb. By construction, 0 ≤ r < b.

When b < 0, we first use the conclusion with −b > 0 in place of b. We find that
a = q′(−b) + r where 0 ≤ r < −b = |b|. Now simply set q =−q′: we have
a =(−q′)b + r = qb + r, as desired

Question 23

50 = 2 · 24 + 2

division 50 hours by 24

Answer 23

2 x 24 +2

2 days 2 hours

Example 1.1.9 (Clocks). Times are the prototypical example of integer division.

90 minutes are equal to 1 hour and 30 minutes, because 90 = 1 · 60 + 30.

50 hours are 2 days and 2 hours because 50 = 2 · 24 + 2

Question 24

e.g consider sequence of digits

a=dₙ …d₃d₂d₁d₀

from 0-9
format

Example 1.1.10 (Digits).

Answer 24

a=10ⁿ dₙ +…+10¹d₁+d₀

The last digit of a number is its remainder after division by 10

d₀ remainder

a= 10q + d₀

where q=10ⁿ⁻¹ dₙ +…+d₁

Question 25

Example 1.1.8
divide 17 by 5

Answer 25

Divide 17 by 5: we find 17 = 3 · 5 + 2 (here q = 3, r = 2).
Divide −17 by −5: we get −17 = 4 · (−5) + 3 (so q = 4, r = 3).

Question 26

Theorem 1.1.11 (Bézout’s Lemma (Bachet de Méziriac, 1624))

Answer 26

Given a, b ∈ Z,
there are s, t ∈ Z s.t.
gcd(a, b) = sa + tb.

Moreover, if a, b > 0, then we may assume that s > 0 and t < 0.

Question 27

Theorem 1.1.11 (Bézout’s Lemma (Bachet de Méziriac, 1624))
PROOF

Answer 27

Specifically for integers.
Let’s take the set
I={ as+tb , s,t s,t∈ Z} ∩ N ⁺¹
subset of the naturals and greater than or equal to 1

Special case: if a=b=0 then I=empty set
gcd(0,0)=0, 0 ∈ I s=t=0 and conclusion holds

For a≠0 or b≠0: (We want to show that gcd(a, b) ∈ I).
The condition gives I is non empty: contains at least one non-zero natural. E.g. it contains |a| and |b| (s=+-1 and t=0 and s=0 t=+-1).
By the induction principle it contains minimum h>0.

CLAIM: h=gcd(a,b). ( we will show h|a and h|b)

Fix some s, t in Z s.t h=sa+tb

Apply the division algorithm and write a= qh+r where 0 ≤ r< h.
(h is minimum and in set I)
Rearrange
r=a-qh=a-q(sa+tb)
= (1-qs)a-qtb
implies r ∈ I.
(If r>0 then r is in I but r <h as is the remainder but h is the minimum of I: contradiction )
By minimality of h, we must have r = 0, remainder must be 0 and so that h | a. By the same argument with b in
place of a, we find that h | b.

It follows that h ≤ gcd(a, b).

CONVERSELY
gcd(a, b) divides a and b,
so it divides h = sa + tb,
gcd(a,b)|h for any s,t in Z
hence gcd(a, b) ≤ h.

It follows that h = gcd(a, b).

suppose a,b>0 Choose s>0 and t <0
Fix s’,t’ in Z s.t. gcd(a,b)=s’a+t’b (we know exists by prev part of proof)

Take a large s.t. s’ +kb>0
(add multiples of b s.t. it becomes positive e.g. take k=|s’|+1)
Take t=t’-ka
taking k large makes t negative
sa+tb= s’a+kab+t’b-kab
=s’a+t’b=gcd(a,b)

(these multiples arent unique; infinitely many ways of writing this GCD)

(differs notes)
Choose k ∈ N large enough so that s′ = s + kb > 0 and t′ = t − ka < 0.
But then s′a +t′b = sa + kab + tb − kab = sa + tb = gcd(a, b), as desired

Question 28

IMMEDIATE CONSEQUENCES OF BEZOUTS LEMMA

meaning behind GCD

Corollary 1.1.12.

Answer 28

1) c | a and c | b IFF c | gcd(a, b).

** (gcd is a biggest common divisor, any other divisor divides it)**

2 If c | ab and gcd(a, c) = 1,
then c | b.

(3) If gcd(a, c) = 1 and gcd(b, c) = 1, then gcd(ab, c) = 1.

(4) If gcd(a, b) = 1 and a | c, b | c, then ab | c

Question 29

Corollary 1.1.12.
PROOF
1) c | a and c | b IFF c | gcd(a, b).

** (gcd is a biggest common divisor, any other divisor divides it)**

Answer 29

1) if c|a and c|b then
c|sa+tb for every integer s and t
so in particular c| gcd(a,b) by Bezouts lemma.

if c | gcd(a, b) then c|a and c|b

Question 30

Corollary 1.1.12.
PROOF
2 If c | ab and gcd(a, c) = 1,
then c | b.

Answer 30

c|ab now
Pick s, t ∈ Z such that
sa + tc = gcd(a, c) = 1.

Multiply by b, so that sab + tcb = b.

Since c | ab and obviously c | tcb, we find that c | b.

Question 31

Corollary 1.1.12.
PROOF

(3) If gcd(a, c) = 1 and gcd(b, c) = 1, then gcd(ab, c) = 1.

Answer 31

Let d = gcd(ab, c). Since d | c and gcd(a, c) = 1, any common divisor of d and a
cannot be more than 1, thus gcd(a, d) = 1. By the previous part, d divides b, hence
d ≤ gcd(b, c) = 1.

Question 32

Corollary 1.1.12.
PROOF

(4) If gcd(a, b) = 1 and a | c, b | c, then ab | c

Answer 32

Pick s, t ∈ Z such that sa + tb = 1. Write also c = qa = rb. Then
c = sac + tbc = sarb + tbqa = ab(sr + tq)
which shows that ab divides c

Question 33

Exercise 1.1.13 (⋆, in exercise sheet). Let a, b ∈ N be non-zero natural numbers and
let d = gcd(a, b).

Show that a/d, b/d are coprime.
gcd(a/d,b/d)=1

Show that if c is a common multiple of a and b (meaning that a | c and b | c), then ab/d | c.
Deduce that ab/d is the least common multiple of a and b.

Answer 33

**

Question 34

Finding s, t ∈ Z such that gcd(a, b) = sa + tb could be hard.

The proof of Bézout’s Lemma suggests searching among all s, t such that |s| ≤ |a| and |t| ≤ |b|, which is a lot of work: that’s (2|a| + 1)(2|b| + 1) possible pairs! We can do a lot better.

Answer 34

Euclid’s algorithm

algorithm takes at most |b| steps, because
r_k = 0 < · · · < r_{ℓ+1} < r_{ℓ} < . . .
forces k ≤ |b|.
This is quite an improvement over (2|a| + 1)(2|b| + 2).

Question 35

Theorem 1.2.1 (Euclid’s Algorithm, c. 300 BC)

Answer 35

Let a, b ∈ Z, with b ≠ 0.
(o/w gcd would be 0!)

Apply repeatedly the Division Algorithm, starting with
r₀ := a, r₁:= |b|, and obtaining remainders r₂,r₃, . . . :

a = r₀ = q₂r₁ + r₂,
where 0 ≤ r₂ < r₁ = |b|

r₁ = q₃r₂ + r₃, where 0 ≤ r₃ < r₂
.
.
.
r_ℓ = q_{ℓ+2}r_{ℓ+1} + r_{ℓ+2}
, where 0 ≤ r_{ℓ+2} < r_{ℓ+1}
.
.
.
Then some remainder r_k
is zero, and the last non-zero remainder r_{k−1}
is gcd(a, b).

strictly decreasing, must happen as natural numbers must have a minimum and it solved by induction principle

It works as GCD (a,b) =GCD(bxq+r, b) =GCD (b,r)
#binary digits of b steps

Question 36

e.g Euclidean Algorithm
Find the Greatest Common divisor of 42 and 112
the last non-zero remainder r_{k−1} is gcd(a, b).

Answer 36

GCD(42,112)

112=42x2 +28

42=28x1 +14

28=14 x 2

thus gcd is 14

Question 37

Exercise 1.2.2 (⋆, in exercise sheet). Prove that k is at most 2 log₂|b| + 3

(hint: show that r_{ℓ+2} ≤ rℓ/2).

Answer 37

*

Question 38

Theorem 1.2.1 (Euclid’s Algorithm, c. 300 BC)
proof
part 1:
claim every r_ℓ is divisible by gcd(a, b)

Answer 38

Since |b| = r1 > r2 > · · · ≥ 0, (decreasing remainders)

by the Induction Principle there is k with r_k = 0.
Take k minimum with this property (again, by the Induction Principle!).

claims: (equivalent)
*r_{k-1} = gcd(a,b)
* r_{k-1)as+bt
* gcd(a,b) divides r_ℓ for every ℓ.
* Every r_ℓ is of the form a s_ℓ + b t_ℓ
for some s_ℓ,t_ℓ in z

base case:
r_0=a r_1 =|b|= ±b (so of the required form)

inductively (looking at remainder two steps before )
claim r_ℓ and r_{ℓ+1} are of the required form

r_{ℓ+2} = r_ℓ - q_{ℓ+2}r_{ℓ+1}
= a s_ℓ + b t_ℓ - q_{ℓ+2}[a s_{ℓ+1} + b t_{ℓ+1}]

= (s_ℓ + q_{ℓ+2}s_{ℓ+1})a + (t_ℓ + q_{ℓ+2}t_{ℓ+1})b.

Thus every r_ℓ is divisible by gcd(a, b).

Question 39

part 2:
we also claim that r_{k−1} divides r_{k−ℓ}
for all ℓ > 0

Answer 39

(the last nonzero remainder divides all of the previous ones)
by induction again:
since r_k = 0 (algorithm stops when r_k=0)
r_{k-1} clearly divides r_{k-1}
, we have
r_{k−2} = q_k r_{k−1} + r_k (by definition)
= q_k r_{k−1}
r_{k-1} divides r_{k-2} (BASE CASE shown)

INDUCTIVE STEP:
Suppose r_{k−1} divides r_{k−ℓ−1} and r_{k−ℓ}
for some ℓ > 0,

r_{k−ℓ−2} = q_k r_{k−ℓ−1} + r_{k−ℓ}

By induction principle:
We can see that r_{k−1} divides r_{k−ℓ−2} as well.

Particularly,
r_{k−1} divides r_1 = |b| and r_0 = a,
Thus, by Bezouts lemma, r_{k−1} divides gcd(a, b).

Question 40

remark Euclids

if a| b and b|a then

Answer 40

divisibility on positive natural numbers is
(antisymmetric?)

if a| b and b|a then a=b

Question 41

def 1.3.1 prime and composite

Answer 41

A natural number p ∈ N with p > 1 is prime if its only positive divisors are 1 and p.

Otherwise, we say that p is composite

1 ISN’T A PRIME

Question 42

Lemma 1.3.2. A number p > 1 is prime if and only if

Answer 42

A number p > 1 is prime IFF for every a, b ∈ Z,

if p | ab implies p | a or p | b.

Question 43

PROOF
LEMMA 1.3.2
A number p > 1 is prime IFF for every a, b ∈ Z,

if p | ab implies p | a or p | b.

Answer 43

Suppose that p is prime (only positive divisors are 1 and p. ). If p ∤ a, then gcd(a, p) = 1 (only common divisor as p is prime), so p | ab implies p | b by Corollary 1.1.12.

Suppose that p is not prime, there is a divisor b s.t. 1<b< p thus p = ab for some positive a, b both different from 1 (and so from p as well):
we must have a < p, b < p, thus p ∤ a and
p ∤ b. condition fails

Question 44

Proposition 1.3.3. products of primes, when can we write as?

Answer 44

Proposition 1.3.3. Every natural number n > 1 can be written as a product of primes.

If n = prime, ‘product’ of a single prime.

n = 1 ‘empty product’ of primes.

Question 45

Proof
Proposition 1.3.3. Every natural number n > 1 can be written as a product of primes.

Answer 45

Suppose by contradiction that there is some n > 1 that cannot be written as a product of primes.

By the Induction Principle, we can take n minimum with this property.

But then n is not prime, (otherwise it would be a prod of primes)

thus n = ab for some a, b both different from 1 and n,
and in particular 1 < a, b < n.

By minimality of n, a and b can be written as products
of primes, ( By induction, since a,b are smaller than N
, they must each be a product of primes.)

so n = ab is a product of primes too, a contradiction.

Question 46

Theorem 1.3.4 (Euclid, c. 300 BC)
how many primes

Answer 46

There are infinitely many prime numbers.

Question 47

proof

There are infinitely many prime numbers.

Answer 47

Suppose by contradiction that there are only finitely many primes, and list
them all as p_1, . . . , p_ₙ. Note that N > 0 since we know for instance that 2 is a prime.

Let M = p₁ · · · p_ₙ + 1. Note that M ≥ 2 + 1 > 1.
(by construction we know the primes won’t divide this)

By Proposition 1.3.3, M is a product of
primes.

Since we listed all primes, we must have
M = p_{k₁} · · · p_{k_ℓ}.
On the other hand, p_i ∤ M for all i = 1, . . . , N, a contradiction.

Question 48

how many primes below M?

Answer 48

approx

mlogm

Question 49

e.g Suppose we thought that {2, 3, 5, 13} was the complete set of primes.

Answer 49

Suppose we thought that {2, 3, 5, 13} was the complete set of primes.
Then M = 2 · 3 · 5 · 13 + 1 = 391 is not divisible by 2, 3, 5, 13. We can factorise it and
find M = 17 · 23, and so find two new primes.

Question 50

Theorem 1.3.6 (Fundamental Theorem of Arithmetic)

Answer 50

Every natural number n > 1 can be written in a unique way as a product of primes, up to reordering the factors

90
= 2 · 3 · 3 · 5
= 3 · 5 · 2 · 3:
the two factorisations are simply a reordering of the same list 2, 3, 3, 5.

Question 51

PROOF
Theorem 1.3.6 (Fundamental Theorem of Arithmetic)

Answer 51

We show uniqueness.

Write n = p_1 · · · p_r = q_1 · · · q_s where each p_i, q_j is prime. same number of primes?

We prove the conclusion by induction on r.
Since p_1 | n, we find that p_1 | q_j for some j (in particular, s ≥ 1) (p_1 is prime thus prev shown p_1 must divide one of the factors) ), thus p1 = qj since qj
is prime.

We reorder the second product so that in fact
p_1 = q_1. (Base case)

Induction hypothesis
Now divide n by p_1.
If r = 1 we find that n = p_1 = q_1, and we are done. Otherwise,
we now have p_2 · · · p_r = q_2 · · · q_s > 1. By induction hypothesis, after reordering the products, we may assume that p_2 = q_2, . . . , p_r = q_r and r = s, and we are done

Question 52

Remark 1.3.7. In practice, one usually applies the Fundamental Theorem of Arithmetic
to write positive integers as products of prime powers, t

Answer 52

in practice, one usually applies the Fundamental Theorem of Arithmetic
to write positive integers as products of prime powers, that is
n = p_1^{α_1}· · · p_k ^{α_k}
where the primes pi are distinct and the
α_i’s are natural numbers.

For example, 350 =2 · 5^2· 7 = 2 · 3^0· 5^2· 7 · 11^0

Given the above expression, one can immediately read off the following numbers:
* the divisors of n are exactly the numbers p_1^{γ_1}· · · p_k ^{γ_k} with γ_i ≤ α_i ;
* if m = p_1^{β_1}· · · p_k^{β_k}, then
gcd(n, m) = p_1 ^{min{α1,β1}}· · · p_k ^{min{αk,βk};
* with m as above, the least common multiple of n and m is
lcm(n, m) = p_1^{max{α1,β1}}· · · p_k ^{max{αk,βk}

Question 53

Exercise 1.3.8. Verify that gcd(n, m) · lcm(n, m) = nm

Question 54

1.3.9 exercise
. Given n = pα11· · · pαkk
, count the number of positive divisors of n

Answer 54

.

Question 55

1) c | a and c | b IFF

Answer 55

1) c | a and c | b IFF c | gcd(a, b).

** (gcd is a biggest common divisor, any other divisor divides it)**

Question 56

2 If c | ab and gcd(a, c) = 1,
then

Answer 56

2 If c | ab and gcd(a, c) = 1,
then c | b.

Question 57

(3) If gcd(a, c) = 1 and gcd(b, c) = 1, then

Answer 57

(3) If gcd(a, c) = 1 and gcd(b, c) = 1, then gcd(ab, c) = 1.

Question 58

(4) If gcd(a, b) = 1 and a | c, b | c, then

Answer 58

(4) If gcd(a, b) = 1 and a | c, b | c, then ab | c