chapter 2 Modular arithmetic Flashcards
Definition 2.1.1
congruent
Let a, b, m ∈ Z with m > 1. We say that a is congruent to b modulo m, written a ≡ b (mod m),
if a = b + mk for some k ∈ Z. This is equivalent to m | (a − b).
We write a ̸≡ b (mod m) otherwise.
Example 2.1.2. 15 mod 3
19 mod 3
15 ≡ 0 (mod 3); 19 ≡ −2 (mod 3)
Example 2.1.3 (Clocks).
and modular arithmetic
Again, clocks are the prototypical example of modular arithmetic in every day life. To compute which hour will show on your clock b hours from now, you simply find the unique r ∈ {1, . . . , 12} such that r ≡ a + b (mod 1)2, where a is the hour showing up now.
11 oclock what time in 37hrs?
37≡13≡1 mod 12 12:00
Exercise 2.1.4. (1) a ≡ 0 (mod m) if and only if m | a
a ≡ 0 (mod m) means that a =0 +mk=mk for some k ∈ Z, by defn,
and that is exactly the meaning of m | a.
Exercise 2.1.4.
(2) a ≡ b (mod m) if and only if a and b have the same remainder on dividing by m.
means a and b have the same remainder upon division by m
Suppose that a ≡ b (mod m). This is equivalent to m|(a-b). Divide a and b by m and write
a=q_1m+r_1
b=q_2m+r_2
m|(A-b) = (q_1-1_2)m +(r_1-r_2)
thus m|(r_1-r_2).
Recall that 0 ≤ r_i < m, so −m < r_1 − r_2 < m.
(There is only one multiple of m between this)
The only number divisible by m in that interval is 0, so
m | (r1 − r2)
if and only if
r1 − r2 = 0, that is, r1 = r2.
Exercise 2.1.4
(3) Every integer is congruent modulo m to exactly one of the numbers 0, 1, 2, . . . , m −
1.
Alternatively, to exactly one of 1, 2, . . . , m. We say that {0, 1, . . . , m − 1} and {1, 2, . . . , m} are complete sets of residues modulo m.
(3) Let a ∈ Z and r ∈ Z be its remainder in the division by m. By the previous point, a ≡ r (mod m).
Moreover, if r′ ∈ {0, 1, . . . ,m−1}, its remainder by m is r′ itself, so by the previous point a ≡ r′ (mod m) if and only if r′ = r. This shows that there is a unique r′ ∈ {0, 1, . . . ,m − 1} such that a ≡ r′ (mod m).
If we want to find r′ ∈ {1, . . . ,m}, just take r = r′ when r > 0, and
r′ = m when r = 0.
Exercise 2.1.4.
(4) ≡ is an equivalence relation:
(a) a ≡ a for all a (reflexive);
(b) a ≡ b implies b ≡ a (symmetric);
(c) a ≡ b and b ≡ c imply a ≡ c (transitive).
- m | 0, so m | (a − a), meaning that a ≡ a (mod m);
- a ≡ b (mod m) means m | (a − b), but then also m | −(a − b) = (b − a), thus b ≡ a (mod m);
- if a ≡ b (mod m) and b ≡ c (mod m), then m | (a − b) and m | (b − c). This implies also that m | ((a − b) + (b − c)) = (b − c), hence
b ≡ c mod m.
congruence remarks
Every integer is congruent to exactly one of 0,1,…,m-1exactly one of 1,2,…m
n|0
complete sets of residues {1,…,n} and {0,1,…,n-1}
remember working on Z
working on Z with mod 2
evens and odds 2 congruence classes
z is partitioned into 2
n=3 we have 3 congruence classes
{3k:k∈ Z}
{3k+1: k∈ Z} ={…,-2,1,4,7,…}
and
{3k+2:k∈ z}
Arithmetic works nicely in these congruence mod m comparable + and -
Lemma 2.1.5 (Arithmetic of congruences)
The equivalence relation ≡ (mod m) is compatible with addition and multiplication, meaning that:
if a ≡ b and c ≡ d, then a + c ≡ b + d and ac ≡ bd.
PROOF
Arithmetic of congruences)
The equivalence relation ≡ (mod m) is compatible with addition and multiplication, meaning that:
if a ≡ b and c ≡ d, then a + c ≡ b + d and ac ≡ bd
Proof. Take a, b, c, d as in the hypothesis. By assumption, m | (a − b) and m | (c − d). In
particular
m | ((a − b) + (c − d)) = ((a + c) − (b + d))
thus a + c ≡ b + d (mod m). For the product, we need to show that m divides (ac − bd).
We use a trick:
ac − bd = ac − bc + bc − bd = (a − b)c + b(c − d).
Clearly m | (a − b)c + b(c − d), so b | (ac − bd), which means that ac ≡ bc (mod m). □
Example 2.1.6. Show that if a ≡ b and c ≡ d, then a − c ≡ b − d, and also a^k ≡ b^k for all
k = 0, 1, 2, . . .
Since −1 ≡ −1, we also have −c ≡ −d, thus a − c ≡ b − d.
For aᵏ we proceed by induction: clearly a_0 = 1 ≡ 1 = b_0;
if aᵏ ≡ bᵏ, then aᵏ⁺¹ = (aᵏ)a ≡
(bᵏ)b = bᵏ⁺¹, and so by induction aᵏ≡ bᵏ for all k.
Corollary 2.1.7
CONGRUENCE CLASSES
Let Z/mZ be the set of the congruence classes for the equivalence relation ≡ (mod m); said differently, it is the quotient of Z by the relation ≡ (mod m).
Then Z/mZ is a cyclic group under addition of size m.
In group theory, the ‘cyclic group of order m’ is also called Cm. The main difference between C_m and Z/mZ is that the former is just an abstract group, the latter has multiplication as well.
Corollary 2.1.7
CONGRUENCE CLASSES
manual
PROOF
Manual proof. Simply recall that a group is a set with a binary operation which is
associative, has an identity, and every element has an inverse.
* a + (b + c) ≡ (a + b) + c (mod m);
* a + 0 ≡ 0 + a ≡ a (mod m);
* a + (−a) ≡ 0 (mod m).
The set {0, 1, . . . , m − 1} is a complete set of residues and it has size m, so the quotient
has size m. Finally, it is cyclic: its generator is the congruence class of 1.
Corollary 2.1.7
CONGRUENCE CLASSES
group theoretic
PROOF
Group theoretic proof. Note that
{a ∈ Z : a ≡ 0 (mod m)} = {mk : k ∈ Z} = mZ.
The set mZ is obviously closed under addition and inverses, so it is a subgroup of Z.
Thus we can take the quotient group Z/mZ. Now recall the definition of quotient
group: two elements a, b ∈ Z are equivalent if and only if a − b ∈ mZ, thus if and only
if m | (a − b), if and only if a ≡ b (mod m). So the quotient group Z/mZ is exactly the
set of congruences we have discussed so far. Since Z is cyclic (it is generated by 1), then Z/mZ is also cyclic and generated by
the quotient of 1. The size is m because again {0, 1, 2, . . . , m − 1} is a complete set of
residues
(2 cosets of a +mZ=b+mZ holds IFF a-b ∈mZ
overline(a)
The class of a modulo m is typically denoted by a-, or a + mZ, or [a].
Lemma 2.1.8 (Inverses and cancellation)
gcd(a, m) = 1 if and only if there exists b ∈ Z with ab ≡ 1 (mod m).
In particular, if gcd(a, m) = 1 and ax ≡ ay (mod m), then x ≡ y (mod m)
(Any integer coprime to m is invertible mod m)
PROOF
gcd(a, m) = 1 if and only if there exists b ∈ Z with ab ≡ 1 (mod m).
In particular, if gcd(a, m) = 1 and ax ≡ ay (mod m), then x ≡ y (mod m)
Proof. Suppose that gcd(a, m) = 1. By Bézout’s Lemma, there are s, t ∈ Z such that
sa + tm = 1. Let b = s: by definition, ab ≡ 1 (mod m). Conversely, suppose that
there is some b such that ab ≡ 1 (mod m). Then ab = 1 + km for some k ∈ Z, that is,
ab − km = 1, thus the greatest common divisor of a and m is 1.
necessary condition for inverse b of a mod m
Note that the condition gcd(a, m) = 1 is necessary: for instance, 8 ≡ 12 (mod 4), but
4 ̸≡ 6 (mod 4)!
Exercise 2.1.9. Show that if gcd(a, m) > 1, there are x, y ∈ Z such that ax ≡ ay
(mod m) and x ̸≡ y (mod m).
Let d ∈ N be the greatest common divisor of a and m. Then a(m/d)≡
0 ≡ a(2m/d) (mod m).
Now suppose that d > 1.
Then
m/d̸ ≡ 0 (mod m) and so
x := 2(m/d)̸≡ m/d =: y (mod m) satisfy the desired conclusion.
Exercise 2.1.10. Show that p is prime if and only if for every a ∈ Z, either a ≡ 0 (mod p) or there is b ∈ Z with ab ≡ 1 (mod p).
For every a ∈ Z we have either gcd(a, p) = 1 or gcd(a, p) = p, because those are the only positive divisors of p. In the former case, there is b such that ab ≡ 1 (mod p); in the latter, a ≡ 0 (mod p).
GROUP corollary under x
Corollary 2.1.11. The set
(Z/mZ)×
:= {a ∈ Z/mZ : gcd(a, m) = 1}
is well defined and it is a group under multiplication
checking group axioms: associativity a +b+c ≡a+b+c mod m
operation is taking representatives of equivalence classes and + mod m of congruence
inverse a+ -a ≡0 mod m
PROOF
Corollary 2.1.11. The set
(Z/mZ)×
:= {a ∈ Z/mZ : gcd(a, m) = 1}
is well defined and it is a group under multiplication
Proof. First, we need to check that if a- = b-, then gcd(a, m) = 1 implies gcd(b, m) = 1.
Indeed, if gcd(a, m) = 1 there is c such that ac ≡ 1 (mod m), but then bc ≡ ac ≡ 1 (mod m) too, hence gcd(b, m) = 1.
Next, recall that multiplication in Z/mZ is associative, just because it was on Z:
a(bc) ≡ (ab)c (mod m). Likewise, 1 is the multiplicative identity, and of course
1 ∈ (Z/mZ)× , because gcd(1, m) = 1.
Finally, if a, b are coprime with m, then gcd(ab, m) = 1 by Corollary 1.1.12, so (Z/mZ)× is closed under multiplication. Moreover, for each a ∈ (Z/mZ) × , there is b ∈ Z/mZ
such that ab ≡ 1 (mod m); such b must necessarily be in (Z/mZ)×
as well. Therefore,
(Z/mZ)× is a group under multiplication.
remark 2.1.12 rings
Remark 2.1.12. The quotient of Z/mZ is actually a ring, that is to say, a set with a sum and product satisfying certain properties (associativity, distributivity, etc). (In fact, if you know rings, you can verify that mZ is an ideal of Z, and so quotienting by mZ
gives us a ring.)
We do not use this language now, for simplicity, but keep this idea in the background: we will talk again about rings towards the end of the module
Example 2.2.1 (Digits). Since 10 ≡ 1 (mod 9), we have 10^n ≡ 1^n = 1 (mod 9) for any n.
checking a numbers sum of digits
Therefore, every number is congruent to the sum of its digits modulo 9:
10^n d_n + 10^{n-1}d_n +…+ d_0 ≡ d_n + · · · + d_0 (mod 9).
For instance, 3456 =
10^3· 3 + 10^2· 4 + 10 · 5 + 6
≡ 1^3· 3 + 1^2· 4 + 1 · 5 + 6 = 18 ≡
1 + 8 = 9 ≡ 0 (mod 9).
as 10 ≡1 mod 9
10^n ≡1^n =1 mod 9
any integer is congruent mod 9 to the sum of its digits
9|171 as 9 | 1+7+1
Example 2.2.2 (Yet more digits). Let us compute the decimal expansion
0.q₁q₂q₃…. of 1/7
each q_k computed as follows
* we start with r_0 = 1, the numerator of 1/7 ; note that 0 ≤ r_0 < 7 (otherwise we would have to do some extra steps!);
- inductively, divide 10r_k by 7 and find quotient q_{k+1}, remainder r_{k+1}
. You can check this manually: 10 = 1 · 7 + 3, thus q1 = 1, r1 = 3; 30 = 4 · 7 + 2, so q2 = 4,
r2 = 2, and so on.
By construction, r_{k+1} ≡ 10r_k (mod 7), thus r_k ≡ 10^k (mod 7). But now we notice that
10^6 ≡ 1 (mod 7): indeed, 10^6 ≡ 3
6 ≡ 2^3 = 8 ≡ 1 (mod 7). Therefore, r_6 = 1, and
more generally r_{k+6} = r_k. In particular, q_{k+6} = q_k , so the expansion is periodic with
period of length (a divisor of) 6. The length is exactly 6 because you can also check that none of 10, 10^2, . . . , 10^5 are congruent to 1 modulo 7.
if you evaluate it it comes in blocks of 6, period of 6. so 10^6=1+7k some k and 6 is least period with the property
period of 1/7 is the smallest r s.t 10^r=1+7k for some k
checking powers of 10 congruent to mod 7 we find this
Exercise 2.2.3. Compute the length of the period of 1/3,1/9,1/11 just by looking at the least k > 0 such that 10k ≡ 1 modulo respectively 3, 9, and 11. What happens for 1/2?
leads to fermats little thm….
Fermat’s little theorem
thm 2.2.4
Let p be a prime and a ∈ Z such that p ∤ a.
Then aᵖ−¹ ≡ 1 (mod p)
whenever p is prime and we take an integer coprime to p
then it’s p-1 th power is congruent to 1 mod p
any integer as long as its not divisible by p
PROOF of Fermat’s little theorem
Let p be a prime and a ∈ Z such that p ∤ a. Then a
p−1 ≡ 1 (mod p)
write down
Group theoretic proof. By Corollary 2.1.11, the congruence classes of 1,…, p − 1 form a group under multiplication. Its size is p − 1 by Exercise 2.1.10: by Lagrange’s theorem, ap−1 ≡ 1 (mod p)forevery element of the group. □ Combinatorial proof. The numbers a,2a,3a,…,(p −1)a are not divisible by p, so they are not congruent to 0 modulo p. Moreover, if ra ≡ sa (mod p), then r ≡ s (mod p) by Lemma2.1.8, since gcd(a, p) = 1. It follows that the numbers a,2a,3a,…,(p −1)a are just some permutation of 1,2,…,(p −1) modulo p. In particular ap−1(p −1)! = p−1 ∏ k=1 ak ≡ p−1 ∏ k=1 k =(p−1)! (mod p). But (p−1)! is also not divisible by p, so by Lemma 2.1.8 again, we can cancel it out and f ind that ap−1 ≡ 1 (mod p). □ Extra. As it turns out, Fermat did not prove this theorem either. Exercise 2.2.5. Show that the decimal expansion of 1 p for p prime different from 2, 5 has period of length at most p −1 (and must divide p−1).
Alt form of Fermat’s little theorem
(Corollary 2.2.6 (Alternative form of Fermat’s Little Theorem).)
p prime, a ∈ Z
implies
Then aᵖ ≡ a (mod p)
(any integer, could be divisible by p!)
(comes from the fact that if p doesnt divide a then we can divide both sides by a; if it is then its congruent to 0 mod p
PROOF for
Corollary 2.2.6 (Alternative form of Fermat’s Little Theorem).
If p | a, then a ≡ 0 and a
p ≡ 0; otherwise p ∤ a, thus aᵖ⁻¹ ≡ 1, hence aᵖ ≡ a just
by multiplying both sides by a.
Applications of Fermat’s little thm
Exercise 2.2.5. Show that the decimal expansion of 1/p for p prime different from 2, 5 has period of length at most p − 1 (and must divide p − 1)
We have seen that the length of the period is the least positive integer k such that
10ᵏ ≡ 1 (mod p)
(provided p ∤ 10).
By Fermat’s Little Theorem, we also have 10ᵖ−¹ ≡ 1 (mod p) (again we use that p ∤ 10).
As k is the least integer p-1 must be divisible by k.
Now divide p − 1 by k, that is write p − 1 =qk + r where 0 ≤ r < k. Then
1 ≡ 10ᵖ−¹ = (10ᵏ)ᵠ10ʳ ≡ 10ʳ (mod p). By minimality
of k, we must have r = 0, that is k | p − 1.
Proposition 2.2.8.
every prime factor of 2ʳ-1 has
Let r > 2 be a prime. Then every prime factor of 2ʳ − 1 is of the form
2kr + 1.
prop 2.2.8 proof
Let r > 2 be a prime. Then every prime factor of 2ʳ − 1 is of the form
2kr + 1.
Let r>2 prime, take p prime divisor of 2ʳ − 1.
Suppose that p | 2ʳ − 1 for some prime p. This means 2ʳ ≡1 (mod p),
By Fermat’s little theorem we have that 2ᵖ⁻¹≡1 (mod p).
2ʳ − 1 is odd so p>2, so gcd(p,2)=1 ( so p ∤2).
(we have two ≡ here now similar to prev proof)
We claim r | p − 1, we assume otherwise and look for a contradiction.
Suppose that r ∤ p − 1.
Since r is prime, gcd(r, p-1)=1 thus by lemma 2.1.8 there is a b ∈ Z such that (p − 1)b ≡ 1 (mod r).
b can be replaced with any number congruent to b, so we can assume b>0.
We have found b s.t (p − 1)b = 1 + rk for some k ∈ Z, and actually k > 0 since
b > 0. Then
(2⁽ᵖ⁻¹⁾)ᵇ ≡ (1)ᵇ= 1 (by FLittleT)
= 2¹⁺ʳᵏ = 2 . (2ʳ)ᵏ (by (p − 1)b = 1 + rk)
≡2 (1ᵏ).2 (by 2ʳ ≡1 mod p)
thus 1≡2 mod p implies 1≡0 mod p
p does not divide 2, p is prime gives our contradiction
mod p
“typo in notes mod r should be mod p”
notes:
1 = 1ᵇ ≡ 2⁽ᵖ⁻¹⁾ᵇ = 2¹⁺ʳᵏ
= 2 · (2ᵏ)ʳ ≡ 2 (mod r),
a contradiction since {0, . . . ,r − 1} is a complete set of residues modulo r.
We must then have r | p − 1. Since p is odd, p − 1 is even, and by assumption r is odd, so gcd(2,r) = 1, thus 2r | p − 1. By defn of divisibility , p = 2kr + 1 for some k ∈ Z.
Exercise 2.2.7 (in exercise sheet).
Let r ∈ N. Prove that if 2ʳ − 1 is prime, then r is prime
not gone through? .
Mersenne prime
2ʳ − 1 if 2ʳ − 1 is prime
we also know this implies r is prime
e.g
2²-1=3
2³-1=7
2⁵-1= 31
2⁷-1=127
however
2¹¹-1 is divisible by 23
The largest known prime number (as of January 2024) is
2²⁸²,⁵⁸⁹,⁹³³ − 1, a Mersenne prime (the 51st, to be precise).
ex Find the smallest prime divisor of 2²³ -1
Example 2.2.9. We have seen that 23 | 2¹¹ − 1, and indeed 23 = 2 · 1 · 11 + 1. What about
2²³ -1? Is it prime?
By proposition every prime factor of 2²³ -1 is of the form 46k+1
The first prime in this form r=47. Thus we work in mod 47:
2⁵=32≡-15
2¹⁰=(2⁵)²≡(-15)² = 225 ≡ 37=-10
2²⁰=(2¹⁰)²≡ (-10)²=100≡6
2²³=6.8=48≡1
Showing 47 divides 2²³ -1 and so 2²³ -1 isn’t prime
Theorem 2.3.1 (Wilson’s Theorem (al-Haytham c. 1000))
If p is prime, then (p − 1)! ≡ −1 (mod p).
Example 2.3.2.
using Wilson’s thm p=11
p=11 and is prime then
10! ≡−1 (mod 11).
as seen
2 · 6 ≡ 3 · 4 ≡ 5 · 9 ≡ 7 · 8 ≡ 1 (mod 11)
(bc p is prime these numbers will have an inverse)
thus
10! =1.2.3.4.5.6.7.8.9.10≡ 10 ≡ −1
Corollary 2.3.3. of Wilson’s thm
If p is prime, then the congruence equation x²≡ −1 (mod p) has a
solution if and only if p = 2 or p = 4k + 1 for some k ∈ Z (that is, p ≡ 1 (mod 4)).
Wilsons thm proof
If p is prime, then (p − 1)! ≡ −1 (mod p).
For every a ∈ {1, . . . , p − 1}, there is a unique
b ∈ {1, . . . , p − 1} such that ab ≡ 1 (mod p).
(inverse exists in integers, unique as p is prime )
Whenever a ̸≡ b, both a and b appear in
(p − 1)!, and we can cross them off
(p-1)!= ∏ₐ₌₁ᵖ⁻¹ a ≡ ∏ₐ₌₁, ₐ₂≡₁ ᵖ⁻¹ of a
(remove values with inverse, keep those s.t a is own inverse)
which a’s satisfy a²≡1?
occurs iff p | (a² − 1) = (a + 1)(a − 1). Since p is prime, we have either p | (a + 1) or p | (a − 1), that is a ≡ ±1
thus
= 1 · (p − 1) = p − 1
proof of corollary of Wilson’s
If p is prime, then the congruence equation x² ≡ −1 (mod p) has a solution
if and only if
p = 2 or p = 4k + 1 for some k ∈ Z (that is, p ≡ 1 (mod 4)).
if p=1 then x=1 is a sol
case: p>2 and focus on p odd and p-1 even
Suppose there is a solution a s.t a² ≡ −1 (mod p) . By FLittleT,
1≡aᵖ⁻¹ (mod p), because p cannot divide a by the assumption of it being a solution to the above.
re-write as p is odd:
1≡aᵖ⁻¹= (a²)⁽ᵖ⁻¹⁾/² ≡(-1)⁽ᵖ⁻¹⁾/² (mod p)
since 1 is not congruent to -1 mod p: (p-1)/2 must be divisible by 2 as must be even, thus 4 |(p − 1).
conversely:
Suppose p ≡ 1 (mod 4)
(p − 1)! = 1 · 2….(p-1)/2 . (p+1)/2….(p-2).(p-1)
(p is odd, we split in half, we know ≡ by subtracting p from factors in the last half)
≡1 · 2….(p-1)/2 .[-(p-1)/2]….(−1) · (−1)
=( (p-1)/2))!· (-1)⁽ᵖ⁻¹⁾/² ( (p-1)/2))!·
= (( (p-1)/2))!)² · (-1)⁽ᵖ⁻¹⁾/²
Now by Wilsons, LHS ((p − 1)!) congruent to -1 and (p-1)/2 is even by assumption thus (-1)⁽ᵖ⁻¹⁾/² ≡ 1.
Follows that x = ((p-1))/2)! satisfies the eq
Theorem 2.4.1 (Chinese Remainder Theorem (Qin Jiushao 秦九韶, 1247))
If m₁, . . . , mₖ are pairwise coprime integers and a₁, . . . , aₖ ∈ Z, then the simultaneous congruences
x ≡a₁ (mod m₁)
x ≡a₂ (mod m₂)
…
x ≡aₖ (mod mₖ )
have a solution x ∈ Z. Moreover, any two solutions are congruent modulo m₁, . . . , mₖ
we say sol is unique up to congruence modulo m₁, . . . , mₖ’
.
background my exercises:
Find x such that 3x ≡ 7 (mod 10)
multiplicative inverse for 3 mod 10 are
3ᵠ⁽¹⁰⁾−¹. and q(10)=4 so the inverse of 3 mod 10 is
3³≡ 27 ≡ 7 (mod 10)
take eq and multiply both sides by 7
x ≡ 49 ≡ 9 (mod 10)
x=9
background ex:
Find x such that 3x ≡ 6 (mod 12).
no multiplicative inverse
if there is a sol this means 3x-6 is divisible by 12, so there is some k ∈ Z s.t 3x-6=12k. Working in integers we can divide by 3. x-2=4k hence x ≡ 2 (mod 4)
background ex:
Example 5. Use the Chinese Remainder Theorem to find an x such that
x ≡ 2 (mod 5)
x ≡ 3 (mod 7)
x ≡ 10 (mod 11)
N=5x7x11=385
m_1=N/5=77
m_2=N/7=55
m_3=N/11=35
seek multiplicative inverse for each m_i mod n_i
m_1 ≡ 77 ≡ 2 (mod 5) has inverse y_1=3
m2 ≡ 55 ≡ 6 (mod 7), inverse to m_2 mod n_2 is y_2 = 6
m3 ≡ 35 ≡ 2 (mod 11), an inverse to m3 mod n3 is y3 = 6.
Therefore, the theorem states that a solution takes the form:
x = y_1b_1m_1 + y_2b_2m_2 + y_3b_3m_3
= 3 × 2 × 77 + 6 × 3 × 55 + 6 × 10 × 35 = 3552.
Since we may take the solution modulo N = 385, we can reduce this to 87, since 2852 ≡87 (mod 385).
Example in lecture: find the solution for x s,t
x ≡2 mod 3
x ≡3 mod 5
x=8, x=23 is a sol by deduction but…
by thm:
x=3y_1+ 5y_2
found by solving
5y_2 ≡ 2 mod 3
cancels out as 5 ≡ 2
3y_1 ≡ 3 mod 5
y_1=1
y_2=1
x=8 is a solution
Example in lecture: find the solution for x s,t
x ≡2 mod 3
x ≡4 mod 9
3 and 9 not coprime
(4+3(3k)= 2+3(m) ???)
has no solution as this means
x ≡2 mod 3
x ≡4 mod 9 means x ≡1 mod 3 which doesn’t work
Proof for chinese remainder theorem
If m₁, . . . , mₖ are pairwise coprime integers and a₁, . . . , aₖ ∈ Z, then the simultaneous congruences
x ≡a₁ (mod m₁)
x ≡a₂ (mod m₂)
…
x ≡aₖ (mod mₖ )
have a solution x ∈ Z. Moreover, any two solutions are congruent modulo m₁, . . . , mₖ
we say sol is unique up to congruence modulo m₁, . . . , mₖ
.
Base case k=2:
take x of the form x=m₁y₁+m₂y₂
so we have
x ≡ m₁y₁=a₂ mod m₂ (1)
x ≡ m₂y₂ =a₁ mod m₁ (2)
2 equations in 2 vars (e.g solving m₁y₁=a₂ and we know m₁ coprime to m₂)
(notes: By lemma 2.1.8 there are c and b s.t.)
Take c s.t m₂c≡1 (mod m₁)
Take b s.t m₁b≡1 (mod m₂)
thus
y₂ ≡ca₁ mod m₁
y₁ ≡ba₂ mod m₂ (from y₁=(1)y₁ ≡(m₁b)y₁= (m₁y₁)b ≡ba₂)
use x = m₁ba₂+ m₂ca₁
as a solution
For k>2 reason by induction:
Find y s.t
y solves system up to k-1
y ≡a₁ (mod m₁)
y ≡a₂ (mod m₂)
…
y ≡aₖ₋₁ (mod mₖ₋₁ )
Then solve system
x≡y mod m₁, . . . , mₖ₋₁
x≡aₖ mod mₖ
notes give slightly different proof?
Finally we show the solution is unique, suppose that x, y are two solutions. In particular, x − y ≡ 0 (mod mᵢ) for every i=1,…,k
thus we have mᵢ |(x − y). Since the mᵢ’s are pairwise coprime, it follows that m₁· … · mₖ| (x − y), that is, x ≡ y (mod m₁· … · mₖ )
Group theory interpretation approach: chinese remainder thm proof
The thm is saying that if we take the group
(Z/(m₁· … · mₖZ), +) under addition
(integers mod m_1 to m_k)
we have (m₁· … · mₖ) elements as elements are represented by 0,1,2,…m_1?m_k-1???
“this is isomorphic to the
group product” of each group with m_1 elements x…. x m_k elements
the group
{Z/m_1Z x …. x Z/ m_kZ} set as the cartesian product
number of tuples is m_1· … · mₖ
This is a bijection between the cartesian product partition of congruence classes modulo m_1 to m_k
and congruence classes between m_1 to m_k
Why is it true: We have seen that the length of the period is the least positive integer k such that
10^k = 1 (mod p)
(provided p doesn’t divide 10).
This statement is a consequence of Fermat’s Little Theorem. It states that if
p is a prime number not dividing 10, then
10^{p−1}
≡1
(mod p). Therefore, the length of the period (or the order of 10 modulo
p) must divide p−1.
Wilson’s thm example corollary
Example 2.3.4. Start with p = 13 ≡ 1 (mod 4). Take x = (p−1)/2 ! = 6! = 720 ≡ 5 2
(mod 13)
Indeed we have 5^2 = 25 ≡ −1 (mod 13)
