1 Numbers and Arithmetic Flashcards
Definition 1.1:
a|b
Let a, b ∈ Z. a divides b, written a | b, if there exists n∈Z such that an=b.
Definition 1.1:
Prime numbers
For p∈N, p is prime if:
- p≥2
- ∀a∈N, a|p ⇒ a=1or a=p.
Lemma 1.3:
1. if a|b and b|a
1. if m|a and m|b
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.
Proposition 1.4:
Product of primes
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.
Definition 1.6:
lcm
Let m,n∈N.
lcm(m,n) is the smallest a∈N such that m|a and n|a.
Definition 1.6:
gcd
Let m,n∈N.
gcd(m,n) is the largest a∈N such that a|m and a|n.
Definition 1.6
coprime
If gcd(m,n) = 1.
m,n∈N
Remark 1.7:
gcd of m/g and n/g
Let g := gcd(m,n). We claim that m/g and n/g are coprime.
Theorem 1.9
Euclid’s theorem
There are infinitely many primes.
Proposition 1.10:
Bézout identity
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.
Lemma 1.14:
Computing all Bézout identities
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.
Lemma 1.16:
Euclid’s Lemma
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.
Theorem 1.17:
Fundamental Theorem of Arithmetic
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.
Lemma 1.19:
gcd and lcm
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.
Definition 1.21:
Congruence modulo n
For n∈N and a,b∈Z,
a and b are congruent modulo n iff n|(a−b).
So a≡b (mod n).
Lemma 1.22:
Modulo
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.
Definition 1.23:
Congruence classes
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.
Lemma 1.24:
Arithmetic in Zn
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.
Proposition 1.26:
Multiplicative inverse
Let n ∈ N and m ∈ Z. Then [m] ∈ Zn has a multiplicative inverse if and only if m and n are coprime.
Corollary 1.27:
Property of Zp if p is prime
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.
Corollary 1.28:
Multiplication by a coprime element is invertible
If m, n ∈ Z are coprime, then the map Mₘ : Zₙ → Zₙ Mₘ([a]) = [a · m] has an inverse map.
Theorem 1.29:
Fermat’s Little Theorem
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).
Definition 1.31:
Congruence equation
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 ℤ𝑛.
Proposition 1.33:
Solving congruences
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.
Theorem 1.36:
Chinese Remainder Theorem
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).
Definition 1.38:
Group of units
Let 𝑛∈ℕ.
Group of units mod n: ℤ𝑛* = { [𝑎]∈ℤ𝑛 ∣ [𝑎] is invertible}.
Equivalently: ℤ𝑛={[𝑎] ∣ 1 ≤ 𝑎 ≤ 𝑛−1 and gcd(𝑎,𝑛)=1}.
Definition 1.38:
Euler’s 𝜙-function
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.
Lemma 1.41:
The group of units is a group
If [a], [b] ∈ Zₙ* , then [ab] ∈ Zₙ* .
Theorem 1.42:
Euler’s generalisation of Fermat’s Little Theorem
If n ∈ N and a ∈ Z is coprime to n, then a^φ(n) ≡ 1 (mod n).
a to the power of φ(n)
Definition 1.43:
Sum of complex numbers
(𝑎+𝑖𝑏) + (𝑥+𝑖𝑦) = (𝑎+𝑥) + 𝑖(𝑏+𝑦)
Definition 1.43:
Product of complex numbers
(𝑎+𝑖𝑏) (𝑥+𝑖𝑦) = 𝑎𝑥 + 𝑖(𝑏𝑥+𝑎𝑦) + 𝑖2𝑏𝑦 = (𝑎𝑥−𝑏𝑦) + 𝑖(𝑏𝑥+𝑎𝑦)
Definition 1.45:
Complex conjugate, real and imaginary parts, modulus
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 𝑧
Lemma 1.47:
Arithmetic with complex conjugate (4)
- Re(z) = (z+z̄)/2, Im(z) = (z−z̄)/2i
- complexconj(z₁+z₂) = z̄₁+z̄₂, complexconj(z₁·z₂) = z̄₁·z̄₂
- |z|² = z·z̄
- |z₁z₂| = |z₁|·|z₂|
Definition 1.48:
Polar form
The polar form of any nonzero 𝑧∈ℂ is 𝑧=𝑟𝑒ⁱᶿ=𝑟(cos𝜃+𝑖sin𝜃), where 𝑟=|𝑧| is the modulus of 𝑧 and 𝜃=arg(𝑧).
Proposition 1.51:
The unit circle is a group
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.
Comment 1.51.5
effect of multiplying complex numbers
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.
Corollary 1.52:
de Moivre’s Theorem
For n ∈ Z, we have (eⁱᶿ)ⁿ = eⁱⁿᶿ, i.e. (cosθ+isinθ)ⁿ = cos(nθ)+isin(nθ).
Definition 1.53:
Roots of unity
Let 𝑛∈ℕ. An 𝑛th root of unity is any complex number 𝑧∈ℂ that satisfies 𝑧^𝑛=1.
Proposition 1.54:
Roots of unity: zⁿ-1
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) ).
Theorem 1.55 / Corollary 1.56:
Fundamental Theorem of Algebra
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.
Definition 1.57:
Order of a root of unity
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.
Lemma 1.58:
Order of a root of unity and its divisibility
If ωⁿ = 1 for some ω ∈ C and n ∈ N, then ord(ω) | n.
