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.
