1 Numbers and Arithmetic

Question 1

Definition 1.1:
a|b

Answer 1

Let a, b ∈ Z. a divides b, written a | b, if there exists n∈Z such that an=b.

Question 2

Definition 1.1:
Prime numbers

Answer 2

For p∈N, p is prime if:
- p≥2
- ∀a∈N, a|p ⇒ a=1or a=p.

Question 3

Lemma 1.3:
1. if a|b and b|a
1. if m|a and m|b

Answer 3

Let a, b, m ∈ Z.
1. If a|b and b|a, then a=±b.
1. If m|a and m|b, then m|λa+μb for all λ,μ∈Z.

Question 4

Proposition 1.4:
Product of primes

Answer 4

Every integer >1 is a product of primes,
i.e., each m∈Z satisfying m≥2 can be written as
m = Πᵏᵢ₌₁ (pᵢ) = p₁ p₂ … pₖ
for some k ≥ 1, where p₁,…,pₖ are primes that need not be distinct.

Question 5

Definition 1.6:
lcm

Answer 5

Let m,n∈N.
lcm(m,n) is the smallest a∈N such that m|a and n|a.

Question 6

Definition 1.6:
gcd

Answer 6

Let m,n∈N.
gcd(m,n) is the largest a∈N such that a|m and a|n.

Question 7

Definition 1.6
coprime

Answer 7

If gcd(m,n) = 1.
m,n∈N

Question 8

Remark 1.7:
gcd of m/g and n/g

Answer 8

Let g := gcd(m,n). We claim that m/g and n/g are coprime.

Question 9

Theorem 1.9
Euclid’s theorem

Answer 9

There are infinitely many primes.

Question 10

Proposition 1.10:
Bézout identity

Answer 10

For a, b ∈ N, let g be the smallest positive integer
in the set S = { λa + μb | λ, μ ∈ Z}.
Then g = gcd(a, b).

i.e. gcd(a, b) = λa + μb for some λ, μ ∈ Z.

Question 11

Lemma 1.14:
Computing all Bézout identities

Answer 11

For a, b ∈ N, write g = gcd(a, b).
Suppose that λ, μ ∈ Z give a particular Bézout identity g = λa + μb.
Then every Bézout identity is of the form g = (λ + α)a + (μ − β)b for some α, β ∈ Z, where αa = βb.

Question 12

Lemma 1.16:
Euclid’s Lemma

Answer 12

Let a, b ∈ Z and p be a prime. Then p|ab ⇒ (p|a or p|b).
More generally p|(a₁… aₖ) ⇒ p|aᵢ for some 1 ≤ i ≤ k.

Question 13

Theorem 1.17:
Fundamental Theorem of Arithmetic

Answer 13

Every integer >1 can be written uniquely (upto the choice of order) as a product of primes.
i.e., each m∈Z satisfying m≥2 can be written as
m = Πᵏᵢ₌₁ (pᵢ) = p₁ p₂ … pₖ
for some k ≥ 1, where the primes p₁,…,pₖ are uniquely determined by m.

Question 14

Lemma 1.19:
gcd and lcm

Answer 14

Consider d, m, n ∈ N. Then:
1. gcd(m,n) · lcm(m,n) = m·n
1. m|d and n|d iff lcm(m,n)|d.

Question 15

Definition 1.21:
Congruence modulo n

Answer 15

For n∈N and a,b∈Z,
a and b are congruent modulo n iff n|(a−b).
So a≡b (mod n).

Question 16

Lemma 1.22:
Modulo

Answer 16

For a ∈ Z, there exists r satisfying 0 ≤ r < n such that a ≡ r (mod n).

i.e. every int is congruent modulo n to an integer r in the range 0≤r<n.

Question 17

Definition 1.23:
Congruence classes

Answer 17

Let 𝑛∈ℕ. The congruence classes modulo 𝑛
are the 𝑛 distinct sets [0], [1], …, [n-1] into which ℤ is ‘partitioned’ by the ‘congruence modulo n’ relation.
We write ℤ𝑛={ [𝑎] ∣ 𝑎∈ℤ } = { [0],[1],…,[𝑛−1] } for the set of all congruences classes modulo n.

Question 18

