# ETOOBUSY 🚀 minimal blogging for the impatient

# Generalized Chinese Remainder Theorem

**TL;DR**

A second take at the Chinese Remainder Theorem, after using the

strictversion in Advent of Code 2020 - Day 13.

That previous post introduced a small implementation of the gist of the Chinese Remainder Theorem, namely:

```
sub crt ($n1, $r1, $n2, $r2) {
my ($gcd, $x, $y) = egcd($n1, $n2);
die "not coprime! <$n1> <$n2>" if $gcd != 1;
my $N = $n1 * $n2;
my $r = ($r2 * $x * $n1 + $r1 * $y * $n2) % $N;
return [$N, $r];
}
```

That was good for that day’s puzzle - after all, the input I was given
(well, this was valid for everyone else too) indeed had only *coprime*
values for the bus numbers, so the `die`

line was actually not needed at all
(it’s there to make sure of that and leaving it does not harm anyway, acting
as a sort of reminder).

But *that’s not the whole story*.

And *I knew it*.

And *it came to haunt me just like the Ghost of Christmas Yet to Come*.

It’s indeed possible to apply the theorem, or better a slight generalization
of it, also to cases when the *coprimeness* (is this a word? 🧐) requirement
is failed, namely (adapting from Chinese Remainder Theorem):

If $r_1 \equiv r_2 \pmod{gcd(n_1, n_2)}$ then this system of equations has a unique solution modulo $\frac{n_1 \cdot n_2}{gcd(n_1, n_2)}$. Otherwise, it has no solutions.

Honestly, as it often happens, it both makes a lot of sense and it’s not
very scaring to implement at all. So I decided to adapt the implementation
with this generalization, and also to accept a generic number of pairs of
*modulus and remainder*, resulting in this:

```
sub chinese_remainder_theorem {
die "no inputs" unless scalar @_;
die "need an even number of inputs" if scalar(@_) % 2 == 1;
my ($N, $R) = splice @_, 0, 2;
while (@_) {
my ($n, $r) = splice @_, 0, 2;
my ($gcd, $x, $y) = egcd($N, $n);
if ($gcd != 1) {
die "cannot combine: {x ~ $R (mod $N)} with {$x ~ $r (mod $n)}"
unless ($R % $gcd) == ($r % $gcd);
$_ /= $gcd for ($N, $n);
}
my $P = $N * $n;
($N, $R) = ($P, ($r * $x * $N + $R * $y * $n) % $P);
}
return ($N, $R);
}
```

As there are a lot of multiplications, integers can explode very fast and
yield wrong results due to representation issues. For this reason, you might
want to use the *big integers* version instead:

```
sub chinese_remainder_theorem_bi {
require Math::BigInt;
return chinese_remainder_theorem(map { Math::BigInt->new($_) } @_);
}
```

It’s just a thin wrapper around the other function, making sure to feed it with Math::BigInt objects instead of plain Perl integers, so that nothing will be lost on the way.

Well, some *time* might be lost, probably. But it’s for the right cause of
correctness 😅.

Both functions ended up in cglib of course, because… why not? There might be a puzzle in the future that can use some copy-and-paste love 🙄