CHAPTER 1 Prime factorisation Flashcards

1
Q

Motivation: Diophantine eq

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

N

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

integers

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Definition 1.1.1 (Divisibility)

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

d divides n if

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

5|0?

A

yes 0 = 5 x 0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

n|0?

A

Every n|0 including 0 itself

.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

1|n?

A

for every n in N n=n x 1

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

0|n?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

d|a and d|b then

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

TRANSITIVE

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A
  • 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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

gcd definition 1.1.4

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

coprime

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

gcd(0,0)

A

=0

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

are 7 and 9 coprime?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

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

A

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|.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

remark lcm

A

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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Lemma 1.1.7 DIVISION ALGORITHM

A

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|.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

PROOF
Lemma 1.1.7 DIVISION ALGORITHM

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

50 = 2 · 24 + 2

division 50 hours by 24

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

e.g consider sequence of digits

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

from 0-9
format

Example 1.1.10 (Digits).

A

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₁

25
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).
26
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.
27
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 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
28
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
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)**
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
30
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.
31
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.
32
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
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.
**
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.
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).
35
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
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).
GCD(42,112) 112=42x2 +28 42=28x1 +14 28=14 x 2 thus gcd is 14
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).
*
38
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).
39
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).
40
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
41
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
42
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.
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.
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
44
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.
45
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.
46
Theorem 1.3.4 (Euclid, c. 300 BC) how many primes
There are infinitely many prime numbers.
47
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.
48
how many primes below M?
approx mlogm
49
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.
50
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.
51
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
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
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}
53
Exercise 1.3.8. Verify that gcd(n, m) · lcm(n, m) = nm
54
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).
55
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)**
56
2 If c | ab and gcd(a, c) = 1, then
2 If c | ab and gcd(a, c) = 1, then c | b.
57
(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.
58
(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