CHAPTER 1 Prime factorisation Flashcards
Motivation: Diophantine eq
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
N
N := {0, 1, 2, . . . }
integers
Z := {. . . , −2, −1, 0, 1, . . .}.
Definition 1.1.1 (Divisibility)
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.
d divides n if
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
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?
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.
5|0?
yes 0 = 5 x 0
n|0?
Every n|0 including 0 itself
.
1|n?
for every n in N n=n x 1
The number 1 divides n for any n ∈ Z because n = n · 1.
0|n?
On the other
hand, 0 | n only when n = 0, because n = q · 0 implies n = 0
d|a and d|b then
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.
a | b, b | c imply that a | c
TRANSITIVE
a | b, b | c imply that a | c
- 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.
gcd definition 1.1.4
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.
coprime
If gcd(a, b) = 1, then we say that a and b are coprime or relatively prime
gcd(8, 12) =
gcd(9, 0) =
gcd(8, 12) = 4, gcd(9, 0) = 0,
gcd(0,0)
=0
as common divisors are all naturals so can we take a max?
are 7 and 9 coprime?
gcd(7, 9) = 1 (hence 7 and 9 are coprime).
Exercise 1.1.6. What is gcd(n, n)?
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|.
remark lcm
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).
Lemma 1.1.7 DIVISION ALGORITHM
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|.
PROOF
Lemma 1.1.7 DIVISION ALGORITHM
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
50 = 2 · 24 + 2
division 50 hours by 24
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
e.g consider sequence of digits
a=dₙ …d₃d₂d₁d₀
from 0-9
format
Example 1.1.10 (Digits).
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₁
Example 1.1.8
divide 17 by 5
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).
Theorem 1.1.11 (Bézout’s Lemma (Bachet de Méziriac, 1624))
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.
Theorem 1.1.11 (Bézout’s Lemma (Bachet de Méziriac, 1624))
PROOF
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
IMMEDIATE CONSEQUENCES OF BEZOUTS LEMMA
meaning behind GCD
Corollary 1.1.12.
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
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)**
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
Corollary 1.1.12.
PROOF
2 If c | ab and gcd(a, c) = 1,
then c | b.
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.
Corollary 1.1.12.
PROOF
(3) If gcd(a, c) = 1 and gcd(b, c) = 1, then gcd(ab, c) = 1.
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.
Corollary 1.1.12.
PROOF
(4) If gcd(a, b) = 1 and a | c, b | c, then ab | c
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
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.
**
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.
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).
Theorem 1.2.1 (Euclid’s Algorithm, c. 300 BC)
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
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).
GCD(42,112)
112=42x2 +28
42=28x1 +14
28=14 x 2
thus gcd is 14
Exercise 1.2.2 (⋆, in exercise sheet). Prove that k is at most 2 log₂|b| + 3
(hint: show that r_{ℓ+2} ≤ rℓ/2).
*
Theorem 1.2.1 (Euclid’s Algorithm, c. 300 BC)
proof
part 1:
claim every r_ℓ is divisible by gcd(a, b)
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).
part 2:
we also claim that r_{k−1} divides r_{k−ℓ}
for all ℓ > 0
(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).
remark Euclids
if a| b and b|a then
divisibility on positive natural numbers is
(antisymmetric?)
if a| b and b|a then a=b
def 1.3.1 prime and composite
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
Lemma 1.3.2. A number p > 1 is prime if and only if
A number p > 1 is prime IFF for every a, b ∈ Z,
if p | ab implies p | a or p | b.
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.
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
Proposition 1.3.3. products of primes, when can we write as?
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.
Proof
Proposition 1.3.3. Every natural number n > 1 can be written as a product of primes.
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.
Theorem 1.3.4 (Euclid, c. 300 BC)
how many primes
There are infinitely many prime numbers.
proof
There are infinitely many prime numbers.
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.
how many primes below M?
approx
mlogm
e.g Suppose we thought that {2, 3, 5, 13} was the complete set of primes.
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.
Theorem 1.3.6 (Fundamental Theorem of Arithmetic)
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.
PROOF
Theorem 1.3.6 (Fundamental Theorem of Arithmetic)
Uniqueness part only
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
Remark 1.3.7. In practice, one usually applies the Fundamental Theorem of Arithmetic
to write positive integers as products of prime powers, t
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}
Exercise 1.3.8. Verify that gcd(n, m) · lcm(n, m) = nm
1.3.9 exercise
. Given n = pα11· · · pαkk
, count the number of positive divisors of n
M. The number of positive divisors is (α1 +1)···(αk +1).
1) c | a and c | b IFF
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
2 If c | ab and gcd(a, c) = 1,
then c | b.
(3) If gcd(a, c) = 1 and gcd(b, c) = 1, then
(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
(4) If gcd(a, b) = 1 and a | c, b | c, then ab | c
