1/31
Looks like no tags are added yet.
Name | Mastery | Learn | Test | Matching | Spaced | Call with Kai |
|---|
No analytics yet
Send a link to your students to track their progress
For integers a, b and n > 0, what does a ≡ b (mod n) mean?
a and b leave the same remainder when divided by n, or that there exists an integer x such that a = b + nx
How can ‘a and b leave the same remainder when divided by n’ be written formally?
n | (a − b) (a - b is divisible by n)
What are the properties of congruence if a ≡ b (mod n) and c ≡ d (mod n)?
Addition: a + c ≡ b + d (mod n)
Subtraction: a − c ≡ b − d (mod n)
Multiplication: ac ≡ bd (mod n)
What does ax ≡ b (mod n) mean?
when ax is divided by n, it leaves the same remainder as b
When does ax ≡ b (mod n) have a solution?
Iff hcf(a, n) | b which is the rule that tells you whether its solvable or not e.g. if hcf(a, n) = 1 then there’s exactly one solution mod n
Why does hcf(a, n) = 1 mean there’s only 1 solution?
Because Bézout’s Lemma guarantees integers x, y such that ax + ny = 1 so x acts as a multiplicative inverse of a mod n. We can multiply both sides of the congruence by that inverse to isolate x
What is the Chinese Remainder Theorem?
If the moduli n1, n2, …, nk are pairwise coprime (no common factors other than 1), then the system:
x = a1 (mod n1)
x = a2 (mod n2)
…
x = ak (mod nk)
Has exactly 1 solution N = n1n2…nk.
(If the moduli don’t “interfere” with each other (they’re coprime), you can combine several modular equations into one single equivalent equation)
What is Fermat’s Little Theorem?
If p is prime and a is not divisible by p, then: ap−1 ≡ 1 (mod p)
Let a, b, c be integers and n be a natural number. What are the properties of congruence modulo n?
Reflexive property: a ≡ a mod n
Symmetric property: If a ≡ b mod n then b ≡ a mod n
Transitive property: If a ≡ b mod n and b ≡ c mod n then a ≡ c mod n
Prove the properties of congruence modulo n
Reflexive property: a ≡ a + 0n so a ≡ a mod n
Symmetric property: Since a ≡ b mod n, there exists an integer x such that a = b + nx. Then b = a - nx = a + n(-x) and -x is an integer. So b ≡ a mod n
Transitive property: Since a ≡ b mod n and b ≡ c mod n, there exists integers x, y such that a = b + nx and b = c + ny. Then a = c + ny + nx so a = c + n(x + y) where x + y is an integer. So a ≡ c mod n
Prove the lemma: Let n be a natural number and a, b be integers. Then a ≡ b mod n iff a and b leave the same remainder when divided by n.
Use division theorem: there exists a q, q’, r, r’ such that a = qn + r and b = q’ + r’
Then r is the remainder when a is divided by n and r’ is the remainder when b is divided by n
So a - b = (q - q’)n + (r - r’)
Suppose a ≡ b mod n so n | (a - b) and n | ((q - q’)n + (r - r’))
Then n | (r - r’) and n | (q - q’) by lemma
Also -n < r - r’ < n
So r - r’ = 0 thus r = r’ then a - b ≡ (q - q’)n
Then n | a - b and a ≡ b mod n
Let n, m be natural numbers and a, a’, b, b’ be integers. Suppose a ≡ b mod n and a’ ≡ b’ mod n. Then…
a + a’ ≡ (b + b’) mod n: Since a + a’ = b + nx + b’ + nx’ so a + a’ = b + b’ + n(x + x’) where x + x’ is an integer
aa’ ≡ bb’ mod n: aa’ = (b + nx)(b’ + nx’) = bb’ + bnx’ + b’nx + n2xx’ = bb’ + n(bx’ + b’x + nxx’) where bx’ + b’x + nxx’ is an integer
am ≡ bm mod n: Repeated use of 2nd proof
What is a linear congruence equation?
One of form ax ≡ b mod n
Let n be a natural number and a be an integer. Suppose that a is coprime to n. Then…
There exists an integer z such that az ≡ 1 mod n
Prove the corollary: Let n be a natural number and a, b be integers. Suppose a is coprime to n. Consider ax ≡ b mod n (*). Then there exists an integer s such that the solutions of (*) are given by x ≡ s mod n.
By the theorem that states that if a is coprime to n, there exists an integer z such that az ≡ 1 mod n.
If ax ≡ b mod n then x ≡ (az)x mod n ≡ z(ax) mod n ≡ zb mod n
If x ≡ zb mod n then,
ax ≡ azb mod n ≡ (az)b mod n ≡ b mod n
Therefore we can take s = zb and the solutions of (*) are given by x ≡ s mod n
What is the algorithm to solve linear congruence equations ax ≡ b mod n?
Calculate h = hcf(a, n)
If h is not a factor of b, there are no solutions. If h | b, consider a’x ≡ b’ mod n’ where a’ = a/h, b’ = b/h and n’ = n/h
Find integer s such that a’s ≡ b’ mod n’. To do this, find integer z such that a’z ≡ 1 mod n’ and then set x = zb’. We can find z using extended Euclidean algorithm or find x by inspection
The solutions are given by x ≡ s mod n’
Let a, b, x be integers, n be a natural number and h = hcf(a, n). Suppose ax ≡ b mod n. Then…
h | b
Let a, b, x be integers, n be a natural number and h = hcf(a, n). Suppose h | b and let a’ = a/h, b’ = b/h and n’ = n/h. Then…
ax ≡ b mod n iff a’x ≡ b’ mod n’
a’ is coprime to n’
Let n be a natural number and a, b, c be integers. Suppose c is coprime to n and ac ≡ bc mod n. Then…
a ≡ b mod n
Let a, b, c be integers. Suppose a is coprime to b, a | c and b | c. Then…
ab | c
Let a, b, c be integers. Suppose a is coprime to c and b is coprime to c. Then…
ab is coprime to c
What is the Chinese Remainder Theorem?
Let n1, …, nk be natural numbers and a1, …, ak be integers. Suppose hcf(ni, nj) = 1 for all i =/ j. Consider the simultaneous congruences (*):
x ≡ a1 mod n1
…
x ≡ ak mod nk
For every integer s such that the solutions to (*) are given by x ≡ s mod n1…nk
What is the definition of a congruence class?
Let n be a natural number and a be an integer. We define the congruence class of a mod n to be [a]n = {x ∈ Z s.t. x ≡ a mod n}
What are some lemmas about congruence classes?
[a]n = [b]n iff a ≡ b mod n
[a]n = [b]n or [a]n ∩ [b]n = empty set
There are exactly n congruence classes mod n namely [0]n, [1]n, …, [n - 1]n
What is the proof for [a]n = [b]n iff a ≡ b mod n?
Suppose [a]n = [b]n
Then a ∈ [a]n = [b]n
Now suppose a ≡ b mod n. Let x ∈ [a]n
Then x ≡ a mod n and a ≡ b mod n, so x ≡ b mod n. Thus x ∈ [b]n
So [a]n ⊆ [b]n
Similarly, [b]n ⊆ [a]n
Hence, [a]n = [b]n
What is the proof for [a]n = [b]n or [a]n ∩ [b]n = empty set?
Suppose [a]n ∩ [b]n =/ empty set
Let x ∈ [a]n ∩ [b]n
Then x ≡ a mod n and x ≡ b mod n
So a ≡ x mod n and x ≡ b mod n
Thus a ≡ b mod n
Therefore [a]n = [b]n by previous proof
What is the definition of the ring of integers modulo n?
Let n be a natural number. We define Zn = {[a]n : a ∈ Z} = {[0]n, …, [n - 1]n} and addition and multiplication on Zn as follows:
Define [a]n + [b]n = [a + b]n and [a]n . [b]n = [ab]n
The set Zn with + and . is called the ring of integers mod n. [a]n can also be written ā
What are the properties of the ring of integers modulo n Zn?
Let x, y, z belong to Zn
x + y = y + x
x . ( y . z) = (x . y) . z
How do we write a ≡ r mod n?
Let n be a natural number and a be an integer. We write a(mod n) for the unique r ∈ {0, 1, …, n - 1} such that a ≡ r mod n
What is Fermat’s Little Theorem?
Let p be a prime natural number and a be an integer. Suppose p is not a factor of a. Then ap-1 ≡ 1 mod p
What is a corollary of Fermat’s Little Theorem?
Let p be a prime natural number and a be an integer. Then ap ≡ a mod p
Let p, q be distinct prime natural numbers, k be a natural number and a be an integer. Then…
ak(p-1)(q-1)+1 ≡ a mod pq