CS2050 L17 Chinese Remainder Theorem
Overview
Abrahim Ladha develops the Chinese Remainder Theorem (CRT), proving that congruences with pairwise coprime moduli have exactly one solution modulo the product of those moduli. He derives a constructive solution formula, demonstrates two solving methods, applies CRT to powers of 6 modulo 10, and uses its bijection between groups of units to prove that Euler's totient function is multiplicative for coprime inputs.
Key takeaways
- For pairwise coprime moduli n1 through nk, a system x = ri modulo ni has exactly one solution modulo their product N, although infinitely many integer representatives exist.
- A constructive CRT solution is x = sum of ri(N/ni)ui, where ui is the inverse of N/ni modulo ni; for 2 modulo 3, 3 modulo 5, and 2 modulo 7, this produces 233, or 23 modulo 105.
- The successive-substitution method solves the same example by writing x = 7k + 2, deriving k = 3 modulo 5, and then obtaining x = 105r + 23.
- Factoring 10 into 2 and 5 simplifies the powers-of-6 problem: for every positive n, 6^n is 0 modulo 2 and 1 modulo 5, so CRT gives 6 modulo 10.
- For coprime m and n, the map from units modulo mn to pairs of units modulo m and n is bijective by CRT, which proves Euler's identity phi(mn) = phi(m)phi(n).
Chapters
- An old Chinese examination riddle asks for a number leaving remainder 2 modulo 3, remainder 3 modulo 5, and remainder 2 modulo 7.
- The number 23 satisfies all three conditions, motivating the question of whether the solution is unique.
- For pairwise relatively prime moduli n1 through nk, the system x = ri modulo ni has a unique solution modulo N = n1 times ... times nk.
- For moduli 3, 5, and 7, N is 105, so 23 and 128 represent the same solution class.
- Abrahim Ladha motivates the construction with terms such as a times 5 times 7, which vanish modulo 5 and 7 while remaining visible modulo 3.
- Pairwise coprimality guarantees the needed modular inverses, allowing each term to be adjusted to produce its target remainder without disturbing the others.
- If gcd(a,n) = gcd(b,n) = 1, then ab also has an inverse modulo n, so gcd(ab,n) = 1.
- Define N as the product of all moduli and Ni = N/ni; pairwise coprimality ensures Ni has an inverse ui modulo ni.
- Set x = sum of ri Ni ui. Modulo ni, every term except the ith vanishes, and Ni ui is congruent to 1, leaving ri.
- If x and x' both solve the system, then each ni divides x - x' because both numbers have the same remainder modulo ni.
- For coprime a and b, if both divide a number, their product divides it; the proof uses Bezout's identity to establish this lemma.
- Applying the lemma across the pairwise coprime moduli shows N divides x - x', so the solutions are congruent modulo N.
- For remainders (2, 3, 2) modulo (3, 5, 7), the complementary products are N1 = 35, N2 = 21, and N3 = 15.
- The required inverses are 35^-1 = 2 modulo 3, 21^-1 = 1 modulo 5, and 15^-1 = 1 modulo 7.
- The construction gives x = 2·35·2 + 3·21·1 + 2·15·1 = 233, which reduces to 23 modulo 105.
- Start with x = 2 modulo 7, so write x = 7k + 2; the condition modulo 5 gives 2k = 1 modulo 5, hence k = 3 modulo 5.
- Writing k = 5l + 3 yields x = 35l + 23; the condition modulo 3 reduces to 2l = 0, hence l = 0 modulo 3.
- Therefore x = 105r + 23, recovering the solution 23 modulo 105 without building the full inverse table.
- Factor 10 into the coprime moduli 2 and 5, replacing one congruence modulo 10 with two simpler congruences.
- For every n at least 1, 6^n is congruent to 0 modulo 2 and 1 modulo 5, since 6 is 0 modulo 2 and 1 modulo 5.
- CRT recombines those conditions as 6^n = 6 modulo 10, proving every positive power of 6 ends in the digit 6.
- The group of units modulo n contains residues a with 1 <= a < n and gcd(a,n) = 1; its size is denoted phi(n).
- Examples include phi(2) = 1, phi(5) = 4, phi(6) = 2, and phi(8) = 4, showing that phi is not monotonic.
- The lecture targets the identity phi(mn) = phi(m)phi(n) when gcd(m,n) = 1, while noting it can fail for noncoprime inputs such as 4 and 2.
- For coprime m and n, define F on units modulo mn by sending c to the pair (c modulo m, c modulo n).
- If gcd(c,mn) = 1, then c is relatively prime to both m and n, so the map lands in the product of the two unit groups.
- Showing this map is a bijection will let CRT translate a congruence theorem into a counting formula for phi.
- Surjectivity follows from the existence part of CRT: for any pair of units a modulo m and b modulo n, some c satisfies both congruences.
- If F(c) = F(c'), then c and c' agree modulo both m and n; CRT uniqueness makes them congruent modulo mn.
- Thus CRT existence proves surjectivity and CRT uniqueness proves injectivity.
- The bijection equates the number of units modulo mn with the size of the Cartesian product of the unit groups modulo m and n.
- For finite sets, the size of a Cartesian product is the product of the set sizes, yielding phi(mn) = phi(m)phi(n) when gcd(m,n) = 1.
- The theorem's existence and uniqueness results therefore establish both how to solve congruences and how to count coprime residues.
Transcript excerpt
0:00 All right, let's just get started. This is CS 2050. The topic of today is the Chinese Remainder Theorem. Really a classic. It's a very important theorem. I think there were some points when I was a grad student that I would have to use this like once a week, maybe something like this. Very powerful, very important theorem. Well, first of all, why is it called that? Isn't that kind of I mean, why do we call things anything, right? So, the history of this is that there was a in I think in the 1200s or something, there was some examinations that were found in scrolls that were buried. Archaeologists had found this riddle. And it was
0:48 actually part of like an entrance exam to be a Chinese bureaucrat in the emperor's palace interior palace or something, right? The The riddle goes something like this. There are an unknown number of things. When divided by two, sorry, divided by three, there are two left over. When divided by five, there are three left over. And when divided by seven, there are two left over, right? How many things are there?
1:44 Right? So, this is the problem. You have an unknown number of things. And it's stated as when divided by three, there are two left over. But today we can formalize this as as what? In modern notation, how would I how would I express this sentence? Yeah. So, if X is some unknown number of things, it should be congruent to two mod three. Right? Similarly for the others, this unknown number X should be congruent to three mod five. And X should be congruent to two mod seven. Okay. Give me a solution to the system of linear congruences. Yeah.
2:34 Yes. If is 23 two plus a multiple of three?
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
In this course
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Abrahim Ladha.