Keep Talking and Nobody Explodes Mod Chinese Remainder Theorem

On the Subject of Chinese Remainder Theorem

More like... Chinese Remainder TFCeorem!

  1. Note down all of the module’s equations N % A = B (which there will be 4 to 8 of), pressing the equation display to cycle through them.
  2. Introduce variables a through c-g, one for each equation excluding one (e.g. you should introduce variables a, b, c, d, and e if you have 6 equations), all initially equal to 0.
  3. Introduce a variable N, equal to B + A*a, where A and B are taken from any of the noted module’s equations. Remove the said equation from your notes.
  4. Start with the a variable being your current letter variable.
  5. If there is a noted equation that is met by the current value of N:
    1. If this is the last remaining noted equation, remove it from your notes, then input and submit N’s value into the module to solve it.
    2. Otherwise, set the current letter variable to be equal to v + A*n, where:
      • v is the value of the variable at this point.
      • A is taken from the aforementioned equation.
      • n is the letter variable that follows the current letter variable.
    3. Remove the said equation from your notes.
    4. Move on to the next letter variable (n) being your current letter variable, and check Step 5’s condition again.
  6. Otherwise, increment the value of the current letter variable, then check Step 5 again.

Example

The module’s equations are:
#1: N % 21 = 15
#2: N % 29 = 20
#3: N % 17 = 5
#4: N % 39 = 36
#5: N % 20 = 6

Introducing four variables for the five noted equations: a, b, c, and d.

Introducing N = 15 + 21*a, where A and B were taken from equation #1.
Removing equation #1 from notes - equations #2, #3, #4, and #5 are still left.

Page 1 of 2
Keep Talking and Nobody Explodes Mod Chinese Remainder Theorem

Current N value - 15, doesn’t satisfy any noted equations: incrementing a (a = 1).
New N value - 36, satisfies equation #4 (36 % 39 = 36): setting a to 1 + 39b and removing equation #4 from notes.
Equations #2, #3, and #5 are still left.
New current letter variable is b.

Current N value - 36, doesn’t satisfy any noted equations: incrementing b (b = 1).
New N value - 855, satisfies equation #3 (855 % 17 = 5): setting b to 1 + 17c and removing equation #3 from notes.
Equations #2 and #5 are still left.
New current letter variable is c.

Current N value - 855, doesn’t satisfy any noted equations: incrementing c (c = 1).
New N value - 14778, doesn’t satisfy any noted equations: incrementing c (c = 2).
New N value - 28701, satisfies equation #2 (28701 % 29 = 20): setting c to 2 + 29d and removing equation #2 from notes.
Equation #5 is the last remaining equation.
New current letter variable is d.

Current N value - 28701, doesn’t satisfy equation #5: incrementing d (d = 1).
New N value - 432468, doesn’t satisfy equation #5: incrementing d (d = 2).
New N value - 836235, doesn’t satisfy equation #5: incrementing d (d = 3).
...
At d = 15, the N value - 6085206, satisfies the final equation #5
(6085206 % 20 = 6), and therefore is a solution for the module.

Page 2 of 2