Chapter 3 Flashcards
a is congruent to b modulo n
Let a,b∈ℤ and n∈ℕ. We write a≡bmodn and say a is congruent to b modulo n if n|(a-b)
a≡bmodn also means that => (there exists…)
there exists a k∈ℤ s.t. b=a+kn
a≡bmodn also means that => (a and b leave)
a and b leave the same remainder when divided by n
Lemma III.1.2 (congruence is an equivalence relation)
Let n∈ℕ and a,b,c∈ℤ
a) a≡amodn (reflexive
(b) if a≡bmodn then b≡amodn (symmetric)
(c) if a≡bmodn and b≡Cmodn then a≡cmodn
Lemma III.1.3 (operations on congruences)
Let n∈ℕ and a,b,c,d∈ℤ. Suppose that a≡bmodn and c≡dmodn. Then,
(i) a+c≡b+dmodn
(ii) a-c≡b-dmodn
(iii) ac≡bdmodn
complete set of residues
Let n∈ℕ. The a complete set of residues (CSR) modulo n is a subset S⊆ℤ with the property that every Integer is congruent modulo n to exactly one element of S.
Lemma II.2.1. complete set of residues modulo n.
Let n∈ℕ. Then {0,1,…,n-1} is a complete set of residues modulo n.
How to solve an equation of the form ax≡bmodn
- write out a table with x, ax and what ax is congruent to modulo n
- the solutions are given by the xs in the columns where the congruence is equal to b
Theorem III.3.1 ax≡bmodn
Let n∈ℕ and a,b∈ℤ and consider the equation ax≡bmodn. Let h=hcf(a,n). Then the following holds
(i) () has solutions <=> h|b
(ii) if x₀ is a solution to () then all the solutions to (*) are of the form
x₀, x₀ + n/h, … ,x₀ + (h-1)n/h
How to use the Euclidean algorithm to solve ax≡bmodn
- use Euclidean algorithm to find hcf(a,n)
- use extended Euclidean algorithm to find x,y s.t. h = xa +yn
- multiply through by b/h
- put into congruence modulo n
- find other solutions (from theorem III.3.1)
Corollary III.3.2 cancelling
Let n∈ℕ and a∈ℤ with a≢0modn. Let x₁,x₂∈ℤ suppose that
ax₁≡ax₂ modn and a and n are coprime. then x₁≡x₂ modn
i.e. you can cancel if a and n are coprime
Corollary III.3.3 cancelling when mod prime
Let p be a prime and a,x₁,x₂∈ℤ. Suppose that ax₁≡ax₂modp and that a≢0modp. Then,
x₁≡x₂modp
Corollary III.3.4 multiplicative inverse
let p be prime and a∈ℤ with a≢0modp. Then there exists a’∈ℤ such that aa’≡1modp
Fermats Little Theorem (FlT)
Suppose that p is prime and that a∈ℤ. Then:
(i) If a≢0modp then aᵖ⁻¹≡1modp
(ii) aᵖ≡amodp
How to determine the remainder when aᵇ is divided by p
- we know that for some c∈ℤ we have aᶜ≡1modp by FlT
- use the division theorem to divide b by c: b=dc + e
- aᵇ = aᵈᶜ ⁺ᵉ = (aᶜ)ᵈaᵉ = 1ᵈaᵉ≡modp
Eulers Theorem
Suppose that n∈ℕ and a∈ℤ with a and n coprime. then
aᵖʰᶦ⁽ⁿ⁾ ≡ 1 modn
f(X) is congruent to g(X)
let f(X) g(X) be polynomials with integer coefficients and let n∈ℕ. We say that f(X) is congruent to g(X) if for each i≥0 the coefficients of xᶦ if f(X) are congruent modulo n to the coefficiant of xᶦ in g(X).
in general f(X)≡g(X)modn =>
f(X)≡g(X)modn => for x∈ℤ f(x)≡g(x)modn
Lemma II.5.2. root of polynomial
Let n∈ℕ and f(X) be a polynomial with integer coefficients. Let a∈ℤ and suppose that a is a root of f(X)modn (i.e. f(a)≡0modn) Then there exists a polynomial g(X) also with integer coefficiants s.t. f(X)≡(x-a)g(X)modn.
degree modulo n of f(X)
Suppose that n∈ℕ and that f(X) is a polynomial with integer coefficients. The degree modulo n of f(X) is the largest d such that the coefficient of Xᵈ is not congruent to 0 modulo n. If all the coefficients are congruent to 0 modulo n then we define the degree to be -∞
if a is a root of f(X)-f(a) then…
f(x)-f(a)=(x-a)g(x)
Lagranges Theorem
Suppose that p is prime and that f(X) is a polynomial with integer coefficients and degree d≥0. Then the equation f(X)≡0modp has at most d distinct solutions modulo p.
Theorem III.5.4. exactly d solutions.
suppose that p is prime and d∈ℕ is such that d|p-1. Then Xᵈ≡1modp has exactly d solutions modulo p.
corollary III.5.6. exactly 2 solutions.
Suppose that p is prime and that p≡1mod4 Then
X²≡-1modp has exactly two solutions modulo p
Theorem III.5.7. coprime exactly n solutions.
Suppose that p is prime and d∈ℕ.
(i) if hcf(d,p-1)=1 then Xᵈ≡1modp has exactly one solution modulo p
(ii) Xᵈ≡1modp has exactly h(d,p-1) solutions modulo p
order
Let p be prime and a∈ℤ with a≢0modp then the order of a mod p is the smallest natural number d∈ℕ s.t. aᵈ≡1modp
we know that the order is always at least 1 because..
fermats little theorem aᵖ⁻¹≡1modp
Theorem
Suppose p is prime. Then there is an integer ω s.t. any integer z≢0modp is congruent to a power of ω modulo p. In other words, the multiplicative group of the integers modulo p is generated by ω
a≡ a +- n mode n
true
lemma III.6.1. distinct numbers modulo p.
Let p be prime a∈ℤ with a≢0modp and let d be the order of a modulo p. Then the integers a⁰,a¹,a²,..,aᵈ⁻¹ are all distinct modulo p
Lemma III.6.2
Let p be prime and a∈ℤ with a≢0modp. Let d be the order of a modp. Let k∈ℕ. Then, aᵏ≡1modp <=> d|k
corollary III.6.3
Let p be prime a∈ℤ with a≢0modp and let d be the order of a modulo p. Then d|p-1
Theorem III.6.4
Suppose that p is a prime and that d|p-1 with d>0. Then there are precisely ϕ(d) integers that have order d modulo p.
primitive root modulo p
suppose that p is prime. A primitive root modulo p is an integer ω with order p-1 modulo p.
corollary III.6.5
suppose that p is prime. Then there are precisely ϕ(p-1) primitive roots modulo p
if ω is a primitive root modulo p then a complete set of residues is given by
0, ω⁰, ω¹, ω², ωᵖ⁻²
true or false primitive roots always exist
true