Lemma 1.24:
Arithmetic in Zn

Answer 18

There are well-defined sum and product operations on Zn given by
* [a]+[b]=[a+b]
* [a]·[b]=[a·b].

Sum and product are both associative and commutative in Zn.

[0] is the additive identity, [1] is the multiplicative identity.

Question 19

Proposition 1.26:
Multiplicative inverse

Answer 19

Let n ∈ N and m ∈ Z. Then [m] ∈ Zn has a multiplicative inverse if and only if m and n are coprime.

Question 20

Corollary 1.27:
Property of Zp if p is prime

Answer 20

If p is prime, then each of [1], [2], . . . , [p−1] have a multiplicative inverse in Zp.

Every nonzero congruence class in Zp has a multiplicative inverse.

Question 21

Corollary 1.28:
Multiplication by a coprime element is invertible

Answer 21

If m, n ∈ Z are coprime, then the map Mₘ : Zₙ → Zₙ Mₘ([a]) = [a · m] has an inverse map.

Question 22

Theorem 1.29:
Fermat’s Little Theorem

Answer 22

If p is prime, then aᵖ ≡ a (mod p) for
all a ∈ Z.
Furthermore if p does not divide a (a and p are coprime), then aᵖ⁻¹ ≡ 1 (mod p).

Question 23

Definition 1.31:
Congruence equation

Answer 23

Let 𝑛∈ℕ and 𝑎,𝑏∈ℤ.
Any statement of the form ‘𝑎𝑥≡𝑏 (mod 𝑛)’ is a congruence equation.
Solving any such equation means finding all 𝑥∈ℤ that satisfy the relation, or equivalently, solving [𝑎][𝑥]=[𝑏] in ℤ𝑛.

Question 24

Proposition 1.33:
Solving congruences

Answer 24

For n ∈ N and a ∈ Z, let g = gcd(a,n). Then
ax≡b (mod n) has a solution iff g|b,
in which case, the congruence reduces to a/g x ≡ b/g (mod n/g), where a/g and n/g are coprime.

Question 25

Theorem 1.36:
Chinese Remainder Theorem

Answer 25

Let m, n ∈ N be coprime. For any a, b ∈ Z, the congruence equations
* x ≡ a (mod m),
* x ≡ b (mod n)

have a unique solution (mod mn).

Question 26

Definition 1.38:
Group of units

Answer 26

Let 𝑛∈ℕ.
Group of units mod n: ℤ𝑛* = { [𝑎]∈ℤ𝑛 ∣ [𝑎] is invertible}.
Equivalently: ℤ𝑛={[𝑎] ∣ 1 ≤ 𝑎 ≤ 𝑛−1 and gcd(𝑎,𝑛)=1}.

Question 27

Definition 1.38:
Euler’s 𝜙-function

Answer 27

Let 𝑛∈ℕ.
It is the function 𝜙:ℕ→ℕ,
𝜙(𝑛) =
* number of integers 𝑎∈{1,…,𝑛−1} where gcd(𝑎,𝑛)=1.
* number of elements in ℤ𝑛*.

Counts the number of elements in the group of units mod n.

𝜙(1)=1.

Question 28

Lemma 1.41:
The group of units is a group

Answer 28

If [a], [b] ∈ Zₙ* , then [ab] ∈ Zₙ* .

Question 29

Theorem 1.42:
Euler’s generalisation of Fermat’s Little Theorem

Answer 29

If n ∈ N and a ∈ Z is coprime to n, then a^φ(n) ≡ 1 (mod n).

a to the power of φ(n)

Question 30

Definition 1.43:
Sum of complex numbers

Answer 30

(𝑎+𝑖𝑏) + (𝑥+𝑖𝑦) = (𝑎+𝑥) + 𝑖(𝑏+𝑦)

Question 31

Definition 1.43:
Product of complex numbers

Answer 31

(𝑎+𝑖𝑏) (𝑥+𝑖𝑦) = 𝑎𝑥 + 𝑖(𝑏𝑥+𝑎𝑦) + 𝑖2𝑏𝑦 = (𝑎𝑥−𝑏𝑦) + 𝑖(𝑏𝑥+𝑎𝑦)

Question 32

