Solutions to systems of Linear Congruences and AOC2020 Day 13

Modular Arithmetic

Modular arithmetic is like regular arithmetic, except you have numbers ‘looping around’ - so once they hit a certain point, they go back to 0.

24-hour clock arithmetic is modular arithmetic: once you get to 24, the numbers loop back to zero. We would say clock arithmetic occurs modulo 24.

In that sense, saying something happens at 28’o’clock is equivalent to saying is happens at (28 - 24) 4’o’clock. In this system, they are they same thing. Mathematically we would say that 28 and 4 are congruent modulo 24, or we would write 28==4 (mod 24). (Congruent in this context means ‘identical in form’)

These are all equivalent ways of describing this:

• a is congruent to b modulo m if m divides their difference.
• a==b (mod m) if a-b=km for some k.
• a==b (mod m) if a = km + b for some k.

For example, 348==236 (mod 7), since _348-236=112=16*7_.

38==14 (mod 12), since 38-14=24, which is a multiple of 12.

Notice that 38/12 and 14/12 have the same remainder of 2.

Congruence Classes

Going back to our clock example, notice that 28 isn’t the only number that is congruent to 4 (mod 24). So is 52. So is 76. So are all numbers that are 4 + 24k (even when k is negative).

We call this set of numbers `x==4 (mod 24) the congruence class 4-bar-mod-24.

More generally The set of all numbers x==a (mod m) is {… , a-2m , a-m, a , a+m, a+2m,…} congruence class of a modulo m.

  a-bar-mod-m = {x in Z | x==a (mod m)}

For example, the following are congruence classes modulo 10:

  0-bar-m10 = {..., -20, -10, 0, 10, 20, ...}
  1-bar-m10 = {..., -19, -9, 1, 11, 21, ...}
  5-bar-m10 = {..., -15, -5, 5, 15, 25, ...}
  9-bar-m10 = {..., -11, -1, 9, 19, 29, ...}

Linear Congruence

A modular congruence of the the form

ax==b (mod m)

It’s just an equation where the x is unknown and you have to find it, like linear equations over real numbers.

Like normal algebra, there may be 0, 1 or several solutions to this congruence.

There is a whole school of techniques for solving linear congruences, but we’re focusing only on one case here.

Systems of linear congruences

In normal algebra you often have to solve ‘simultaneous equations’ - that is you’re given multiple equations at the same time, with some common connection, and you have to solve them.

Systems of linear congruences are to linear congruences what simultaneous equations are to normal equations. In other words you’re given several of them at the same time and have to solve them. They’re given in the form:

  X = a1 (mod n1)
  X = a2 (mod n2)
  X = a3 (mod n3)
  X = a4 (mod n4)
  ...

And you have to solve for X. This is what we’re going to do here, and to do it we’ll need to know about Modular Multiplicative Inverses.

Modular Multiplicative Inverse

MMI is a special case of linear congruence.

It’s equivalent to the ‘inverse’ in real-number mathematics, where the inverse of x is x^-1: x * x^-1 = 1. We’re saying that y is the inverse of x where x * y = 1 (where _*_ is a binary operation)

In modular arithmetic we also say y is the inverse of x when x * y = 1, only here you have to plop the modulo on the end. The MMI of integer a is an x ST ax==1 (mod m).

You can think of this as

• the remainder of ax/m is 1.
• m evenly divides ax-1.

Take a=43, and m=5.

x=2 is a MMI of 43 mod 5, since _43*2-1 = 85_, which is divisible by 5.

x=3 is not an MMI of 43 mod 5, since _43*3-1 = 128_ is not divisible by 5.

A solution to ax==1 (mod m) exists only if and only if gcd(a,m)=1, i.e. they they are coprime

Take MMI(3, 10), 3x==1 (mod 10). Since gcd(3,10)=1, this will have solutions.

7 is one solution: _3*7 == 1 (mod 10), (21-1)/10=2_.

17 is another: _3*17 == 1 (mod 10), (51-1)/10=5_.

In fact, every number in the congruence group 7-bar mod 10: {…, -3, 7, 17, 27, …} will be a solution.

You can see this by noticing that every element of 7-bar mod 10 can be expressed as:

  7 + 10r

and

  3(7 + 10r) - 1 = 21 + 30r - 1 = 10(2+3r)

Computation of MMI using the extended Euclidean Algorithm

The Euclidean algorithm is just the common method for finding the gcd.

(defn gcd [a b]
  (if (zero? b) a
      (recur b (mod a b))))

The extended Euclidean computes, in addition to the gcd, the coefficients to Bezout’s identity, that is

ax + by = gcd(a,b)

The algorithm goes like this

(defn xgcd [a b]
  (if (= a 0) [b 0 1]
    (let [[g x y] (xgcd (mod b a) a)]
      [g (- y (* (Math/floorDiv b a) x)) x])))

Which returns a tuple of gcd, x, y.

The application for MMIs is that you know gcd(a,m)=1, and so finding x in the Bezout Identity, is equivalent to solving for the MMI. (y you can ignore, because whatever it is it gets multiplied by the modulo and so disappears).

So for the equation _3x==1 (mod 10)__, you are looking for a solution

  3x + 10y = 1

We can apply the xgcd(a,b), where a=3, b=10, which returns [1 -3 1]

The second argument, x, -3 is the solution to 3x==1 (mod 10). (as are all the numbers in the congruence group 7-bar mod 7, of the form 7+10r)

(Java has a built in .modInverse method, which you should probably use in practice)

Chinese Remainder Theorem and solving systems of linear congruences

• https://www.geeksforgeeks.org/chinese-remainder-theorem-set-1-introduction/
• https://www.geeksforgeeks.org/chinese-remainder-theorem-set-2-implementation/?ref=lbp
• https://en.wikipedia.org/wiki/Chinese_remainder_theorem

The Chinese Remainder Theorem (CRT) is a theory of systems of linear congruences. That is, for problems in the form

  X == a1 (mod n1)
  X == a2 (mod n2)
  ...
  X == ak (mod nk)

where the n’s are coprime - gcd(ni,nj)=1 for all n.

The CRT states that there is always a solution X to such a system.

Systems of linear congruences can be solved with MMIs using the formula:

  X = (∑ (ai * ppi * invi)) (mod prod)
  prod = Π ni
  ppi = prod / ni
  invi = MMI(ppi, ni)

With a very literal translation into Clojure:

(defn- linear-congruence-solve [pairs]
  (let [remainders (map first pairs)
        modulos (map second pairs)
        prod (apply * modulos)
        pp (map #(/ prod %) modulos)
        inv (map #(.modInverse (biginteger %1) (biginteger %2)) pp modulos)]
    (mod (apply + (map * remainders pp inv)) prod)))

Take

  X = 2 (mod 3)
  X = 3 (mod 4)
  X = 1 (mod 5)

Applying the formula we get X = 11

An application to Day 13 of Advent of Code

Link to problem (note: you need to have solved part 1!)

We are told there are a bunch of buses which complete a cycle of their routes every m minutes, starting from minute 0 when they all leave the terminal concurrently.

We are asked to find the earliest time X where bus1 passes through the terminal at X, bus2 at X+1, bus3 at X+3 etc. (there are some ‘gaps’, but they don’t complicate the problem much and we’ll ignore them)

This can be interpreted as a system of linear congruences. When you have multiple things going around in loops and you are asked to predict how they will interact waaay in the future, your mind should always go here.

Consider the case where you have bus1 on a 3 minute look, and bus2 on a 5 minute loop. The schedule would look something like this, with D being every time one of the buses passes the depot:

  0     D     D
  1     .     .
  2     .     .
  3     D     .
  4     .     .
  5     .     D
  6     D     .
  7     .     .
  8     .     .
  9     D     .
  10    .     D
  11    .     .
  12    D     .
  13    .     .
  14    .     .
  15    D     D
  16    .     .
  17    .     .
  18    D     .
  19    .     .
  20    .     D
  21    D     .
  22    .     .
  23    .     .
  24    D     .
  25    .     D
  26    .     .
  27    D     .
  28    .     .
  29    .     .
  30    D     D

The solutions we can see are 9 and 24.

This is a system of linear congruences: We are being asked to find X such that

  X == 0 (mod 3), (9 == 0 (mod 3))
  X == -1 (mod 5), (9 == -1 (mod 5))

Note 3 and 5 are pairwise coprime, so we can use the formula from above here.

"7,13,x,x,59,x,31,19"

"time     bus 7   bus 13  bus 59  bus 31  bus 19
1068773    .       .       .       .       .
1068774    D       .       .       .       .
1068775    .       .       .       .       .
1068776    .       .       .       .       .
1068777    .       .       .       .       .
1068778    .       .       .       .       .
1068779    .       .       .       .       .
1068780    .       .       .       .       .
1068781    D       .       .       .       .  <- 1068781 is the answer
1068782    .       D       .       .       .
1068783    .       .       .       .       .
1068784    .       .       .       .       .
1068785    .       .       D       .       .
1068786    .       .       .       .       .
1068787    .       .       .       D       .
1068788    D       .       .       .       D
1068789    .       .       .       .       .
1068790    .       .       .       .       .
1068791    .       .       .       .       .
1068792    .       .       .       .       .
1068793    .       .       .       .       .
1068794    .       .       .       .       .
1068795    D       D       .       .       .
1068796    .       .       .       .       .
1068797    .       .       .       .       ."

(linear-congruence-solve [[0 7] [-1 13] [-4 59] [-6 31] [-7 19]])
;; => 1068781N

"17,x,13,19"
(linear-congruence-solve [[0 17] [-2 13] [-3 19]])
;; => 3417N

"67,7,59,61"
(linear-congruence-solve [[0 67] [-1 7] [-2 59] [-3 61]])
;; => 754018N

"67,x,7,59,61"
(linear-congruence-solve [[0 67] [-2 7] [-3 59] [-4 61]])
;; => 779210N

"67,7,x,59,61"
(linear-congruence-solve [[0 67] [-1 7] [-3 59] [-4 61]])
;; => 1261476N

"1789,37,47,1889"
(linear-congruence-solve [[0 1789] [-1 37] [-2 47] [-3 1889]])
;; => 1202161486N