Keep Talking and Nobody Explodes Mod Chinese Remainder Theorem

On the Subject of Chinese Remainder Theorem

More like... Chinese Remainder TFCeorem!

  1. For each of the module’s 4-8 N % A = B equations (which there will be 4 to 8 of; press the green button while the top display is blank to cycle through them):
    1. Break A down into its prime factors p1q1, p2q2...
    2. For every prime factor with its power pq:
      • If you have already noted down an equation of form N % pr = ..., where r is greater than q, skip this prime factor.
      • Otherwise, note down the equation N % pq = (B % pq).
        • If you previously had a noted equation of form N % po = ..., where o is less than q, remove it from your notes.
  2. Introduce letter variables a, b, c... one for each of your noted equations excluding one (e.g. you should introduce variables a, b, c, d, and e if you have 6 noted 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 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.
1
Keep Talking and Nobody Explodes Mod Chinese Remainder Theorem

Example

The module’s equations are:
#1: N % 18 = 6
#2: N % 44 = 40
#3: N % 39 = 33
#4: N % 30 = 18

Equation #1: N % 18 = 6.
18 = 21 * 32.
I haven’t yet noted down an equation N % 22+ = ..., so I’ll note down the equation:
N % 21 = (6 % 21), and simplify it to get: N % 2 = 0.
I haven’t yet noted down an equation N % 33+ = ..., so I’ll note down the equation:
N % 32 = (6 % 32), and simplify it to get: N % 9 = 6.

Equation #2: N % 44 = 40.
44 = 22 * 111.
I haven’t yet noted down an equation N % 23+ = ..., so I’ll note down the equation:
N % 22 = (40 % 22), and simplify it to get: N % 4 = 0,
after which I’ll also remove the noted equation N % 2 = 0
(because 1 < 2 from 2 and 4, i.e. 21 and 22).
I haven’t yet noted down an equation N % 112+ = ..., so I’ll note down the equation:
N % 111 = (40 % 111), and simplify it to get: N % 11 = 7.

Equation #3: N % 39 = 33.
39 = 31 * 131.
I have already noted down an equation N % 32+ = ... (that is, N % 9 = 6), so I’ll skip 31.
I haven’t yet noted down an equation N % 132+ = ..., so I’ll note down the equation:
N % 131 = (33 % 131), and simplify it to get: N % 13 = 7.

Equation #4: N % 30 = 18.
30 = 21 * 31 * 51.
I have already noted down an equation N % 22+ = ... (that is, N % 4 = 0), so I’ll skip 21.
I have already noted down an equation N % 32+ = ... (that is, N % 9 = 6), so I’ll skip 31.
I haven’t yet noted down an equation N % 52+ = ..., so I’ll note down the equation:
N % 51 = (18 % 51), and simplify it to get: N % 5 = 3.

Afterwards, my noted equations are:
#1: N % 9 = 6
#2: N % 4 = 0
#3: N % 11 = 7
#4: N % 13 = 7
#5: N % 5 = 3

2
Keep Talking and Nobody Explodes Mod Chinese Remainder Theorem

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

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

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

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

Current N value - 168, doesn’t satisfy any noted equations: incrementing c (c = 1).
New N value - 348, satisfies equation #3 (348 % 11 = 7), setting c to 1 + 11*d
and removing equation #3 from notes.
Equation #4 is the last remaining equation..
New current letter variable is d.

Current N value - 348, doesn’t satisfy any noted equations: incrementing d (d = 1).
New N value - 2328, doesn’t satisfy any noted equations: incrementing d (d = 2).
New N value - 4308, doesn’t satisfy any noted equations: incrementing d (d = 3).
New N value - 6288, doesn’t satisfy any noted equations: incrementing d (d = 4).
...
At d = 9, the N value - 18168, satisfies the final equation #4
(18168 % 13 = 7), and therefore is a solution for the module.

Final variables and their values:
N = 6 + 9*a (18168),
a = 2 + 4*b (2018),
b = 4 + 5*c (504),
c = 1 + 11*d (100),
d = 9 (9).

3