Errichto Algorithms · YouTube · 8:48
This 150-second whiteboard lesson solves the system x ≡ 3 (mod 4), x ≡ 5 (mod 6), x ≡ 2 (mod 5) by an iterative search method. It first lists numbers congruent to 3 modulo 4, then picks the first one also congruent to 5 modulo 6, namely 11. The solution family for the first two congruences is advanced by LCM(4,6)=12, giving 11, 23, 35, 47, ... , and the first term congruent to 2 modulo 5 is 47. The video then states that all solutions are 47 plus multiples of LCM(4,6,5)=60, and finally generalizes the same pattern to a four-congruence system using and LCM(,,). This 150-second whiteboard segment teaches a practical Chinese Remainder Theorem workflow built around least common multiples. It first shows that once some congruences are solved, all compatible candidates form an arithmetic progression whose step is the LCM of the moduli already combined. The speaker then distinguishes the coprime case, where LCM(a,b)=ab, from the non-coprime case, using 5 and 12 versus 4 and 6 to show why replacing LCM by the product can skip valid solutions such as 47. Two computation methods for LCM(4,6) are demonstrated: listing multiples until reaching 12, and using the formula LCM=ab/GCD. In the final worked example, the system x≡1 (mod 4), x≡0 (mod 3), x≡1 (mod 5), x≡3 (mod 7) is reordered so the equal-remainder congruences come first. From x≡1 (mod 4) and x≡1 (mod 5), the solution progression 1, 21, 41, ... is obtained because LCM(4,5)=20. The clip ends after selecting 21 as the first term satisfying x≡0 (mod 3); the modulo-7 step is not completed within this segment. This video demonstrates a constructive method for solving a system of four linear congruences using the Chinese Remainder Theorem principles. The presenter iteratively combines conditions: first merging moduli 4 and 5 to get a step size of 20, then incorporating modulus 3 to update the step to 60. To handle the final modulus 7 without computing large numbers, a 'remainder trick' is used, generating a sequence of residues modulo 7 until the target is found. This identifies the correct term in the arithmetic progression, yielding the solution 381. Finally, the general solution period is calculated as LCM(60,7)=420. This video segment demonstrates the constructive method for solving a system of linear congruences using the Chinese Remainder Theorem. It highlights the periodic nature of remainders when iterating with a step size coprime to the modulus, proving that a solution must appear within 'm' steps or not at all. The segment concludes by analyzing the algorithmic time complexity of this iterative approach, which is linear with respect to the sum of the moduli.
Use the learning inspector for key ideas and moments, or open the reading tabs for the complete notes.
Generated from the video's visuals and explanation; not verbatim speech.
The clip opens with a concrete system of three congruences written on a black board: x ≡ 3 (mod 4), x ≡ 5 (mod 6), x ≡ 2 (mod 5). Blue arrows label 3 as the remainder and 4 as the modulus, so the viewer is told how to read each line before the solution begins.
The first move is to isolate one condition at a time. To satisfy x ≡ 3 (mod 4), the presenter writes the arithmetic progression 3, 7, 11, ... and notes that adding 4 never changes the remainder modulo 4. This is the basic building block of the method: one congruence gives an infinite family of candidates.
Next, the presenter intersects that family with the second congruence x ≡ 5 (mod 6). The candidates are tested in order: 3 fails, 7 leaves remainder 1 modulo 6, and 11 leaves remainder 5. Thus 11 is identified as the first number satisfying the first two congruences simultaneously.
The video then emphasizes that 11 is not unique. Once two congruences are satisfied, the whole joint solution set is obtained by adding a number divisible by both moduli already used. Since LCM(4,6)=12, the new progression becomes 11, 23, 35, ... with step 12. This is the central iterative rule of the method.
With the first two conditions folded into one sequence, the presenter searches that sequence for the first term meeting the last congruence x ≡ 2 (mod 5). The checks are explicit: 11 ≡ 1 (mod 5), 23 ≡ 3 (mod 5), 35 ≡ 0 (mod 5), and then 47 ≡ 2 (mod 5). Therefore 47 is declared the smallest solution of the full three-congruence system.
The final numerical step is to describe all solutions, not just the smallest one. The presenter computes LCM(4,6,5)=60, explaining that this is the same as taking the previous step 12 and the new modulus 5 and computing their LCM. Hence the complete displayed family is 47, 107, 167, 227, ... , i.e. .
The last section abstracts the procedure. The board replaces the concrete numbers with a four-line system x ≡ (mod ) and writes the sequence , +LCM(,,), ·LCM(,,), ... . The speaker explains that after solving the first three congruences, one scans this progression for the first term satisfying the fourth congruence, calls that term a, and indicates that the process would continue in the same way. The clip ends before the next full formula after a is completed.
The segment opens on a general CRT system with four congruences in x. The key visual point is that after solving part of the system, the remaining candidates are not arbitrary: they form an arithmetic progression. The board writes , +LCM(,,), ·LCM(,,), ... and then indicates that after incorporating the fourth modulus one again gets a new starting value a and a new step given by an LCM.
The discussion then isolates the rule for coprime moduli. The formula on screen is LCM(a,b)= if a and b are coprime, and the example LCM(5,12)=60 shows the shortcut in action. This matters for CRT because the step between compatible solutions is exactly the LCM of the moduli already combined.
Immediately afterward, the speaker warns that the product rule fails when the moduli share a divisor. The pair 4 and 6 is used as the counterexample: their product is 24, but their least common multiple is only 12. The board then illustrates the consequence of using 24 as the step by writing the progression 11, 35, 59, ... and noting that 47 is skipped. This is the central misconception the segment corrects.
To compute the correct LCM for non-coprime numbers, the video first uses a concrete search method. Multiples of 4 are listed as 4, 8, 12, ... and the first one divisible by 6 is 12, so LCM(4,6)=12. This is a direct numerical realization of the definition of least common multiple.
The alternative general formula is then written: LCM = / GCD. Applying it to 4 and 6 gives gcd(4,6)=2 and therefore LCM(4,6)=. This connects the special coprime product rule to the broader arithmetic identity relating LCM and GCD.
A larger worked example appears: x ≡ 1 (mod 4), x ≡ 0 (mod 3), x ≡ 1 (mod 5), x ≡ 3 (mod 7). The first methodological trick is reordering the congruences. Since the system is simultaneous, permutation does not change the solution set. The speaker moves x ≡ 1 (mod 5) upward so that the two congruences with remainder 1 are adjacent.
With x ≡ 1 (mod 4) and x ≡ 1 (mod 5) together, the common solution is immediate: works for both. The combined solution set is then 1 plus multiples of LCM(4,5). Because 4 and 5 are coprime, that LCM is 20, so the progression becomes 1, 21, 41, ... . This is the CRT step sequence in practice.
The next task is to satisfy x ≡ 0 (mod 3). One scans the progression 1, 21, 41, ... for the first term divisible by 3. The term 1 fails, but 21 succeeds, so 21 becomes the first common solution of the first three congruences. The clip ends here, before the modulo-7 congruence is processed and before the updated LCM after including modulus 3 is written out.
We begin with a system of congruences. The screen displays and . Combining these, we note that any number satisfying both must differ by a multiple of . Since 1 works, the sequence of candidates is , denoted on screen as .
Next, we incorporate the condition . We check the candidates from the previous step. 1 is not divisible by 3, but 21 is. Thus, 21 becomes our new starting point. The step size updates to . Since 20 and 3 are coprime, the new step is . The candidate sequence becomes , shown as .
Finally, we must satisfy . Checking large numbers like 81, 141, etc., is tedious. Instead, we use a remainder trick. We look at the sequence modulo 7. The start 21 gives . The step 60 gives . So, each subsequent term adds 4 to the remainder modulo 7.
We generate the remainder sequence: Start at 0. Add 4 to get 4. Add 4 to get . Add 4 to get 5. Add 4 to get . Add 4 to get 6. Add 4 to get . We have reached the target remainder 3. On screen, this sequence is written as with indicated.
Counting the steps from the start (0), it took 6 additions of 4 to reach 3. This corresponds to the 6th term in our arithmetic progression . Calculating this value: . This is our particular solution.
To describe all solutions, we find the period of the entire system. This is . Since 60 and 7 are coprime, the period is . Thus, the general solution is . The next solution would be . The presenter reminds us that the product rule for LCM only applies when numbers are coprime.
Beyond the basic solution, observe the sequence of remainders generated when testing values against the modulus 7. Starting from 21, the remainders are 0, 4, 1, 5, 2, 6, 3.
Because the step size (60) and the modulus (7) are coprime, these remainders form a complete cycle covering all residues from 0 to 6. The sequence repeats indefinitely.
This periodicity implies a strict bound on the search: you only need to check at most values. If the target remainder hasn't appeared by then, no solution exists for that congruence.
From a programming perspective, this defines the algorithm's efficiency. The time complexity is determined by the sum of the moduli, expressed as , since each stage requires at most iterations.
The opening board presents three modular conditions on the same unknown x. The labels remainder and modulus identify the roles of the numbers in x ≡ 3 (mod 4), so the problem is to find an integer x whose remainders modulo 4, 6, and 5 are respectively 3, 5, and 2.
To satisfy a single congruence, start from one valid representative and keep adding the modulus. In the example, all numbers of the form satisfy the first condition, which is why the board writes 3, 7, 11, ... (+4).
Instead of solving algebraically at once, the method tests the current progression against the next congruence. Here 3 and 7 fail modulo 6, while 11 succeeds, so 11 becomes the first simultaneous solution of the first two conditions.
After two congruences are satisfied, any further increment must be divisible by both moduli to preserve both remainders. The smallest positive such increment is their least common multiple, so the joint solution family advances by 12: 11, 23, 35, ... .
The sequence of simultaneous solutions to the first two congruences is then scanned against the third congruence. The values 11, 23, and 35 do not leave remainder 2 modulo 5, but 47 does, so 47 is the smallest solution to all three conditions.
Once 47 satisfies the whole system, the complete family is obtained by adding the least common multiple of all three moduli. The video computes this as 60 and lists 47, 107, 167, 227, ... as successive solutions.
The closing board abstracts the method: if solves the first three congruences, then all such solutions form ·LCM(,,). The next task is to find the first term in that progression satisfying the fourth congruence, denoted a in the clip.
After some congruences are solved, every other compatible solution is obtained by adding multiples of the least common multiple of the moduli already combined. The video displays this as , +LCM(,,), ·LCM(,,), ... and then repeats the same idea after adding another modulus.
For coprime positive integers a and b, the least common multiple equals ab. This shortcut is used in the CRT workflow to determine the step size quickly, as in LCM(5,12)=60 and later LCM(4,5)=20.
When a and b share a divisor greater than 1, their product is usually too large to be the least common multiple. The example 4 and 6 shows this clearly: , but LCM(4,6)=12. Using 24 as the CRT step can skip valid solutions such as 47.
The video demonstrates both a direct search and a formula-based method. Listing multiples of 4 gives 4, 8, 12, ... and the first multiple also divisible by 6 is 12. Equivalently, using the GCD formula gives LCM(4,6)=/gcd(4,6)=.
A system of simultaneous congruences may be written in any order without changing its solution set. The speaker exploits this by moving x ≡ 1 (mod 5) next to x ≡ 1 (mod 4), making the equal-remainder pattern visible at a glance.
If two congruences have the same remainder r, then satisfies both. The full combined solution set is then r plus multiples of the LCM of the two moduli. In the example, x ≡ 1 (mod 4) and x ≡ 1 (mod 5) immediately yield the progression 1, 21, 41, ... because LCM(4,5)=20.
Once a partial CRT solution set is known, the next congruence is handled by testing terms of the progression. From 1, 21, 41, ... the first term divisible by 3 is 21, so 21 becomes the first common solution of the congruences modulo 4, 5, and 3. The clip stops before the modulo-7 step is completed.
A strategy to solve systems of linear congruences by combining them one by one. At each stage, maintain an arithmetic progression of candidates. When adding a new congruence , update the step size to and find the first term in the current progression that satisfies the new condition.
If two integers and share no common factors other than 1 (i.e., ), their least common multiple is simply their product: . This simplifies calculating step sizes in the CRT method.
To find a term in an arithmetic progression that satisfies without computing large numbers, analyze the remainders modulo . Start with and repeatedly add (modulo ) until you hit . The number of steps tells you which term in the original progression is the solution.
Once a particular solution is found for a system of congruences with moduli , all solutions are given by , where and is an integer. In the video example, .
When solving by iterating where , the sequence of remainders cycles through all possible residues exactly once before repeating. This guarantees that a solution, if it exists, is found within steps.
Due to the cyclic nature of remainders, checking more than values for a specific modulus is redundant. If the target remainder is not found in the first iterations, the system has no solution (or an error was made), allowing for early termination.
The constructive method for the Chinese Remainder Theorem described has a time complexity proportional to the sum of the moduli involved in the sequential checks. For a system with moduli , the complexity is roughly .
Explore conditions, steps and evidence. Supplementary explanations are labeled separately from content shown in the video.
The unknown is written as x in the displayed congruences and in the generalized system.
The speaker says, "We're looking for the smallest value x".
x
An integer solution to a system of congruences; in the worked example it denotes the sought number satisfying all listed modular conditions.
Integers; in this clip the search is for the smallest nonnegative or positive representative shown by the sequence method.
The notation (mod 4), (mod 6), (mod 5) appears in the example, and (mod ), (mod ), (mod ), (mod ) appears in the generalization.
The speaker labels the number after mod as the modulus and says, "You can increase it by something divisible by all moduli so far".
,,,
Moduli of the congruences; in the concrete example they are 4, 6, and 5.
The generalized system is displayed as x ≡ (mod ), x ≡ (mod ), x ≡ (mod ), x ≡ (mod ).
In the worked example the numbers 3, 5, and 2 are treated as the remainders to be matched.
,,,
Remainders specified by each congruence.
The speaker says, "Least common multiple, LCM, of that is 12" and later, "By least common multiple of 4, 6, 5".
The screen shows (+12), then (+60), and in the general formula LCM(,,).
LCM
Least common multiple of the moduli already incorporated; used as the step size for the current solution sequence.
The generalized solution sequence begins with .
The speaker says, "Let's say that you found solution for first three congruences, ".
A particular solution to the first three congruences in the generalized setup.
A handwritten a appears at the bottom after the general sequence is introduced.
The speaker says, "After we find it, let's say it's a".
The clip ends before the full expression for the next solution family is completed.
a
The first value in the sequence ·LCM(,,) that also satisfies the fourth congruence.
The variable x appears in congruence statements such as x ≡ (mod ) and later in the concrete system x ≡ 1 (mod 4).
x
Unknown integer being solved for in a system of congruences.
Integers
The symbols , , , appear as remainders in the general CRT system.
Remainder associated with modulus in the general congruence x ≡ (mod ).
Integers
The symbols , , , appear as moduli in the general CRT system.
Modulus in the congruence x ≡ (mod ).
Positive integers
LCM is used in the solution sequence and in the formula LCM(a,b)= when a and b are coprime.
The speaker says 'least common multiple' and uses LCM to describe the step size between solutions.
LCM
Least common multiple of given integers; used as the period or step size for compatible solutions.
Positive integers
The formula LCM(a,b)= if a and b are coprime is shown, and later LCM = / GCD is written.
a, b
Two positive integers whose least common multiple is being computed.
Positive integers
The denominator GCD appears in the formula LCM = / GCD.
The speaker says 'greatest common divisor of a and b'.
GCD
Greatest common divisor of two integers.
Positive integers
The board shows x ≡ 3 (mod 4), x ≡ 5 (mod 6), x ≡ 2 (mod 5).
The speaker introduces the task as solving a system of congruences and names the three conditions.
Arrows label 3 as remainder and 4 as modulus.
Each line states that x leaves a specified remainder upon division by a specified modulus. In this clip the notation is used concretely rather than defined abstractly.
The example treats x as an integer.
The labels remainder and modulus identify the roles of the numbers in the notation.
The speaker says, "To satisfy the first requirement, we can take 3 or 7, 11, 15, and so on. You can keep increasing by 4, and that obviously doesn't change remainder modulo 4."
The screen writes 3, 7, 11, ... (+4).
Once one solution to x ≡ r (mod m) is known, adding the modulus m repeatedly produces further solutions because the remainder modulo m does not change.
Applied to a single congruence.
The sequence shown starts from the smallest displayed representative and increases by the modulus.
The speaker says, "Not the only one though. You can increase it by something divisible by all moduli so far, 4 and 6. Least common multiple, LCM, of that is 12, and if you add to something 12, you don't change remainders modulo 6 and 4, because 12 is divisible by 6 and 4."
The board changes from 11 to 11, 23, 35, ... (+12).
After two congruences are satisfied simultaneously, all simultaneous solutions form an arithmetic progression whose common difference is the least common multiple of the two moduli already used.
is one solution satisfying both earlier congruences.
The new step size must be divisible by every modulus already incorporated.
The speaker checks 11 mod 5, 23 mod 5, 35 mod 5, then says, "after 35 plus 12 that's 47, and 47 modulo 5 is 2 indeed. So it is the smallest solution for our system of three congruences."
The sequence 11, 23, 35, 47, ... (+12) is shown, and 47 is highlighted as the answer.
The method searches the current arithmetic progression for the first term that satisfies the remaining congruence. Here the first such term is 47.
The search is over the sequence of simultaneous solutions to the first two congruences.
The result is the smallest value found by this forward scan.
The speaker says, "Again, not the only one. We can increase it by what? By least common multiple of 4, 6, 5, all moduli values. It's easiest to compute it by taking the previous LCM and the new modulus value and just grabbing those two, computing their LCM. In this case, that's 60, smallest value divisible by 12 and 5. The smallest solution is 47, but then there's 107, 167, 227, and so on."
The board shows and then solutions: 47, 107, 167, ...
Once the smallest solution is found, all solutions are obtained by adding multiples of the least common multiple of all moduli in the system.
The displayed list uses nonnegative k.
60 = LCM(4,6,5) = LCM(12,5).
The board displays a four-congruence system and the sequence , +LCM(,,), *LCM(,,), *LCM(,,), ...
The speaker says, "This method still works if there are more congruences. Let's say that you found solution for first three congruences, , and you computed least common multiple of the first three moduli... then here is the sequence of solutions for first three congruences, and in this sequence we need to find the first value satisfying the fourth congruence. After we find it, let's say it's a, you can keep increasing it..."
The clip ends before the speaker completes the final sentence about how to continue after finding a.
The same search-and-update pattern generalizes: solve the first few congruences, list their solutions as an arithmetic progression with step equal to the LCM of the solved moduli, then scan that progression for the first term satisfying the next congruence.
is assumed to satisfy the first three congruences.
The next target is the first term in this sequence that also satisfies x ≡ (mod ).
The board shows , +LCM(,,), *LCM(,,), *LCM(,,), ... and then a, (+ LCM).
The speaker explains that instead of recomputing from scratch, one can use the already known LCM and then compute the LCM with modulus 4.
When solving a system of congruences incrementally, once a particular solution is found for some subset of congruences, all other compatible solutions form an arithmetic progression whose step is the least common multiple of the moduli already combined. Adding another congruence means searching within this progression and then updating the step to the LCM including the new modulus.
A particular solution has already been found for the earlier congruences.
The listed moduli are the ones already combined.
The next candidate solutions are obtained by adding multiples of their LCM.
The board states LCM(a, b) = if a and b are coprime.
The speaker says that if moduli are coprime, their LCM is simply the product.
If two integers have no common divisor greater than 1, then their least common multiple equals their ordinary product. This fact is used repeatedly in the CRT method to turn a congruence combination into a simple step size.
a and b are positive integers.
a and b are coprime, i.e. gcd(a,b)=1.
The board writes LCM = / GCD.
The speaker says to alternatively use the formula LCM is product divided by the greatest common divisor of a and b.
For arbitrary positive integers, the least common multiple can be computed from the product divided by the greatest common divisor. This is the fallback when the coprime shortcut does not apply.
a and b are positive integers.
No coprimality assumption is needed.
The speaker says he can reorder congruences to make computations easier.
The displayed system changes order so that x ≡ 1 (mod 5) is moved next to x ≡ 1 (mod 4).
In a system of simultaneous congruences, the equations may be rearranged without changing the solution set. The video uses this to place congruences with equal remainders adjacent to each other, making the first combined solution obvious.
The system is a set of simultaneous congruences in the same unknown x.
Reordering does not change the solution set.
The speaker says that when he sees equal remainders, it is good to put them at the top because he immediately sees the solution for them.
From x ≡ 1 (mod 4) and x ≡ 1 (mod 5), the board writes .
If two congruences have the same remainder, that remainder itself is a solution to both. The full solution set for those two congruences is then that remainder plus multiples of the LCM of their moduli.
The two congruences share the same remainder r.
The moduli m and n are positive integers.
Speaker describes a step-by-step process of combining congruences using LCMs and remainder sequences.
Visual layout shows progressive filtering of solution sets: first two congruences yield (+20), then adding third yields (+60), then fourth yields (+420).
To solve a system of linear congruences with pairwise coprime moduli, one can iteratively combine conditions. Start by finding the sequence of numbers satisfying the first few congruences, determined by the LCM of their moduli. Then, to add a new congruence, examine the remainders of the current sequence modulo the new modulus. Find the position in this remainder cycle that matches the target residue. The solution is the corresponding term in the sequence. The new step size becomes the LCM of the old step size and the new modulus.
Moduli are pairwise coprime (or at least the combined LCM logic applies).
The system has a solution (guaranteed if moduli are pairwise coprime).
The speaker says, "You can keep increasing by 4, and that obviously doesn't change remainder modulo 4."
The sequence 3, 7, 11, ... (+4) is written under x ≡ 3 (mod 4).
If a number satisfies a congruence modulo m, then adding m to it gives another number with the same remainder modulo m.
The starting number satisfies the given congruence.
The added quantity is exactly the modulus m.
For the worked example, repeatedly adding 4 to any listed solution keeps the remainder modulo 4 equal to 3.
The speaker says, "You can increase it by something divisible by all moduli so far, 4 and 6. Least common multiple, LCM, of that is 12, and if you add to something 12, you don't change remainders modulo 6 and 4, because 12 is divisible by 6 and 4."
The board updates the solution family to 11, 23, 35, ... (+12).
If a number satisfies several congruences, then adding the least common multiple of their moduli produces another number satisfying the same congruences.
The starting number satisfies all congruences whose moduli are included in the LCM.
The added quantity is divisible by each of those moduli.
In the example, adding 12 = LCM(4,6) to 11 preserves both the modulo 4 and modulo 6 remainders.
The speaker says, "This method still works if there are more congruences."
A four-congruence system is displayed together with the sequence based on LCM(,,).
The clip does not prove existence or uniqueness conditions for the generalized method; it only states that the same procedure continues.
The same sequential search method used for three congruences can be applied when there are more congruences by treating the solutions of the first group as a new arithmetic progression and scanning it for the next condition.
A solution to the first group of congruences has already been found.
The step size is the LCM of the moduli in that first group.
Stated for a system with a fourth congruence after the first three.
The board explicitly conditions LCM(a,b)= on 'if a and b are coprime'.
The speaker contrasts 5 and 12 with 4 and 6, saying the product rule does not work if there is some common divisor.
For positive integers a and b, LCM(a,b)=ab holds when a and b are coprime; if they have a common divisor greater than 1, the product is generally too large.
a and b are positive integers.
For all positive integers a and b, if gcd(a,b)=1 then LCM(a,b)=ab.
The board writes 4,6 -> 12 while the audio mentions their product is 24.
The speaker says for 4 and 6 their product is 24 and yet there is a smaller multiple, 12.
The integers 4 and 6 are not coprime, and although , their least common multiple is 12.
Consider the specific integers 4 and 6.
Existential counterexample to using the product as LCM without coprimality.
The speaker says if you use product instead of LCM you would miss some values and maybe also the solution.
The board shows the incorrect sequence 11, 35, 59, ... and the audio says 47 is missed.
The exact earlier congruences producing 11 and 47 are not fully restated inside this clip, but the numbers 11, 35, 59, ... and 47 are clearly discussed.
If one advances through candidate solutions by the product of non-coprime moduli rather than by their LCM, the resulting arithmetic progression can skip valid solutions; in the example, starting from 11 and stepping by 24 gives 11, 35, 59, ... and misses 47.
A previous solution is 11.
The step used incorrectly is 24 instead of the correct LCM 12.
There exists a case where using the product step omits a valid solution.
The speaker says the easiest way to compute LCM for two not coprime values is to write down multiples of one value and find the first divisible by the other.
The board lists 4, 8, 12, ... and marks 12 as the first multiple divisible by 6.
To compute LCM(a,b), list multiples of one integer and choose the first one divisible by the other integer. For 4 and 6, the multiples 4, 8, 12, ... show that 12 is the least common multiple.
a and b are positive integers.
For the example pair 4 and 6, the procedure yields 12.
The speaker says he can reorder congruences to make all the computations easier.
The system is visually reordered without any claim that the solution set changes.
The order in which simultaneous congruences are written does not affect their common solutions.
The congruences are all required to hold simultaneously for the same unknown x.
For any finite system of simultaneous congruences, permutation of the equations leaves the solution set unchanged.
The speaker says when he sees equal remainders he immediately sees the solution for them.
From x ≡ 1 (mod 4) and x ≡ 1 (mod 5), the board writes .
If x ≡ r (mod m) and x ≡ r (mod n), then satisfies both congruences, and the combined solution set is r plus multiples of LCM(m,n).
The two congruences have the same remainder r.
For all integers r and positive integers m,n, common solutions of x≡r (mod m) and x≡r (mod n) are exactly ·LCM(m,n).
The entire video demonstrates finding a solution, implying existence for this specific system.
A valid solution 381 is found and verified visually against the constraints.
The general theorem statement (CRT) is not explicitly quoted, but the method relies on its truth for the given coprime moduli 3, 4, 5, 7.
For the system of congruences , , , , a solution exists because the moduli 3, 4, 5, 7 are pairwise coprime.
Moduli 3, 4, 5, 7 are pairwise coprime.
There exists an integer x satisfying all four congruences simultaneously.
Speaker states 'if you want to find all the solutions, the new LCM is...' and calculates 420.
The notation '(+420)' is appended to the solution 381.
If is a solution to the system, then is also a solution for any integer . In this case, the period is 420.
is a particular solution.
Moduli are 3, 4, 5, 7.
For all integers k.
"Actually if you try to go for more than seven steps and you didn't find it already the solution, then either you made a mistake or there is no solution to this system of congruences."
If a solution to within an arithmetic progression does not appear in the first terms, then no solution exists for that specific congruence within the progression (assuming coprimality).
The step size of the progression is coprime to the modulus .
The search checks consecutive terms of the progression.
For all moduli m and step sizes coprime to m.
The speaker narrates the full solve: start from 3, 7, 11, ...; test against mod 6; get 11; extend by 12; test against mod 5; get 47; then extend by 60.
The board successively shows 3, 7, 11, ... (+4); 11, 23, 35, ... (+12); ; solutions: 47, 107, 167, ...
Start with numbers satisfying the first congruence x ≡ 3 (mod 4).
Adding the modulus 4 preserves the remainder modulo 4.
Test the sequence against the second congruence x ≡ 5 (mod 6).
Direct substitution into the second condition.
Once 11 satisfies the first two congruences, generate all simultaneous solutions by adding 12.
12 = LCM(4,6), and adding a common multiple of the current moduli preserves both remainders.
Search the new sequence for the first term satisfying x ≡ 2 (mod 5).
Direct checking of each candidate against the third congruence.
After finding 47 as the smallest solution to all three congruences, describe the full family of solutions.
60 = LCM(4,6,5) = LCM(12,5), so adding 60 preserves all three remainders.
The smallest solution shown for the system is 47, and the displayed solution family is 47, 107, 167, 227, ... .
The speaker explains the next stage for a four-congruence system but the sentence is cut off before completion.
The board shows , +LCM(,,), *LCM(,,), *LCM(,,), ... and then a handwritten a.
The final update rule after finding a is not fully spoken or written within this clip.
Consider a larger system with four congruences.
The speaker explicitly says the method still works if there are more congruences.
List all solutions to the first three congruences as an arithmetic progression.
By the same LCM-preservation principle used in the worked example.
Choose the first term in that progression that also satisfies the fourth congruence.
The speaker says, "in this sequence we need to find the first value satisfying the fourth congruence. After we find it, let's say it's a".
The clip establishes the next search stage for a fourth congruence, but stops before writing the full final solution family after a.
The speaker explains writing down multiples of one value and finding the first divisible by the other.
The board shows 4, 8, 12, ... and identifies 12.
List the positive multiples of 4.
This is the procedure stated in the video for finding a common multiple.
Check which listed multiple is also a multiple of 6.
The first common multiple in the list is the least common multiple.
Conclude that the least common multiple is 12.
By definition of LCM as the smallest positive common multiple.
The least common multiple of 4 and 6 is 12.
The board writes LCM = / GCD.
The speaker says the common divisor of 4 and 6 is 2, so LCM is 24 divided by 2.
Start from the general formula shown on the board.
This is the alternative method introduced in the video.
Identify the greatest common divisor of 4 and 6.
Stated directly by the speaker.
Substitute and simplify.
Arithmetic evaluation of the displayed formula.
Using the GCD formula also gives LCM(4,6)=12.
The reordered system begins with x ≡ 1 (mod 4) and x ≡ 1 (mod 5).
The speaker says works for the first two and then it can be increased by LCM of 4 and 5, which is 20.
The board writes and then 1, 21, ...
Take the two congruences with equal remainders after reordering.
These are the first two lines shown in the reordered system.
Observe that 1 satisfies both congruences.
Because 1 leaves remainder 1 upon division by both 4 and 5.
Compute the step size for the combined solution set.
4 and 5 are coprime, so the product rule for LCM applies.
Write the arithmetic progression of all solutions to the first two congruences.
Add successive multiples of 20 to the particular solution 1.
The common solutions of x≡1 (mod 4) and x≡1 (mod 5) are 1, 21, 41, ... , i.e. .
The speaker says to find the first value in the sequence satisfying divisibility by 3; 1 doesn't work, 21 does work.
The board underlines 21 in the sequence 1, 21, ... and writes 21 below the line x ≡ 0 (mod 3).
The clip ends before the next LCM update after incorporating modulus 3 is written out.
Start from the solution progression for the first two congruences.
This progression was derived immediately before this step.
Test the first candidate against x≡0 (mod 3).
1 is not divisible by 3, so it fails the third congruence.
Test the next candidate.
21 is divisible by 3, so it satisfies the third congruence.
Select 21 as the first common solution of the first three congruences.
It lies in the prior progression and meets the new modulus condition.
Within the displayed clip, 21 is identified as the first solution satisfying x≡1 (mod 4), x≡1 (mod 5), and x≡0 (mod 3).
Shows 'x ≡ 1 (mod 4)', 'x ≡ 1 (mod 5)' leading to '1, 21, ... (+20)'.
Start with the first two conditions.
Given problem statement.
Calculate the step size for numbers satisfying both.
LCM of coprime moduli is their product.
Generate the sequence starting from the smallest positive solution 1.
Definition of arithmetic progression with difference 20.
The candidates after two steps are for integer .
Adds 'x ≡ 0 (mod 3)' and updates sequence to '21, 81, ... (+60)'.
Speaker mentions LCM of 20 and 3 is 60 because they are coprime.
Update the step size to include the modulus 3 condition.
20 and 3 are coprime, so LCM is product.
Check which term in the previous sequence satisfies the new condition.
Direct calculation: 21 is divisible by 3.
New sequence starts at 21 with step 60.
Arithmetic progression definition.
The candidates after three steps are for integer .
Writes out '' under the sequence 21, 81...
Speaker explains '21 modulo 7 is 0' and '60 modulo 7 is 4', then iterates adding 4.
Determine the starting remainder of the sequence modulo 7.
Direct calculation.
Determine the increment of remainders modulo 7.
Direct calculation ().
Iteratively add 4 modulo 7 until the target remainder 3 is reached.
Applying the remainder sequence trick.
Count the number of steps taken to reach remainder 3.
It took 6 additions of 4 to go from 0 to 3 (mod 7).
The 6th term in the sequence (starting count from ) is the solution.
Writes ''.
Speaker says 'This is 21 plus 6 times 60... 381. That's the solution.'
Substitute into the sequence formula derived in step 2.
Result from derivation der-step3-remainder-search.
Perform multiplication.
Arithmetic.
Perform addition.
Arithmetic.
381 is a solution to the system.
Writes '(+420)' and '801'.
Speaker calculates LCM(60,7) = 420 and adds it to 381.
Calculate the new period for the full system.
60 and 7 are coprime, so LCM is product.
State the general form of all solutions.
Property of linear congruence systems.
Find the next positive solution.
Arithmetic.
All solutions are of the form for integer .
"The next element after three would be three plus four... seven modulo seven is zero. Then four, one and so on."
Sequence 0, 4, 1, 5, 2, 6, 3 written below the line '21, 81, ... (+60)'.
Start with the current solution 21.
Direct calculation.
Add step size 60. , so remainder increases by 4.
Modular addition property.
Continue adding 4 modulo 7 to generate the sequence.
Iterative modular arithmetic.
The target remainder 3 is found at the 6th index (0-indexed).
Matching target condition.
The sequence of remainders cycles through all residues modulo 7 because gcd(60, 7) = 1.
The entire worked example is written on screen from the initial system to the final solution list.
The speaker solves it verbally in real time and announces 47 as the smallest solution.
Find the smallest value x satisfying the three displayed congruences.
x ≡ 3 (mod 4)
x ≡ 5 (mod 6)
x ≡ 2 (mod 5)
Find the smallest solution and then describe the full solution family.
Begin with numbers congruent to 3 modulo 4.
These are generated by repeatedly adding the modulus 4.
Select 11 as the first number in that list that is congruent to 5 modulo 6.
The speaker checks 3, then 7, then 11 against the second congruence.
Generate all numbers satisfying the first two congruences by adding 12.
12 = LCM(4,6), so adding 12 preserves both remainders.
Pick 47 as the first number in that sequence congruent to 2 modulo 5.
The speaker tests 11, 23, 35, and then 47 against the third congruence.
Write the full family of solutions by adding 60 repeatedly.
60 = LCM(4,6,5) = LCM(12,5).
The smallest solution shown is 47, and the displayed solution family is 47, 107, 167, 227, ... .
The speaker verifies by direct modular checks: 47 modulo 5 is 2, and the earlier steps checked the modulo 4 and modulo 6 conditions.
The board writes LCM(5,12)=60.
The speaker says like for 5 and 12 it's just 60.
Compute LCM(5,12).
The integers are 5 and 12.
5 and 12 are coprime.
Find their least common multiple.
Recognize that 5 and 12 share no common divisor greater than 1.
Stated implicitly by the coprime condition in the example.
Use the product rule for coprime integers.
If two numbers are coprime, their LCM equals their product.
60
60 is divisible by both 5 and 12, and no smaller positive common multiple exists because the numbers are coprime.
The board writes 4,6 -> 12 and later shows and 11, 35, 59, ...
The speaker says for 4 and 6 their product is 24 and yet there is a smaller multiple, 12, and that using product instead of LCM misses 47.
The full original congruence pair that produced the solution 11 is not restated in this clip, but the numerical illustration 11, 35, 59, ... and the missed value 47 are explicit.
Compare LCM(4,6) with the product and illustrate what goes wrong if one steps by 24 instead of 12.
The integers are 4 and 6.
Their product is 24.
A previous solution is 11.
The correct step should be LCM(4,6)=12.
Show that using the product as the step can omit valid solutions.
Compute the product of the two moduli.
Direct arithmetic.
Identify the true least common multiple.
Shown on the board and explained verbally.
Generate the incorrect progression by repeatedly adding 24.
This is the sequence written on the board for the mistaken method.
Note that 47, a valid solution for the earlier congruences, does not appear in the incorrect progression.
Stated by the speaker.
The correct LCM is 12; using 24 as the step gives 11, 35, 59, ... and misses 47.
Adding 12 instead of 24 would include intermediate values such as 23 and 35 and eventually 47, so the smaller LCM step is necessary to avoid skipping solutions.
The board displays x ≡ 1 (mod 4), x ≡ 0 (mod 3), x ≡ 1 (mod 5), x ≡ 3 (mod 7), then reorders to put x ≡ 1 (mod 5) second.
The speaker solves the first two congruences to get 1, 21, 41, ... and then selects 21 as the first value divisible by 3.
The clip ends before the fourth congruence modulo 7 is processed, so the final full CRT solution is not reached within this segment.
Solve the reordered system beginning with x ≡ 1 (mod 4), x ≡ 1 (mod 5), x ≡ 0 (mod 3).
x ≡ 1 (mod 4)
x ≡ 1 (mod 5)
x ≡ 0 (mod 3)
The system is reordered to place the two congruences with remainder 1 together.
Find the first common solution after incorporating the third congruence.
Start with the two equal-remainder congruences.
Reordering is allowed and makes the first step immediate.
Take 1 as a particular solution of the first two congruences.
1 leaves remainder 1 modulo both 4 and 5.
Compute the combined step size.
4 and 5 are coprime, so their LCM is their product.
List the arithmetic progression of solutions to the first two congruences.
All solutions are 1 plus multiples of 20.
Search the progression for the first term divisible by 3.
1 is not divisible by 3, but 21 is.
Select 21 as the first solution satisfying the first three congruences.
It belongs to the prior progression and meets the modulo-3 condition.
21 is the first displayed common solution of x≡1 (mod 4), x≡1 (mod 5), and x≡0 (mod 3).
21≡1 (mod 4), 21≡1 (mod 5), and 21≡0 (mod 3), so it satisfies the three congruences processed in this clip.
The entire video is dedicated to solving this specific system.
Find an integer such that:
Four linear congruences with moduli 4, 5, 3, 7.
Moduli are pairwise coprime.
Find the smallest positive integer solution and describe the set of all solutions.
Identify sequence
LCM(4,5)=20 and 1 satisfies both.
Identify sequence
LCM(20,3)=60 and 21 is the first term divisible by 3.
Find that the 6th step (index 6) yields remainder 3.
, . Adding 4 six times modulo 7 gives 3.
Calculate the specific solution.
Substituting index 6 into the sequence formula.
Determine the spacing of all solutions.
LCM of current step and new modulus.
Smallest positive solution: 381. General solution: .
Check 381: (ok), (ok), (ok), (ok).
Full board work showing the step-by-step construction.
Find integer x satisfying the system of four congruences.
x ≡ 1 (mod 4)
x ≡ 1 (mod 5)
x ≡ 0 (mod 3)
x ≡ 3 (mod 7)
Find the smallest positive integer x.
Combine mod 4 and mod 5. Since x≡1 for both, x≡1 mod 20.
LCM of 4 and 5 is 20.
Check 1, 21... against mod 3. 21 is div by 3. New step size is LCM(20,3)=60.
LCM of 20 and 3 is 60.
Check 21, 81... against mod 7. Remainders are 0, 4, 1, 5, 2, 6, 3. Target 3 is at index 6.
Iterative search bounded by modulus 7.
381
381 % ; 381 % ; 381 % ; 381 % .
Blue arrows point to 3 and 4 in the first congruence, labeled remainder and modulus.
The three congruences
Blue arrows
The words remainder and modulus
The labels identify which number is the remainder and which is the modulus.
The congruences themselves do not change during this labeling.
The visual annotation introduces the terminology needed to read the system.
The board progressively writes 3, 7, 11, ... (+4), then 11, 23, 35, ... (+12), then , then solutions: 47, 107, 167, ...
Colored arrows and dots mark which congruence is currently being used.
Arithmetic sequences
Colored arrows
Underlined candidate values
The first sequence is built from the modulo 4 condition.
The second sequence is built after matching the modulo 6 condition.
The third stage highlights 47 after matching the modulo 5 condition.
The final line lists the full solution family.
Each displayed sequence is an arithmetic progression.
The step size changes only when a new group of congruences has been incorporated.
The visual progression encodes the iterative CRT-style search: restrict to one congruence, then intersect with the next by scanning the current progression.
The screen switches to a four-line symbolic system and a long sequence formula with LCM(,,).
White circles and underlines emphasize , , and the sequence terms.
The handwritten a appears near the end, but the continuation after a is not completed onscreen.
The system x ≡ (mod )
The sequence ·LCM(,,)
Handwritten a
The concrete numbers are replaced by symbolic moduli and remainders.
The previously used step 12 is generalized to LCM(,,).
A new symbol a is introduced for the first term satisfying the fourth congruence.
The structure remains an arithmetic progression of simultaneous solutions.
The method still searches within that progression for the next congruence.
The board abstracts the worked example into a reusable pattern for larger systems.
A general four-congruence system is shown at upper left, with a blue arrow pointing down to a solution sequence involving and LCM(,,).
Yellow highlighting moves among the moduli , , , and while the lower line a (+ LCM) is written.
System of four congruences x ≡ (mod )
Blue arrow
Sequence , +LCM(,,), ...
Handwritten line a (+ LCM)
Yellow highlights on moduli
Yellow emphasis shifts from grouped moduli to individual moduli.
The lower handwritten expression is completed as a (+ LCM).
The upper system remains a simultaneous congruence problem in x.
The lower sequence represents candidate solutions generated by adding a common period.
The visual layout connects a previously solved subsystem to a new solution progression after incorporating another modulus.
The board clears to a new section headed by LCM(a, b) = if a and b are coprime.
Examples are added sequentially: LCM(5,12)=60, then 4,6 -> 12, then the incorrect progression and 11, 35, 59, ..., then the formula LCM = / GCD.
Formula LCM(a,b)= for coprime a,b
Example LCM(5,12)=60
Example 4,6 -> 12
Incorrect progression 11, 35, 59, ...
Formula LCM = / GCD
The board moves from the coprime product rule to a non-coprime counterexample.
A wrong arithmetic progression is written and then contrasted with the correct LCM idea.
The general GCD formula is added at the bottom right.
All displayed content concerns computation of least common multiples.
The examples are used to justify when the product rule is valid and when it is not.
The visual sequence teaches that coprime moduli allow a product shortcut, while non-coprime moduli require the true LCM or the GCD formula.
Red diagonal strokes cross out the incorrect progression 11, 35, 59, ...
Sequence 11, 35, 59, ...
Red crossing-out strokes
The incorrect sequence is visually invalidated.
The numbers themselves remain visible under the red marks.
The red cross indicates that stepping by 24 rather than by the LCM 12 is not an acceptable method.
A new four-line congruence system appears, then the third line x ≡ 1 (mod 5) is moved upward next to x ≡ 1 (mod 4).
The solution line is written, expanded to 1, 21, ..., and then 21 is underlined and copied below the modulo-3 congruence.
The clip ends before the modulo-7 congruence is processed.
Original system x ≡ 1 (mod 4), x ≡ 0 (mod 3), x ≡ 1 (mod 5), x ≡ 3 (mod 7)
Reordered system with x ≡ 1 (mod 5) moved up
Line
Sequence 1, 21, ...
Underlined 21
Copied 21 below x ≡ 0 (mod 3)
The congruence order changes to group equal remainders.
A particular solution 1 is extended by step 20.
The candidate 21 is selected as the first value divisible by 3.
The unknown remains x throughout.
The first two congruences continue to define the same solution progression .
The animation demonstrates the practical CRT workflow: reorder for convenience, combine easy congruences, then scan the resulting arithmetic progression for compatibility with the next modulus.
Text lines appear sequentially: first the initial congruences, then the derived sequences with arrows indicating progression, then the remainder calculation row, and finally the solution equation.
Congruence equations
Arithmetic sequences
Remainder sequence
Final calculation
Lines of text are added from top to bottom.
Arrows connect related concepts (e.g., congruence to sequence).
Colors distinguish different stages (blue for first step, yellow/orange for second, white for remainder search).
The original problem statement remains visible at the top throughout.
The logical flow is strictly sequential.
The visual layout mirrors the iterative algorithm: reduce the problem step-by-step, tracking the current candidate set and its properties.
The number '3' in the remainder sequence '0 4 1 5 2 6 3' is highlighted/circled or emphasized when found.
Exact highlighting style (circle vs underline) might vary slightly in perception, but emphasis is clear.
Remainder sequence digits
Attention shifts to the digit '3' at the end of the sequence.
The sequence itself does not change, only the focus.
Marks the successful termination of the search loop in the remainder trick.
Green curved arrow drawn from the final '0' in the remainder sequence back to the initial '0'.
Remainder sequence 0, 4, 1, 5, 2, 6, 3, 0
Green arrow
Arrow connects end of sequence to start.
The sequence values themselves do not change, only the annotation.
Demonstrates that the remainders repeat periodically, justifying why the search stops after checking values.
Text '' appears on the right side of the board.
Big-O notation formula
Formula appears as speaker discusses programmer perspective.
Summarizes the computational cost of the method shown.
After identifying 11, the speaker immediately says, "Not the only one though."
After identifying 47, the speaker again says, "Again, not the only one."
Once a number such as 11 or 47 satisfies the current congruences, it may seem to be the only solution.
The video explicitly states that these are only the smallest values found so far; all further solutions are obtained by adding the appropriate LCM.
The speaker specifies that one may increase by "something divisible by all moduli so far" and computes LCM(4,6)=12.
One might think that after finding a simultaneous solution, any larger number still satisfies the same system.
Only increments divisible by all moduli already incorporated preserve all current remainders; in the example that minimal positive increment is 12, then later 60.
The speaker says it doesn't work if there is some common divisor and warns that using product instead of LCM would miss some values and maybe also the solution.
The board contrasts 4,6 -> 12 with the incorrect progression 11, 35, 59, ...
One may think that for any two moduli the step between compatible solutions is their product.
The product equals the LCM only when the moduli are coprime. For non-coprime moduli such as 4 and 6, the correct step is 12, not 24; using 24 can skip valid solutions such as 47.
The speaker explicitly says he can reorder congruences to make computations easier.
Learners may assume the congruences must be processed in the order they are first displayed.
Simultaneous congruences may be reordered freely. The video uses this to place equal-remainder congruences together and simplify the first step.
Speaker warns: 'Just remember, if they are not coprime, it's not simply a product.'
Assuming LCM(a,b) is always .
LCM(a,b) = only holds if a and b are coprime. If they share factors, the LCM is smaller than the product.
"You will not go forever. Actually if you try to go for more than seven steps... either you made a mistake or there is no solution..."
One might think that if a solution isn't found quickly, one must continue searching indefinitely or that a solution might exist far beyond the modulus range.
Due to the cyclic nature of remainders modulo , if a valid remainder hasn't appeared within steps, it never will. The search space is strictly bounded by the modulus.
The speaker first adds 4 to stay within one congruence, then adds 12 after combining two congruences.
The board moves from (+4) to (+12).
The single-congruence rule 'add the modulus' is generalized to multiple congruences as 'add the LCM of the moduli already satisfied'.
The speaker finds 47 and then says the solution can be increased by LCM(4,6,5)=60.
The board shows and the list 47, 107, 167, ...
The LCM-update rule is applied once more, now to all three moduli, to produce the complete solution family.
The speaker says, "This method still works if there are more congruences."
The concrete numbers are replaced by , , , and LCM(,,).
The worked three-congruence procedure is abstracted into a symbolic iterative pattern for a larger system.
The speaker uses the coprime product rule when combining moduli 4 and 5 to get step 20.
LCM(4,5)=20 is justified by coprimality in the worked example.
The CRT incremental method relies on computing the LCM of the moduli already combined; when those moduli are coprime, the product rule supplies that LCM immediately.
The board introduces LCM = / GCD right after discussing the non-coprime pair 4 and 6.
The GCD formula works for arbitrary positive integers and therefore extends the coprime product rule to the non-coprime case.
The speaker says reordering helps because equal remainders can then be seen together.
The system is reordered so that the two congruences with remainder 1 become adjacent.
Reordering the system is what makes the equal-remainder shortcut visually and computationally immediate in the worked example.
The example writes , then 1, 21, ..., and searches that progression for divisibility by 3.
The partial CRT example is a direct application of the incremental solution-sequence method.
Speaker repeatedly uses LCM to determine step sizes in the CRT method.
The constructive CRT method relies on calculating LCMs of moduli to find the periodicity of partial solution sets.
The example problem is solved using the described method.
The main example serves as a concrete demonstration of the abstract CRT solution method.
Speaker links the cycle observation directly to the limit of 7 steps.
The periodicity of the remainder sequence (ki-remainder-cycle) is the mathematical reason why the search is bounded by the modulus (claim-no-solution-condition).
"If you are a programmer... what's important for you is that you need m4 steps... So that's the complexity..."
The specific iterative method demonstrated (ki-crt-system) leads directly to the stated time complexity (claim-complexity-bound).
The speaker asks for the smallest value x and later identifies 47 as the smallest solution.
The final highlighted answer is 47.
The speaker explains that 12 is the LCM of 4 and 6 and that adding it preserves both remainders.
The sequence becomes 11, 23, 35, ... (+12).
The speaker says the next increment is the LCM of 4, 6, 5 and computes it as 60.
The board shows and solutions: 47, 107, 167, ...
The speaker states that the method still works with more congruences and introduces and a.
The generalized sequence with LCM(,,) is displayed.
The clip ends before the final continuation after a is fully written.
The speaker explains that using product instead of LCM misses values and gives the 47 example.
The board states LCM(a,b)= if a and b are coprime.
The board writes LCM = / GCD.
The speaker says he can reorder congruences to make computations easier.
The speaker says equal remainders let him immediately see the solution for them.
The speaker tests 1 and then 21 against divisibility by 3.
The speaker says the incorrect progression misses 47.
The earlier congruences producing 11 and 47 are not fully restated in this clip.
Video explains the process of combining congruences one by one.
Covered · Opening statement of the problem and visual labeling of remainder and modulus.
Covered · Construction of the first sequence and selection of 11 as the first match for the second congruence.
Covered · Explanation that the combined solution family advances by LCM(4,6)=12.
Covered · Scanning 11, 23, 35, 47 to satisfy the third congruence and identifying 47 as the smallest solution.
Covered · Computation of LCM(4,6,5)=60 and listing of the full solution family.
Covered · Symbolic generalization to four congruences; the clip ends while introducing the next step after finding a.
Covered · General CRT system and incremental solution sequence are shown and explained.
Covered · Coprime LCM rule and the non-coprime counterexample 4,6 are introduced.
Covered · The incorrect progression 11, 35, 59, ... is used to show missed solutions.
Covered · LCM(4,6) is computed by listing multiples.
Covered · The general formula LCM = ab / GCD is written and applied to 4 and 6.
Covered · The larger congruence system is reordered to group equal remainders.
Covered · The first two congruences are combined into the progression 1, 21, 41, ...
Covered · The sequence is searched for the first value divisible by 3, yielding 21 before the clip ends.
Covered · Initial setup and combining first two congruences (mod 4, mod 5).
Covered · Adding the third congruence (mod 3) and updating the sequence/step size.
Covered · Applying the remainder trick to satisfy the fourth congruence (mod 7).
Covered · Calculating the specific numerical solution 381.
Covered · Determining the general solution period and warning about non-coprime LCMs.
Covered · Introduction to the extra topic, pointing to the remainder sequence.
Covered · Detailed explanation of the remainder cycle and visual demonstration.
Covered · Logical consequence of the cycle: bounded search and no-solution detection.
Covered · Discussion of algorithmic complexity for programmers and closing remarks.
Reviewed English material v1: card "Iterative CRT Method" at 5:00 — A strategy to solve systems of linear congruences by combining them one by one. At each stage, maintain an arithmetic progression of candidates. When adding a new congruence , update the step size to and find the first term in the current progression that satisfies the new condition.
Reviewed English material v1: card "Complexity of Iterative CRT" at 8:16 — The constructive method for the Chinese Remainder Theorem described has a time complexity proportional to the sum of the moduli involved in the sequential checks. For a system with moduli , the complexity is roughly .
Because the step size and the modulus m are coprime, the sequence of remainders generated by adding the step size modulo m forms a complete cycle of length m. If the target remainder does not appear within the first m steps, it will never appear, meaning no solution exists for that specific congruence within the progression.
Conditions: The step size of the current arithmetic progression is coprime to the target modulus m.; The search is bounded by the modulus m.
The step size updates to the least common multiple (LCM) of the moduli already satisfied because adding the LCM to a current solution preserves the remainders for all those moduli. Any increment divisible by all the current moduli will not change the remainder modulo any of them, and the LCM is the smallest positive such increment.
Conditions: A number currently satisfies a set of congruences.; The new step size must preserve the remainders for all those congruences.
The time complexity is proportional to the sum of the moduli (excluding the first one), expressed as O( + ... + ). This is because each stage of the iterative search requires at most steps to find a solution or prove none exists for the i-th congruence.
Conditions: The moduli are pairwise coprime.; Naive iteration is used to find the multiplier for each step.
The least common multiple (LCM) of two positive integers is equal to their product if and only if the two integers are coprime, meaning their greatest common divisor (GCD) is 1.
Conditions: The two integers are positive.; The two integers are coprime (gcd(a,b) = 1).
If two congruences x ≡ r (mod m) and x ≡ r (mod n) share the same remainder r, then is an immediate particular solution. The full combined solution set is then r plus multiples of the LCM of the two moduli: * LCM(m, n).
Conditions: The two congruences have the identical remainder r.; The moduli m and n are positive integers.
The general formula for the least common multiple (LCM) of two positive integers a and b is their product divided by their greatest common divisor (GCD): LCM(a,b) = () / GCD(a,b).
Conditions: a and b are positive integers.
The method solves the congruences one by one by maintaining an arithmetic progression of candidate solutions. It starts with the sequence of numbers satisfying the first congruence, tests them against the second to find a common solution, and then updates the step size to the least common multiple (LCM) of the first two moduli.
Conditions: The unknown x is an integer.; The system consists of the congruences x ≡ 3 (mod 4), x ≡ 5 (mod 6), and x ≡ 2 (mod 5).
Instead of computing large terms in the arithmetic progression, the trick computes the sequence of remainders modulo the new target modulus. It starts with the current solution's remainder and repeatedly adds the step size's remainder modulo the target, stopping when the target remainder is reached.
Conditions: You have an arithmetic progression of candidates satisfying previous congruences.; You need to find the first term satisfying a new congruence x ≡ r (mod m).
Continue with related videos in the same subject.
YouTube5:09
YouTube4:58
YouTube5:00