Definition 1.45:
Complex conjugate, real and imaginary parts, modulus

Answer 32

Let 𝑧=𝑥+𝑖𝑦∈ℂ.
* z̄ =𝑥−𝑖𝑦 is the complex conjugate (reflection in the real axis).
* ℜ(𝑧) := 𝑥 is the real part of 𝑧
* ℑ(𝑧) :=𝑦 is the imaginary part of 𝑧
* |𝑧|= sqrt(𝑥²+𝑦²) is the modulus (or magnitude) of 𝑧

Question 33

Lemma 1.47:
Arithmetic with complex conjugate (4)

Answer 33

1. Re(z) = (z+z̄)/2, Im(z) = (z−z̄)/2i
2. complexconj(z₁+z₂) = z̄₁+z̄₂, complexconj(z₁·z₂) = z̄₁·z̄₂
3. |z|² = z·z̄
4. |z₁z₂| = |z₁|·|z₂|

Question 34

Definition 1.48:
Polar form

Answer 34

The polar form of any nonzero 𝑧∈ℂ is 𝑧=𝑟𝑒ⁱᶿ=𝑟(cos𝜃+𝑖sin𝜃), where 𝑟=|𝑧| is the modulus of 𝑧 and 𝜃=arg(𝑧).

Question 35

Proposition 1.51:
The unit circle is a group

Answer 35

The unit circle S¹ = { w∈C | |w|=1 } is closed under complex multiplication; more explicitly, eⁱᶿ¹ · eⁱᶿ² = eⁱ⁽ᶿ¹⁺ᶿ²⁾.

Closed under complex multiplication:
The product of two complex numbers that lie on the unit circle is a complex number on the unit circle.

Question 36

Comment 1.51.5
effect of multiplying complex numbers

Answer 36

For any nonzero w = reⁱᶿ, z = seⁱᵝ ∈ C, multiplication by w is z ↦ (w·z) = reⁱᶿ·seⁱᵝ = (rs)eⁱ⁽ᶿ⁺ᵝ⁾,

i.e. a rotation by arg(w) = θ and scaling by |w|= r.

Question 37

Corollary 1.52:
de Moivre’s Theorem

Answer 37

For n ∈ Z, we have (eⁱᶿ)ⁿ = eⁱⁿᶿ, i.e. (cosθ+isinθ)ⁿ = cos(nθ)+isin(nθ).

Question 38

Definition 1.53:
Roots of unity

Answer 38

Let 𝑛∈ℕ. An 𝑛th root of unity is any complex number 𝑧∈ℂ that satisfies 𝑧^𝑛=1.

Question 39

Proposition 1.54:
Roots of unity: zⁿ-1

Answer 39

The nth roots of unity are precisely z = e^(2πik/n) for 0 ≤ k ≤ n − 1.
In particular, zⁿ − 1 = Πₖ₌₀ⁿ⁻¹ ( z − e^(2πik/n) ).

Question 40

Theorem 1.55 / Corollary 1.56:
Fundamental Theorem of Algebra

Answer 40

Every polynomial f(z) in one variable with coefficients in C has a root in C, that is, a solution to f(z) = 0.

Basically:
Every polynomial of degree n with coefficients in C has precisely n roots in C if we count roots ‘with multiplicity’.
i.e. f(z) is a product of n linear factors:
* if f(z) = aₙzⁿ +…+ a₁z + a₀

with aⱼ ∈C and aₙ≠0, then
* f(z)=aₙ Πⁿᵢ₌₁ (z−αᵢ),

for some αᵢ ∈ C.

Question 41

Definition 1.57:
Order of a root of unity

Answer 41

If 𝜔∈ℂ is a root of unity (i.e. 𝜔ⁿ=1 for some 𝑛∈ℕ) then we say 𝜔 has order 𝑚, denoted ord(𝜔)=𝑚, if 𝑚=min{ 𝑛∈ℕ ∣ 𝑤ⁿ=1 }. In this case, we call 𝜔 a primitive 𝑚th root of unity.

Question 42

Lemma 1.58:
Order of a root of unity and its divisibility

Answer 42

If ωⁿ = 1 for some ω ∈ C and n ∈ N, then ord(ω) | n.