There we have it! We have x = − 2 x = -2 x = − 2 and y = 33 y = 33 y = 33 .
But what does this have to do with the "modular multiplicative inverse modulo m"?
Well... say we have the following congruence:
a ≡ b ( m o d m )
a \equiv b \pmod m
a ≡ b ( mod m )
Then if a a a and m m m are coprime, their GCD is 1.
Then, Bézout's identity, which is:
a x + m y = G C D ( a , m )
ax + my = GCD(a, m)
a x + m y = GC D ( a , m )
Becomes:
a x + m y = 1
ax + my = 1
a x + m y = 1
Which is very, very interesting. Because, if we're "modulo m", then we have:
a x + m y ≡ 1 ( m o d m )
ax + my \equiv 1 \pmod m
a x + m y ≡ 1 ( mod m )
But m m o d m = 0 {m \bmod m = 0} m mod m = 0 , so it all reduces down to:
a x + 0 ⋅ y ≡ 1 ( m o d m ) a x ≡ 1 ( m o d m )
\begin{aligned}
ax + 0 \cdot y &\equiv 1 \pmod m \
ax &\equiv 1 \pmod m \
\end{aligned}
a x + 0 ⋅ y a x ≡ 1 ( mod m ) ≡ 1 ( mod m )
So, for 7 {7} 7 and 5 {5} 5 , in 7 j ≡ 1 ( m o d 5 ) {7j \equiv 1 \pmod 5} 7 j ≡ 1 ( mod 5 ) , let's run through the whole thing again.
First, the Euclidean Algorithm:
7 = 1 ⋅ 5 + 2 5 = 2 ⋅ 2 + 1 2 = 2 ⋅ 1 + 0
\begin{aligned}
7 &= 1 \cdot 5 + 2 \
5 &= 2 \cdot 2 + 1 \
2 &= 2 \cdot 1 + 0 \
\end{aligned}
7 5 2 = 1 ⋅ 5 + 2 = 2 ⋅ 2 + 1 = 2 ⋅ 1 + 0
Then the Extended Euclidean algorithm:
1 = 5 − 2 ⋅ 2 1 = 5 − 2 ( 7 − 5 ) 1 = 3 ⋅ 5 − 2 ⋅ 7
\begin{aligned}
1 &= 5 - 2 \cdot 2 \
1 &= 5 - 2 (7 - 5) \
1 &= 3 \cdot 5 - 2 \cdot 7 \
\end{aligned}
1 1 1 = 5 − 2 ⋅ 2 = 5 − 2 ( 7 − 5 ) = 3 ⋅ 5 − 2 ⋅ 7
Which gives us 7 − 1 = − 2 ( m o d 5 ) {7^{-1} = -2 \pmod 5} 7 − 1 = − 2 ( mod 5 ) — we've found the modular
multiplicative inverse of 7 modulo 5! And since we're modulo 5, we have − 2 m o d 5 = 3 {-2
\bmod 5 = 3} − 2 mod 5 = 3 , so 3 {3} 3 is also the modular multiplicative inverse of 7
modulo 5.
Using it, we can get rid of the factor 7 in our linear congruence:
7 j ≡ 1 ( m o d 5 ) 7 − 1 ⋅ 7 j ≡ 7 − 1 ⋅ 1 ( m o d 5 ) j ≡ 3 ⋅ 1 ( m o d 5 ) j ≡ 3 ( m o d 5 )
\begin{aligned}
7j &\equiv 1 \pmod 5 \
7^{-1} \cdot 7j &\equiv 7^{-1} \cdot 1 \pmod 5 \
j &\equiv 3 \cdot 1 \pmod 5 \
j &\equiv 3 \pmod 5 \
\end{aligned}
7 j 7 − 1 ⋅ 7 j j j ≡ 1 ( mod 5 ) ≡ 7 − 1 ⋅ 1 ( mod 5 ) ≡ 3 ⋅ 1 ( mod 5 ) ≡ 3 ( mod 5 )
Let's make another spreadsheet to make sure everything checks out:
Looks good!
However, the Extended Euclidean Algorithm seems rather annoying to implement
in code. I'm sure it's not that bad, but we have an even simpler way available
due to what our puzzle input is.
Another method to determine the modular multiplicative inverse of a a a modulo
m m m exists, if a a a and m m m are coprime. For 7 j ≡ 1 ( m o d 5 ) {7j \equiv 1 \pmod 5} 7 j ≡ 1 ( mod 5 ) , it's
definitely the case: both 7 {7} 7 and 5 {5} 5 are prime.
In that case, we have:
a ϕ ( m ) ≡ 1 ( m o d m )
a^{\phi(m)} \equiv 1 \pmod m
a ϕ ( m ) ≡ 1 ( mod m )
And:
a ϕ ( m ) − 1 ≡ a − 1 ( m o d m )
a^{\phi(m)-1} \equiv a^{-1} \pmod m
a ϕ ( m ) − 1 ≡ a − 1 ( mod m )
Where phi (ϕ
) is Euler's totient function .
ϕ ( m ) {\phi(m)} ϕ ( m ) counts the positive integers up to m m m that are relatively prime to m m m .
If m m m is prime, it's even easier! All integers n n n between 1 {1} 1 and m − 1 {m-1} m − 1
(included) are relatively prime to m m m - in other words, G C D ( n , m ) = 1 GCD(n, m) = 1 GC D ( n , m ) = 1 .
So, for a prime m m m , we have ϕ ( m ) = m − 1 \phi(m) = m - 1 ϕ ( m ) = m − 1 , and thus:
a ϕ ( m ) − 1 ≡ a − 1 ( m o d m )
a^{\phi(m)-1} \equiv a^{-1} \pmod m
a ϕ ( m ) − 1 ≡ a − 1 ( mod m )
Becomes:
a ( m − 1 ) − 1 ≡ a − 1 ( m o d m )
a^{(m-1)-1} \equiv a^{-1} \pmod m
a ( m − 1 ) − 1 ≡ a − 1 ( mod m )
Which reduces to:
a m − 2 ≡ a − 1 ( m o d m )
a^{m-2} \equiv a^{-1} \pmod m
a m − 2 ≡ a − 1 ( mod m )
Using this, we can find 7 − 1 ( m o d 5 ) {7^{-1} \pmod 5} 7 − 1 ( mod 5 ) :
7 − 1 ≡ 7 5 − 2 ( m o d 5 ) 7 − 1 ≡ 7 3 ( m o d 5 ) 7 − 1 ≡ 343 ( m o d 5 ) ( 343 m o d 5 = 3 ) 7 − 1 ≡ 3 ( m o d 5 )
\begin{aligned}
7^{-1} &\equiv 7^{5-2} \pmod 5 \
7^{-1} &\equiv 7^3 \pmod 5 \
7^{-1} &\equiv 343 \pmod 5 \
(343 \bmod 5 &= 3) \
7^{-1} &\equiv 3 \pmod 5 \
\end{aligned}
7 − 1 7 − 1 7 − 1 ( 343 mod 5 7 − 1 ≡ 7 5 − 2 ( mod 5 ) ≡ 7 3 ( mod 5 ) ≡ 343 ( mod 5 ) = 3 ) ≡ 3 ( mod 5 )
We get the same result!
From there - I have good news and bad news. Which do you want to hear first,
bear?
Let's hear the good news first!
Here's the good news: I don't know if you've noticed, but all the bus IDs
in the puzzle inputs are prime numbers.
In my puzzle input, I have 19 , 37 , 383 , 23 , 13 , 29 , 457 , 41 , 17 {19, 37, 383, 23, 13, 29, 457, 41, 17} 19 , 37 , 383 , 23 , 13 , 29 , 457 , 41 , 17 - they're all
primes. This is not a coincidence! I believe the Advent of Code writers have
done this on purpose.
Sounds good! So we can use Euler's totient there?
Although... that's where the bad news come in. Say we have the following
linear congruence:
13 j ≡ 2 ( m o d 457 )
13j \equiv 2 \pmod{457}
13 j ≡ 2 ( mod 457 )
Using Euler's totient, we can find the modular multiplicative inverse of 13
modulo 457 like so:
1 3 − 1 ≡ 1 3 457 − 2 ( m o d 457 ) 1 3 − 1 ≡ 1 3 455 ( m o d 457 )
\begin{aligned}
13^{-1} &\equiv 13^{457-2} \pmod{457} \
13^{-1} &\equiv 13^{455} \pmod{457} \
\end{aligned}
1 3 − 1 1 3 − 1 ≡ 1 3 457 − 2 ( mod 457 ) ≡ 1 3 455 ( mod 457 )
The problem is that uh... 1 3 455 {13^{455}} 1 3 455 is a huge number.
Huge.
As in, it doesn't fit in a u64
:
Rust code
fn main ( ) {
dbg ! ( 13_u64 .pow( 455 ) ) ;
}
Shell session
Compiling playground v0.0.1 (/playground)
Finished dev [unoptimized + debuginfo] target(s) in 1.41s
Running `target/debug/playground`
thread 'main' panicked at 'attempt to multiply with overflow', /rustc/7eac88abb2e57e752f3302f02be5f3ce3d7adfb4/library/core/src/num/mod.rs:707:5
Heck, it doesn't even fit in an u128
!
We could, of course, use something like num-bigint .
Rust code
use num_bigint:: BigUint;
fn main ( ) {
let a: BigUint = "13" . parse ( ) . unwrap ( ) ;
dbg ! ( a.pow( 455 ) .to_str_radix( 10 ) ) ;
}
Shell session
Compiling playground v0.0.1 (/playground)
Finished dev [unoptimized + debuginfo] target(s) in 3.41s
Running `target/debug/playground`
[src/main.rs:5] a.pow(455).to_str_radix(10) = "698594721138087101169088219064926429093683995717535691958391180527375156988715725642243890871883009275610843781276220679332947793384643076241831002323658555648998535582443808358436808350475323422663450896893453131394048123221684800209034474726802596033203335669614369076809716123273257303071068129527888344287266217650968529754239505317017230570888006093561845355916409336361243674362617819009028956341804832084422627863716588624177425577212277628851844621576921451262128531363806650216682920524232108345957"
But here's the interesting thing - just as before, there's a much smaller
modular multiplicative inverse: that value modulo 457, which happens to be
211.
It doesn't stop there though: remember how powers work? 1 3 455 {13^{455}} 1 3 455 is just:
1 3 455 = 13 ⋅ 13 ⋅ 13 … 13 ⋅ 13
13^{455} = 13 \cdot 13 \cdot 13 \dots 13 \cdot 13
1 3 455 = 13 ⋅ 13 ⋅ 13 … 13 ⋅ 13
And remember that we're also "modulo 457". So we can compute it by doing each
individual multiplication, and only keeping the remainder of euclidean
division by 457 at every step:
1 3 2 ≡ 13 ⋅ 13 ≡ 169 ( m o d 457 ) 1 3 3 ≡ 1 3 2 ⋅ 13 ≡ 169 ⋅ 13 ≡ 2197 ≡ 369 ( m o d 457 ) 1 3 4 ≡ 1 3 3 ⋅ 13 ≡ 369 ⋅ 13 ≡ 4797 ≡ 227 ( m o d 457 ) …
\begin{aligned}
13^2 &\equiv 13 \cdot 13 &\equiv 169 \pmod{457} \
13^3 &\equiv 13^2 \cdot 13 &\equiv 169 \cdot 13 \equiv 2197 \equiv 369 \pmod{457} \
13^4 &\equiv 13^3 \cdot 13 &\equiv 369 \cdot 13 \equiv 4797 \equiv 227 \pmod{457} \
\dots \
\end{aligned}
1 3 2 1 3 3 1 3 4 … ≡ 13 ⋅ 13 ≡ 1 3 2 ⋅ 13 ≡ 1 3 3 ⋅ 13 ≡ 169 ( mod 457 ) ≡ 169 ⋅ 13 ≡ 2197 ≡ 369 ( mod 457 ) ≡ 369 ⋅ 13 ≡ 4797 ≡ 227 ( mod 457 )
Or, in code:
Rust code
fn main ( ) {
let a = 13_u64 ;
let m = 457_u64 ;
let mut a_mmi = 1 ;
for _ in 1 ..=( m-2 ) {
a_mmi = ( a_mmi * a) % m;
}
dbg ! ( a_mmi) ;
}
Shell session
Compiling playground v0.0.1 (/playground)
Finished dev [unoptimized + debuginfo] target(s) in 3.15s
Running `target/debug/playground`
[src/main.rs:9] a_mmi = 211
Of course, we could optimize that - we only need to wrap around when we would
overflow u64
. Luckily, Rust comes with a checked_pow
function that simply
returns None
if we would overflow, so:
Rust code
fn main ( ) {
dbg ! ( modular_multiplicative_inverse( 13 , 457 ) ) ;
}
/// Finds the modular multiplicative inverse of `a` modulo `m`
/// Returns the wrong result if `m` isn't prime.
fn modular_multiplicative_inverse ( a : i64 , m : u32 ) -> i64 {
modular_pow ( a, m - 2 , m as _ )
}
fn modular_pow ( x : i64 , exp : u32 , modulo : i64 ) -> i64 {
( match x. checked_pow ( exp) {
Some( x) => x,
None => {
let exp_a = exp / 2 ;
let exp_b = exp - exp_a;
modular_pow ( x, exp_a, modulo) * modular_pow ( x, exp_b, modulo)
}
} ) % modulo
}
Shell session
Compiling playground v0.0.1 (/playground)
Finished dev [unoptimized + debuginfo] target(s) in 0.78s
Running `target/debug/playground`
[src/main.rs:2] modular_multiplicative_inverse(13, 457) = 211
Out of curiosity, I added some debug printing to know how many times
modular_pow
was called: turns out, just 63 times! Much better than our 457
loop than before. I have no doubt there are even smarter solutions out there,
but this'll do.
Notably, num-bigint
provides a
modpow
function, whose comment mentions "Montgomery multiplication" for any odd modulus - this
seems like it would work here, except for m = 2
(the only prime that's also an even
number), for which the result of modular_multiplicative_inverse
would be 1
anyway,
since aᵐ⁻² = a⁰ = 1
.
But let's not make this article any longer, shall we.
Okay! Should we get back to the problem at hand?
Let's go back to this set of linear congruences:
{ x ≡ 5 ( m o d 7 ) x ≡ 1 ( m o d 5 ) x ≡ 2 ( m o d 3 )
\left{
\begin{aligned}
x &\equiv 5 \pmod 7 \
x &\equiv 1 \pmod 5 \
x &\equiv 2 \pmod 3 \
\end{aligned}
\right.
⎩ ⎨ ⎧ x x x ≡ 5 ( mod 7 ) ≡ 1 ( mod 5 ) ≡ 2 ( mod 3 )
We rewrote x x x as:
x = 7 j + 5
x = 7j + 5
x = 7 j + 5
Then substituted x
in the second linear congruence:
x ≡ 1 ( m o d 5 ) 7 j + 5 ≡ 1 ( m o d 5 ) 7 j ≡ 1 − 5 ≡ 1 ( m o d 5 )
\begin{aligned}
x &\equiv 1 \pmod 5 \
7j + 5 &\equiv 1 \pmod 5 \
7j &\equiv 1 - 5 \equiv 1 \pmod 5 \
\end{aligned}
x 7 j + 5 7 j ≡ 1 ( mod 5 ) ≡ 1 ( mod 5 ) ≡ 1 − 5 ≡ 1 ( mod 5 )
We've just seen that the modular multiplicative inverse of 7 modulo 5 is 3,
so that gives us j ≡ 3 ( m o d 5 ) {j \equiv 3 \pmod 5} j ≡ 3 ( mod 5 ) .
Rewriting this as an expression, we get:
j = 5 k + 3
j = 5k + 3
j = 5 k + 3
Then we substitute j
:
x = 7 j + 5 x = 7 ( 5 k + 3 ) + 5 x = 35 k + 7 ⋅ 3 + 5 x = 35 k + 26
\begin{aligned}
x &= 7j + 5 \
x &= 7(5k + 3) + 5 \
x &= 35k + 7 \cdot 3 + 5 \
x &= 35k + 26 \
\end{aligned}
x x x x = 7 j + 5 = 7 ( 5 k + 3 ) + 5 = 35 k + 7 ⋅ 3 + 5 = 35 k + 26
Finally, we substitute x
in our last congruence:
x ≡ 2 ( m o d 3 ) 35 k + 26 ≡ 2 ( m o d 3 )
\begin{aligned}
x &\equiv 2 \pmod 3 \
35k + 26 &\equiv 2 \pmod 3 \
\end{aligned}
x 35 k + 26 ≡ 2 ( mod 3 ) ≡ 2 ( mod 3 )
And solve it:
35 k ≡ ( 2 − 26 ) ≡ − 24 ≡ 0 ( m o d 3 ) 35 k ≡ 0 ( m o d 3 )
\begin{aligned}
35k &\equiv (2 - 26) \equiv -24 \equiv 0 \pmod 3 \
35k &\equiv 0 \pmod 3 \
\end{aligned}
35 k 35 k ≡ ( 2 − 26 ) ≡ − 24 ≡ 0 ( mod 3 ) ≡ 0 ( mod 3 )
We need the modular multiplicative inverse of 35 modulo 3. Luckily, 3 is prime,
so we can re-use our code...
Hang on - don't we have 0 on the right-hand side? Doesn't that mean that
whatever we multiply both sides by, the right-hand side will remain 0?
That means we can just get rid of the 35 factor:
k ≡ 0 ( m o d 3 )
k \equiv 0 \pmod 3
k ≡ 0 ( mod 3 )
Then express k
:
k = 3 l
k = 3l
k = 3 l
Substitute k
in our last expression for x
:
x = 35 k + 26 x = 35 ( 3 l ) + 26 x = 105 l + 26
\begin{aligned}
x &= 35k + 26 \
x &= 35(3l) + 26 \
x &= 105l + 26 \
\end{aligned}
x x x = 35 k + 26 = 35 ( 3 l ) + 26 = 105 l + 26
And that's our solution!
As a reminder, this was our set:
x ≡ 5 ( m o d 7 ) x ≡ 1 ( m o d 5 ) x ≡ 2 ( m o d 3 )
\begin{aligned}
x &\equiv 5 \pmod 7 \
x &\equiv 1 \pmod 5 \
x &\equiv 2 \pmod 3 \
\end{aligned}
x x x ≡ 5 ( mod 7 ) ≡ 1 ( mod 5 ) ≡ 2 ( mod 3 )
I think it's time to move on to an example from the Advent of Code: the
following input:
Translates to the following set of linear congruences:
{ x ≡ 0 ( m o d 17 ) x ≡ 2 ( m o d 13 ) x ≡ 3 ( m o d 19 )
\left{
\begin{aligned}
x &\equiv 0 \pmod{17} \
x &\equiv 2 \pmod{13} \
x &\equiv 3 \pmod{19} \
\end{aligned}
\right.
⎩ ⎨ ⎧ x x x ≡ 0 ( mod 17 ) ≡ 2 ( mod 13 ) ≡ 3 ( mod 19 )
The remainders (0, 2 and 3) are the position of the items in the list.
We'll do exactly as before - but we'll try and write a bit of code to help us
along the way.
Our first congruence gives us the following expression:
x = 17 j
x = 17j
x = 17 j
We can then replace it in the second congruence:
x ≡ 2 ( m o d 13 ) 17 j ≡ 2 ( m o d 13 )
\begin{aligned}
x &\equiv 2 \pmod{13} \
17j &\equiv 2 \pmod{13} \
\end{aligned}
x 17 j ≡ 2 ( mod 13 ) ≡ 2 ( mod 13 )
Let's think about how we could solve that congruence in code.
First we'd need a way to represent it. There's probably a very simple way to
do all this, but I haven't looked at anyone else's code, so I just want to try
and reproduce in code what we've been doing by hand.
If we're going to write a "solver", we need to be able to represent
expressions, including expressions with variables.
We could start with something as simple as this:
Rust code
#[ derive( Clone, Debug, PartialEq, Eq) ]
enum Expr {
Literal( i64 ) ,
Var,
Add( Vec < Expr > ) ,
Mul( Vec < Expr > ) ,
}
Then we can start working on a "reduce" method: for example, Add(vec![2, 3])
should reduce to Literal(5)
.
Rust code
impl Expr {
fn reduce ( & self ) -> Expr {
match self {
& Expr:: Literal( lit) => Expr:: Literal ( lit) ,
Expr:: Var => Expr:: Var,
Expr:: Add( items) => {
let ( literals, others) : ( Vec < _ > , Vec < _ > ) = items
. iter ( )
. map ( Self:: reduce)
. partition ( |x| matches ! ( x, Self::Literal( _) ) ) ;
if literals. is_empty ( ) && others. is_empty ( ) {
Expr:: Literal ( 0 )
} else {
let mut terms = others;
let sum = literals
. into_iter ( )
. map ( |x| {
if let Expr:: Literal( x) = x {
x
} else {
unreachable ! ( )
}
} )
. sum ( ) ;
if sum != 0 {
if terms. is_empty ( ) {
return Self:: Literal ( sum) ;
} else {
terms. insert ( 0 , Self:: Literal ( sum) ) ;
}
}
if terms. len ( ) == 1 {
terms. pop ( ) . unwrap ( )
} else {
Expr:: Add ( terms)
}
}
}
Expr:: Mul( items) => {
let ( literals, others) : ( Vec < _ > , Vec < _ > ) = items
. iter ( )
. map ( Self:: reduce)
. partition ( |x| matches ! ( x, Self::Literal( _) ) ) ;
if literals. is_empty ( ) && others. is_empty ( ) {
Expr:: Literal ( 1 )
} else {
let mut terms = others;
let product = literals
. into_iter ( )
. map ( |x| {
if let Expr:: Literal( x) = x {
x
} else {
unreachable ! ( )
}
} )
. product ( ) ;
if product != 1 {
if terms. is_empty ( ) {
return Self:: Literal ( product) ;
} else {
terms. insert ( 0 , Self:: Literal ( product) ) ;
}
}
if terms. len ( ) == 1 {
terms. pop ( ) . unwrap ( )
} else {
Expr:: Mul ( terms)
}
}
}
}
}
}
That's a lot of code, let's write some tests!
Rust code
#[ test]
fn test_reduce ( ) {
assert_eq ! ( Expr::Add( vec![ ] ) .reduce( ) , Expr::Literal( 0 ) .reduce( ) ) ;
assert_eq ! (
Expr::Add( vec![ Expr::Literal( 2 ) , Expr::Literal( 3 ) ] ) .reduce( ) ,
Expr::Add( vec![ Expr::Literal( 5 ) ] ) .reduce( ) ,
) ;
assert_eq ! (
Expr::Add( vec![ Expr::Literal( 2 ) , Expr::Literal( 3 ) , Expr::Literal( 5 ) ] ) .reduce( ) ,
Expr::Add( vec![ Expr::Literal( 10 ) ] ) .reduce( ) ,
) ;
assert_eq ! (
Expr::Add( vec![ Expr::Literal( 2 ) , Expr::Literal( 3 ) , Expr::Var] ) .reduce( ) ,
Expr::Add( vec![ Expr::Literal( 5 ) , Expr::Var] ) .reduce( ) ,
) ;
assert_eq ! (
Expr::Mul( vec![ Expr::Literal( 2 ) , Expr::Literal( 3 ) , Expr::Var] ) .reduce( ) ,
Expr::Mul( vec![ Expr::Literal( 6 ) , Expr::Var] ) .reduce( ) ,
) ;
assert_eq ! (
Expr::Mul( vec![
Expr::Add( vec![ Expr::Literal( 2 ) , Expr::Literal( 3 ) ] ) ,
Expr::Literal( 10 ) ,
Expr::Var
] )
.reduce( ) ,
Expr::Mul( vec![ Expr::Literal( 50 ) , Expr::Var] ) .reduce( ) ,
) ;
}
This passes - seems like a decent start!
Now we must have a way to represent linear congruences:
Rust code
#[ derive( Clone, Debug, PartialEq, Eq) ]
struct LinearCongruence {
lhs : Expr ,
rhs : Expr ,
modulo : u32 ,
}
Now, we can represent the linear congruence we wanted to solve:
Rust code
fn main ( ) {
let lc = LinearCongruence {
lhs : Expr:: Mul ( vec ! [ Expr::Literal( 17 ) , Expr::Var] ) ,
rhs : Expr:: Literal ( 2 ) ,
modulo : 13 ,
} ;
println ! ( "{:?}" , lc) ;
}
Shell session
$ cargo run --quiet
LinearCongruence { lhs: Mul([Literal(17), Var]), rhs: Literal(2), modulo: 13 }
Mhh, this isn't the prettiest way we could print that. How about we provide
a custom Debug
implementation for Expr
?
Rust code
impl fmt:: Debug for Expr {
fn fmt ( & self , f : & mut fmt:: Formatter < ' _ > ) -> fmt:: Result {
match self {
& Expr:: Literal( lit) => write ! ( f, "{}" , lit) ,
Expr:: Var => write ! ( f, "x" ) ,
Expr:: Add( terms) => {
write ! ( f, "(" ) ?;
for ( i, term) in terms. iter ( ) . enumerate ( ) {
if i == 0 {
write ! ( f, "{:?}" , term) ?;
} else {
write ! ( f, " + {:?}" , term) ?;
}
}
write ! ( f, ")" ) ?;
Ok ( ( ) )
}
Expr:: Mul( terms) => {
write ! ( f, "(" ) ?;
for ( i, term) in terms. iter ( ) . enumerate ( ) {
if i == 0 {
write ! ( f, "{:?}" , term) ?;
} else {
write ! ( f, " * {:?}" , term) ?;
}
}
write ! ( f, ")" ) ?;
Ok ( ( ) )
}
}
}
}
Shell session
$ cargo run --quiet
LinearCongruence { lhs: (17 * x), rhs: 2, modulo: 13 }
Better! Now a custom Debug
implementation for LinearCongruence
:
Rust code
impl fmt:: Debug for LinearCongruence {
fn fmt ( & self , f : & mut fmt:: Formatter < ' _ > ) -> fmt:: Result {
write ! ( f, "{:?} ≡ {:?} (mod {})" , self .lhs, self .rhs, self .modulo)
}
}
Shell session
$ cargo run --quiet
(17 * x) ≡ 2 (mod 13)
Super neat!
It's time to try and solve linear congruences in code.
This case is easy - we just need to multiply both sides by the modular
multiplicative inverse of 17.
Rust code
#[ derive( Debug) ]
struct CantSolve ( LinearCongruence ) ;
impl fmt:: Display for CantSolve {
fn fmt ( & self , f : & mut fmt:: Formatter < ' _ > ) -> fmt:: Result {
fmt:: Debug:: fmt ( self , f)
}
}
impl std:: error:: Error for CantSolve { }
impl LinearCongruence {
fn solve ( & self ) -> Result < Self , CantSolve > {
if let Expr:: Mul( items) = & self . lhs {
if let [ Expr:: Literal( lit) , Expr:: Var] = items[ ..] {
let mmi = modular_multiplicative_inverse ( lit as _ , self . modulo ) ;
todo ! ( "Must multiply both sides by {}" , mmi) ;
}
}
Err ( CantSolve ( self . clone ( ) ) )
}
}
Let's stop there and verify it's attempting the right thing:
Rust code
fn main ( ) {
let lc = LinearCongruence {
lhs : Expr:: Mul ( vec ! [ Expr::Literal( 17 ) , Expr::Var] ) ,
rhs : Expr:: Literal ( 2 ) ,
modulo : 13 ,
} ;
dbg ! ( &lc) ;
let lc = lc. solve ( ) . unwrap ( ) ;
dbg ! ( &lc) ;
}
Shell session
$ cargo run --quiet
[src/main.rs:326] &lc = (17 * x) ≡ 2 (mod 13)
thread 'main' panicked at 'not yet implemented: Must multiply both sides by 10', src/main.rs:312:17
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
Seems fairly straightforward - except we haven't really taught our reduce
method about modulos, so if we just do the obvious - multiply on both sides:
Rust code
impl Expr {
/// Multiply `self` by `expr`
fn mul ( & self , expr : Expr ) -> Self {
match self {
Self:: Mul( items) => {
Self:: Mul ( std:: iter:: once ( expr) . chain ( items. iter ( ) . cloned ( ) ) . collect ( ) )
}
_ => Self:: Mul ( vec ! [ expr, self .clone( ) ] ) ,
}
}
}
impl LinearCongruence {
/// Multiply both sides of congruence by `expr`
fn mul ( & self , expr : Expr ) -> Self {
Self {
lhs : self . lhs . mul ( expr. clone ( ) ) . reduce ( ) ,
rhs : self . rhs . mul ( expr) . reduce ( ) ,
modulo : self . modulo ,
}
}
}
impl LinearCongruence {
fn solve ( & self ) -> Result < Self , CantSolve > {
eprintln ! ( "should solve {:?}" , self ) ;
if let Expr:: Mul( items) = & self . lhs {
if let [ Expr:: Literal( lit) , Expr:: Var] = items[ ..] {
let mmi = modular_multiplicative_inverse ( lit, self . modulo ) ;
eprintln ! ( "multiplying by mmi: {}" , mmi) ;
return self . mul ( Expr:: Literal ( mmi) ) . solve ( ) ;
}
}
Err ( CantSolve ( self . clone ( ) ) )
}
}
fn main ( ) {
let lc = LinearCongruence {
lhs : Expr:: Mul ( vec ! [ Expr::Literal( 17 ) , Expr::Var] ) ,
rhs : Expr:: Literal ( 2 ) ,
modulo : 13 ,
} ;
let lc = lc. solve ( ) . unwrap ( ) ;
dbg ! ( &lc) ;
}
We get an infinite loop:
Shell session
$ cargo run --quiet 2>&1 | head
should solve (17 * x) ≡ 2 (mod 13)
multiplying by mmi: 10
should solve (170 * x) ≡ 20 (mod 13)
multiplying by mmi: 1
should solve (170 * x) ≡ 20 (mod 13)
multiplying by mmi: 1
should solve (170 * x) ≡ 20 (mod 13)
multiplying by mmi: 1
should solve (170 * x) ≡ 20 (mod 13)
multiplying by mmi: 1
Because 170 m o d 13 = 1 {170 \bmod 13 = 1} 170 mod 13 = 1 , but Expr
doesn't know we're modulo 13! So,
I think we need a second method - modulo
:
Rust code
impl Expr {
fn modulo ( & self , modulo : u32 ) -> Self {
match self {
& Self:: Literal( lit) => Expr:: Literal ( lit. rem_euclid ( modulo as _ ) ) ,
Self:: Var => Expr:: Var,
Self:: Add( _) => self . clone ( ) ,
Self:: Mul( items) => Self:: Mul ( items. iter ( ) . map ( |x| x. modulo ( modulo) ) . collect ( ) ) ,
}
}
}
In the case of mul
, we reduce
again, because if we start with 170 x {170x} 170 x and end
up with 1 x {1x} 1 x , we want to get rid of that 1 {1} 1 .
Let's try it out:
Rust code
impl LinearCongruence {
/// Multiply both sides of congruence by `expr`
fn mul ( & self , expr : Expr ) -> Self {
Self {
lhs : self . lhs . mul ( expr. clone ( ) ) . reduce ( ) . modulo ( self . modulo ) ,
rhs : self . rhs . mul ( expr) . reduce ( ) . modulo ( self . modulo ) ,
modulo : self . modulo ,
}
}
}
Shell session
$ cargo run --quiet
should solve (17 * x) ≡ 2 (mod 13)
multiplying by mmi: 10
should solve x ≡ 7 (mod 13)
thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: CantSolve(x ≡ 7 (mod 13))', src/main.rs:372:25
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
Alright! Turns out, this is the solved form - the variable is isolated on the
left, there's nothing left to do.
Let's add a condition for that:
Rust code
impl LinearCongruence {
fn solve ( & self ) -> Result < Self , CantSolve > {
eprintln ! ( "should solve {:?}" , self ) ;
if let Expr:: Mul( items) = & self . lhs {
if let [ Expr:: Literal( lit) , Expr:: Var] = items[ ..] {
let mmi = modular_multiplicative_inverse ( lit, self . modulo ) ;
eprintln ! ( "multiplying by mmi: {}" , mmi) ;
return self . mul ( Expr:: Literal ( mmi) ) . solve ( ) ;
}
}
if let Expr:: Var = & self . lhs {
// 👇
// already solved!
return Ok ( self . clone ( ) ) ;
}
Err ( CantSolve ( self . clone ( ) ) )
}
}
Rust code
$ cargo run --quiet
should solve ( 17 * x) ≡ 2 ( mod 13 )
multiplying by mmi: 10
should solve x ≡ 7 ( mod 13 )
[ src/main. rs : 378 ] & lc = x ≡ 7 ( mod 13 )
Okay! We've solved 17 j ≡ 2 ( m o d 13 ) {17j \equiv 2 \pmod{13}} 17 j ≡ 2 ( mod 13 ) with code.
What were we doing again? Oh right, solving a set of linear congruences.
Now we can express j j j as an.. expression:
Rust code
impl LinearCongruence {
/// Turns this linear congruence into an expression,
/// for example `x ≡ 7 (mod 13)` would give `13*var + 7`.
/// Panics if linear congruence is not solved yet.
fn expr ( & self ) -> Expr {
match ( & self . lhs , & self . rhs ) {
( Expr:: Var, & Expr:: Literal( remainder) ) => Expr:: Add ( vec ! [
Expr::Mul( vec![ Expr::Literal( self .modulo as _) , Expr::Var] ) ,
Expr::Literal( remainder) ,
] ) ,
_ => {
panic ! (
"Expected solved congruence (of form `var ≡ literal (mod m)`), but got `{:?}`" ,
self
)
}
}
}
}
Rust code
fn main ( ) {
let lc = LinearCongruence {
lhs : Expr:: Mul ( vec ! [ Expr::Literal( 17 ) , Expr::Var] ) ,
rhs : Expr:: Literal ( 2 ) ,
modulo : 13 ,
} ;
let lc = lc. solve ( ) . unwrap ( ) ;
dbg ! ( &lc) ;
// 👇 new!
let expr = lc. expr ( ) ;
dbg ! ( &expr) ;
}
Shell session
$ cargo run --quiet
should solve (17 * x) ≡ 2 (mod 13)
multiplying by mmi: 10
should solve x ≡ 7 (mod 13)
[src/main.rs:398] &lc = x ≡ 7 (mod 13)
[src/main.rs:400] &expr = ((13 * x) + 7)
Things get a bit confusing here, since we only have one variable in code (for
simplicity), when we actually are dealing with several variables in the maths
world.
Let's recap what we've done so far:
From first congruence x ≡ 0 ( m o d 17 ) As an equation x = 17 j + 0 = 17 j From second congruence x ≡ 2 ( m o d 13 ) Substitution 17 j ≡ 2 ( m o d 13 ) After solving j ≡ 7 ( m o d 13 ) As an equation j = 13 k + 7
\begin{aligned}
&\text{From first congruence} \
x &\equiv 0 \pmod{17} \
&\text{As an equation} \
x &= 17j + 0 = 17j \
&\text{From second congruence} \
x &\equiv 2 \pmod{13} \
&\text{Substitution} \
17j &\equiv 2 \pmod{13} \
&\text{After solving} \
j &\equiv 7 \pmod{13} \
&\text{As an equation} \
j &= 13k + 7 \
\end{aligned}
x x x 17 j j j From first congruence ≡ 0 ( mod 17 ) As an equation = 17 j + 0 = 17 j From second congruence ≡ 2 ( mod 13 ) Substitution ≡ 2 ( mod 13 ) After solving ≡ 7 ( mod 13 ) As an equation = 13 k + 7
Now we need to replace the j j j in x = 17 j {x = 17j} x = 17 j with 13 k + 7 {13k + 7} 13 k + 7 .
Let's try and make a method for that:
Rust code
impl Expr {
// Replaces `Expr::Var` with `expr` everywhere in that expression
fn replace ( & self , expr : Expr ) -> Self {
match self {
& Expr:: Literal( lit) => Expr:: Literal ( lit) ,
Expr:: Var => expr,
Expr:: Add( items) => Expr:: Add (
items
. iter ( )
. cloned ( )
. map ( |ex| ex. replace ( expr. clone ( ) ) )
. collect ( ) ,
) ,
Expr:: Mul( items) => Expr:: Mul (
items
. iter ( )
. cloned ( )
. map ( |ex| ex. replace ( expr. clone ( ) ) )
. collect ( ) ,
) ,
}
}
}
And actually do it:
Rust code
fn main ( ) {
let lc = LinearCongruence {
lhs : Expr:: Mul ( vec ! [ Expr::Literal( 17 ) , Expr::Var] ) ,
rhs : Expr:: Literal ( 2 ) ,
modulo : 13 ,
} ;
let lc = lc. solve ( ) . unwrap ( ) ;
dbg ! ( &lc) ;
let expr = lc. expr ( ) ;
dbg ! ( &expr) ;
let expr = LinearCongruence {
lhs : Expr:: Var,
rhs : Expr:: Literal ( 0 ) ,
modulo : 17 ,
}
. expr ( )
. replace ( expr) ;
dbg ! ( &expr) ;
}
Shell session
$ main
❯ cargo run --quiet
should solve (17 * x) ≡ 2 (mod 13)
multiplying by mmi: 10
should solve x ≡ 7 (mod 13)
[src/main.rs:452] &lc = x ≡ 7 (mod 13)
[src/main.rs:454] &expr = ((13 * x) + 7)
[src/main.rs:463] &expr = ((17 * ((13 * x) + 7)) + 0
Things are getting quite confusing now, since x
is used for everything.
Let's make a slight adjustement: Var
will now take a char
- but we'll
still assume we only ever have one var in a given expression.
Rust code
#[ derive( Clone, PartialEq, Eq) ]
enum Expr {
Literal( i64 ) ,
Var( char ) ,
Add( Vec < Expr > ) ,
Mul( Vec < Expr > ) ,
}
We'll need to fix up our Debug
implementation:
Rust code
impl fmt:: Debug for Expr {
fn fmt ( & self , f : & mut fmt:: Formatter < ' _ > ) -> fmt:: Result {
match self {
& Expr:: Literal( lit) => write ! ( f, "{}" , lit) ,
// 👇
Expr:: Var( c) => write ! ( f, "{}" , c) ,
// (other arms omitted)
}
}
}
along with Expr::reduce
, our reduce tests, LinearCongruence::solve
,
also LinearCongruence::expr
- which will now take the name of the new
variable:
Rust code
impl LinearCongruence {
/// Turns this linear congruence into an expression,
/// for example `x ≡ 7 (mod 13)` would give `13*name + 7`.
/// Panics if linear congruence is not solved yet.
// 👇
fn expr ( & self , name : char ) -> Expr {
match ( & self . lhs , & self . rhs ) {
( Expr:: Var( _) , & Expr:: Literal( remainder) ) => Expr:: Add ( vec ! [
// 👇
Expr::Mul( vec![ Expr::Literal( self .modulo as _) , Expr::Var( name) ] ) ,
Expr::Literal( remainder) ,
] ) ,
_ => {
panic ! (
"Expected solved congruence (of form `var ≡ literal (mod m)`), but got `{:?}`" ,
self
)
}
}
}
}
(The changes that aren't shown are left as an exercise to the reader).
And to really be able to describe what we're doing with just method calls, we'll
add a replace
method to LinearCongruence
as well:
Rust code
impl LinearCongruence {
// Replaces `Expr::Var` with `expr` everywhere in that expression
fn replace ( & self , expr : Expr ) -> Self {
Self {
lhs : self . lhs . replace ( expr. clone ( ) ) ,
rhs : self . rhs . replace ( expr) ,
modulo : self . modulo ,
}
}
}
Now let's use actual names in our main
function.
Rust code
fn main ( ) {
let con1 = LinearCongruence {
lhs : Expr:: Var ( 'x' ) ,
rhs : Expr:: Literal ( 0 ) ,
modulo : 17 ,
} ;
let con2 = LinearCongruence {
lhs : Expr:: Var ( 'x' ) ,
rhs : Expr:: Literal ( 2 ) ,
modulo : 13 ,
} ;
let con3 = LinearCongruence {
lhs : Expr:: Var ( 'x' ) ,
rhs : Expr:: Literal ( 3 ) ,
modulo : 19 ,
} ;
println ! ( "First congruence" ) ;
println ! ( "{:?}" , con1) ;
let x = con1. expr ( 'j' ) ;
println ! ( "x = {:?}" , x) ;
let x = x. reduce ( ) ;
println ! ( "After simplification" ) ;
println ! ( "x = {:?}" , x) ;
println ! ( "Second congruence" ) ;
println ! ( "{:?}" , con2) ;
let con2 = con2. replace ( x. clone ( ) ) ;
println ! ( "After substitution" ) ;
println ! ( "{:?}" , con2) ;
let con2 = con2. solve ( ) . unwrap ( ) ;
println ! ( "Solved" ) ;
println ! ( "{:?}" , con2) ;
println ! ( "As equation" ) ;
let j = con2. expr ( 'k' ) ;
println ! ( "j = {:?}" , j) ;
println ! ( "After substitution" ) ;
let x = x. replace ( j) ;
println ! ( "x = {:?}" , x) ;
println ! ( "After simplification" ) ;
let x = x. reduce ( ) ;
println ! ( "x = {:?}" , x) ;
}
Shell session
$ cargo run --quiet
First congruence
x ≡ 0 (mod 17)
x = ((17 * j) + 0)
After simplification
x = (17 * j)
Second congruence
x ≡ 2 (mod 13)
After substitution
(17 * j) ≡ 2 (mod 13)
should solve (17 * j) ≡ 2 (mod 13)
multiplying by mmi: 10
should solve j ≡ 7 (mod 13)
Solved
j ≡ 7 (mod 13)
As equation
j = ((13 * k) + 7)
After substitution
x = (17 * ((13 * k) + 7))
After simplification
x = (17 * (7 + (13 * k)))
Okay, okay, there's a wrinkle - we don't know how to distribute yet. Well,
let's try it!
Rust code
impl Expr {
fn distribute ( & self ) -> Self {
if let Self:: Mul( items) = self {
if let [ Self:: Literal( lit) , Self:: Add( add_terms) ] = & items[ ..] {
return Self:: Add (
add_terms
. iter ( )
. map ( |ex| ex. mul ( Self:: Literal ( * lit) ) )
. collect ( ) ,
) ;
}
}
self . clone ( )
}
}
Rust code
println ! ( "After substitution" ) ;
let x = x. replace ( j) ;
println ! ( "x = {:?}" , x) ;
// 👇 new!
println ! ( "After distribution" ) ;
let x = x. distribute ( ) ;
println ! ( "x = {:?}" , x) ;
println ! ( "After simplification" ) ;
let x = x. reduce ( ) ;
println ! ( "x = {:?}" , x) ;
Shell session
$ cargo run --quiet
(some lines omitted)
As equation
j = ((13 * k) + 7)
After substitution
x = (17 * ((13 * k) + 7))
After distribution
x = ((17 * 13 * k) + (17 * 7))
After simplification
x = (119 + (221 * k))
Alright! Now we can keep going:
Rust code
// in main:
println ! ( "Third congruence" ) ;
println ! ( "{:?}" , con3) ;
let con3 = con3. replace ( x) ;
println ! ( "After substitution" ) ;
println ! ( "{:?}" , con3) ;
let con3 = con3. solve ( ) . unwrap ( ) ;
println ! ( "Solved" ) ;
println ! ( "{:?}" , con3) ;
Shell session
Third congruence
x ≡ 3 (mod 19)
After substitution
(119 + (221 * k)) ≡ 3 (mod 19)
should solve (119 + (221 * k)) ≡ 3 (mod 19)
thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: CantSolve((119 + (221 * k)) ≡ 3 (mod 19))', src/main.rs:535:31
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
Ah, we don't know how to solve that yet. Well that should be easy! If
the left-hand-side is an addition, and one of the term is a literal, just
subtract it from both sides:
Rust code
impl LinearCongruence {
fn solve ( & self ) -> Result < Self , CantSolve > {
eprintln ! ( "should solve {:?}" , self ) ;
if let Expr:: Mul( items) = & self . lhs {
if let [ Expr:: Literal( lit) , Expr:: Var( _) ] = items[ ..] {
let mmi = modular_multiplicative_inverse ( lit, self . modulo ) ;
eprintln ! ( "multiplying by mmi: {}" , mmi) ;
return self . mul ( Expr:: Literal ( mmi) ) . solve ( ) ;
}
}
// 👇 new!
if let Expr:: Add( items) = & self . lhs {
if let Some( lit) = items. iter ( ) . find_map ( |expr| match expr {
Expr:: Literal( lit) => Some ( lit) ,
_ => None,
} ) {
eprintln ! ( "adding {} on both sides" , -lit) ;
return self . add ( Expr:: Literal ( -lit) ) . solve ( ) ;
}
}
if let Expr:: Var( _) = & self . lhs {
// already solved!
return Ok ( self . clone ( ) ) ;
}
Err ( CantSolve ( self . clone ( ) ) )
}
}
Shell session
Third congruence
x ≡ 3 (mod 19)
After substitution
(119 + (221 * k)) ≡ 3 (mod 19)
should solve (119 + (221 * k)) ≡ 3 (mod 19)
adding -119 on both sides
should solve (12 * k) ≡ 17 (mod 19)
multiplying by mmi: 8
should solve k ≡ 3 (mod 19)
Solved
k ≡ 3 (mod 19)
Now for the grand finale:
Rust code
println ! ( "As equation" ) ;
let k = con3. expr ( 'l' ) ;
println ! ( "After substitution" ) ;
let x = x. replace ( k) ;
println ! ( "x = {:?}" , x) ;
println ! ( "After distribution" ) ;
let x = x. distribute ( ) ;
println ! ( "x = {:?}" , x) ;
println ! ( "After simplification" ) ;
let x = x. reduce ( ) ;
println ! ( "x = {:?}" , x) ;
Shell session
Solved
k ≡ 3 (mod 19)
As equation
After substitution
x = (119 + (221 * ((19 * l) + 3)))
After distribution
x = (119 + (221 * ((19 * l) + 3)))
After simplification
x = (119 + (221 * (3 + (19 * l))))
Oh, we were a bit too quick with our Expr::distribute
method, let's revise it:
Rust code
impl Expr {
fn distribute ( & self ) -> Self {
if let Self:: Mul( items) = self {
if let [ Self:: Literal( lit) , Self:: Add( add_terms) ] = & items[ ..] {
return Self:: Add (
add_terms
. iter ( )
. map ( |ex| ex. mul ( Self:: Literal ( * lit) ) )
. collect ( ) ,
) ;
}
}
// 👇 new!
if let Self:: Add( items) = self {
return Self:: Add ( items. iter ( ) . map ( |ex| ex. distribute ( ) ) . collect ( ) ) ;
}
self . clone ( )
}
}
Much like the rest of our methods, it won't work for all expressions, but we
just need it to work for the expressions we actually have, so it should bring
us a bit further:
Shell session
Solved
k ≡ 3 (mod 19)
As equation
After substitution
x = (119 + (221 * ((19 * l) + 3)))
After distribution
x = (119 + ((221 * 19 * l) + (221 * 3)))
After simplification
x = (119 + (663 + (4199 * l)))
Mhhh better, but still not quite there - we need a way to turn Add(x, Add(y, z))
into Add(x, y, z)
.
Rust code
impl Expr {
fn reduce ( & self ) -> Expr {
match self {
& Expr:: Literal( lit) => Expr:: Literal ( lit) ,
& Expr:: Var( c) => Expr:: Var ( c) ,
Expr:: Add( items) => {
// 👇 new!
if let Some( ( index, nested_items) ) =
items
. iter ( )
. enumerate ( )
. find_map ( |( index, item) | match item {
Expr:: Add( terms) => Some ( ( index, terms) ) ,
_ => None,
} )
{
return Expr:: Add (
items
. iter ( )
. enumerate ( )
. filter ( |& ( i, _) | i != index)
. map ( |( _, item) | item)
. chain ( nested_items)
. cloned ( )
. collect ( ) ,
)
. reduce ( ) ;
}
// (the rest is as before)
}
// other arms omitted
}
}
}
And with that change, we get the following output:
Shell session
$ cargo run --quiet
First congruence
x ≡ 0 (mod 17)
x = ((17 * j) + 0)
After simplification
x = (17 * j)
Second congruence
x ≡ 2 (mod 13)
After substitution
(17 * j) ≡ 2 (mod 13)
should solve (17 * j) ≡ 2 (mod 13)
multiplying by mmi: 10
should solve j ≡ 7 (mod 13)
Solved
j ≡ 7 (mod 13)
As equation
j = ((13 * k) + 7)
After substitution
x = (17 * ((13 * k) + 7))
After distribution
x = ((17 * 13 * k) + (17 * 7))
After simplification
x = (119 + (221 * k))
Third congruence
x ≡ 3 (mod 19)
After substitution
(119 + (221 * k)) ≡ 3 (mod 19)
should solve (119 + (221 * k)) ≡ 3 (mod 19)
adding -119 on both sides
should solve (12 * k) ≡ 17 (mod 19)
multiplying by mmi: 8
should solve k ≡ 3 (mod 19)
Solved
k ≡ 3 (mod 19)
As equation
After substitution
x = (119 + (221 * ((19 * l) + 3)))
After distribution
x = (119 + ((221 * 19 * l) + (221 * 3)))
After simplification
x = (782 + (4199 * l))
Which means the first solution is x = 782 x = 782 x = 782 , and indeed, we have:
782 m o d 17 = 0 782 m o d 13 = 2 782 m o d 19 = 3
\begin{aligned}
782 \bmod 17 &= 0 \
782 \bmod 13 &= 2 \
782 \bmod 19 &= 3 \
\end{aligned}
782 mod 17 782 mod 13 782 mod 19 = 0 = 2 = 3
..but the advent of code example says otherwise:
The earliest timestamp that matches the list 17,x,13,19 is 3417.
So we clearly went wrong somewhere.
But before we dig into that, let's try and automate the whole process.
Ideally, we'd like a function that can take a Vec<LinearCongruence>
and
can solve the whole thing :
Rust code
fn solve_lincon_system ( cons : Vec < LinearCongruence > ) -> i64 {
println ! ( "Solving system of {} linear congruences" , cons.len( ) ) ;
// Variable naming
let mut curr_var = b'a' ;
let mut next_var = || -> char {
let res = curr_var as char ;
curr_var += 1 ;
res
} ;
let mut cons = cons. iter ( ) ;
let con = cons. next ( ) . unwrap ( ) ;
println ! ( "👉 {:?}" , con) ;
let mut x = con. expr ( next_var ( ) ) . reduce ( ) ;
println ! ( "x = {:?}" , x) ;
for con in cons {
println ! ( "👉 {:?}" , con) ;
x = x
. replace ( con. replace ( x. clone ( ) ) . solve ( ) . unwrap ( ) . expr ( next_var ( ) ) )
. distribute ( )
. reduce ( ) ;
println ! ( "x = {:?}" , x) ;
}
let x = x. replace ( Expr:: Literal ( 0 ) ) . reduce ( ) ;
if let Expr:: Literal( lit) = x {
lit
} else {
panic ! ( "expected `x` to be a literal but got {:?}" , x)
}
}
With that, our whole main
function simply becomes:
Rust code
fn main ( ) {
let con1 = LinearCongruence {
lhs : Expr:: Var ( 'x' ) ,
rhs : Expr:: Literal ( 0 ) ,
modulo : 17 ,
} ;
let con2 = LinearCongruence {
lhs : Expr:: Var ( 'x' ) ,
rhs : Expr:: Literal ( 2 ) ,
modulo : 13 ,
} ;
let con3 = LinearCongruence {
lhs : Expr:: Var ( 'x' ) ,
rhs : Expr:: Literal ( 3 ) ,
modulo : 19 ,
} ;
println ! (
"✅ Solution: {}" ,
solve_lincon_system( vec![ con1, con2, con3] )
) ;
}
And we get:
Shell session
$ cargo run --quiet
Solving system of 3 linear congruences
👉 x ≡ 0 (mod 17)
x = (17 * a)
👉 x ≡ 2 (mod 13)
should solve (17 * a) ≡ 2 (mod 13)
multiplying by mmi: 10
should solve a ≡ 7 (mod 13)
x = (119 + (221 * b))
👉 x ≡ 3 (mod 19)
should solve (119 + (221 * b)) ≡ 3 (mod 19)
adding -119 on both sides
should solve (12 * b) ≡ 17 (mod 19)
multiplying by mmi: 8
should solve b ≡ 3 (mod 19)
x = (782 + (4199 * c))
✅ Solution: 782
Not gonna lie, that's super cool. It's a bit... odd, that going to such
lengths is required to solve that problem, but uhh it's really really cool to
have the steps printed out like that.
We can even go one step further - taking the input, parsing it, generating
a system of linear congruences, and solving it.
First off, we can change our solve_lincon_system
to simply take an
Iterator
:
Rust code
fn solve_lincon_system < I > ( mut cons : I ) -> i64
where
I : Iterator < Item = LinearCongruence > ,
{
// (same code, with the first `println!` omitted, because it called `.len()`)
}
If we still wanted to call it manually, we'd do this:
Rust code
fn main ( ) {
// omitted: let con1, con2, con3
println ! (
"✅ Solution: {}" ,
// new: we call into_iter 👇
solve_lincon_system( vec![ con1, con2, con3] .into_iter( ) )
) ;
}
But we don't! We want to call it from ProblemStatement::solve
, where we do
have an Iterator
, because we map
from ProblemStatement::buses
:
I can't believe you've found a way to make this about iterators again.
Rust code
impl ProblemStatement {
fn solve ( & self ) -> i64 {
solve_lincon_system ( self . buses . iter ( ) . map ( |bus| LinearCongruence {
lhs : Expr:: Var ( 'x' ) ,
rhs : Expr:: Literal ( bus. time_offset as _ ) ,
modulo : bus. id as _ ,
} ) )
}
}
Now our main becomes:
Rust code
fn main ( ) {
println ! (
"✅ Solution: {}" ,
ProblemStatement::parse( "0\n17,x,13,19" ) .solve( )
) ;
}
And still gives the same solution:
Shell session
$ cargo run --quiet
👉 x ≡ 0 (mod 17)
x = (17 * a)
👉 x ≡ 2 (mod 13)
should solve (17 * a) ≡ 2 (mod 13)
multiplying by mmi: 10
should solve a ≡ 7 (mod 13)
x = (119 + (221 * b))
👉 x ≡ 3 (mod 19)
should solve (119 + (221 * b)) ≡ 3 (mod 19)
adding -119 on both sides
should solve (12 * b) ≡ 17 (mod 19)
multiplying by mmi: 8
should solve b ≡ 3 (mod 19)
x = (782 + (4199 * c))
✅ Solution: 782
But as mentioned.. that's not the solution the Advent of Code problem
statement gives us.
So let's try and think about our timetable again...
This:
x ≡ 0 ( m o d 17 )
x \equiv 0 \pmod{17}
x ≡ 0 ( mod 17 )
Definitely means that Bus 17 leaves at x x x . (And x + 17 x + 17 x + 17 , and x + 2 ⋅ 17 x + 2 \cdot 17 x + 2 ⋅ 17 , etc.)
But what does this mean?
x ≡ 2 ( m o d 13 )
x \equiv 2 \pmod{13}
x ≡ 2 ( mod 13 )
Does it really mean that Bus 13 leaves in 2 minutes?
Ohhhhhhhhhhhhhhhhhhhh. OHHHHHHH! That's not what it means at all!
What it actually means is that Bus 13 left 2 minutes ago . The problem we've
been solving — for quite a few minutes now — is: what's the timestamp x
where:
Bus 17 leaves
Bus 13 has left 2 minutes prior
Bus 19 has left 3 minutes prior
If we want to find a timestamp where Bus 13 leaves 2 minutes after , we need
this instead:
x ≡ 13 − 2 ( m o d 13 ) x ≡ 11 ( m o d 13 )
\begin{aligned}
x &\equiv 13 - 2 \pmod{13} \
x &\equiv 11 \pmod{13} \
\end{aligned}
x x ≡ 13 − 2 ( mod 13 ) ≡ 11 ( mod 13 )
Rust code
impl ProblemStatement {
fn solve ( & self ) -> i64 {
solve_lincon_system ( self . buses . iter ( ) . map ( |bus| LinearCongruence {
lhs : Expr:: Var ( 'x' ) ,
// 👇👇👇
rhs : Expr:: Literal ( ( bus. id as i64 - bus. time_offset as i64 ) . rem_euclid ( bus. id as _ ) ) ,
modulo : bus. id as _ ,
} ) )
}
}
Let's try it 🤞:
Shell session
$ cargo run --quiet
👉 x ≡ 0 (mod 17)
x = (17 * a)
👉 x ≡ 11 (mod 13)
should solve (17 * a) ≡ 11 (mod 13)
multiplying by mmi: 10
should solve a ≡ 6 (mod 13)
x = (102 + (221 * b))
👉 x ≡ 16 (mod 19)
should solve (102 + (221 * b)) ≡ 16 (mod 19)
adding -102 on both sides
should solve (12 * b) ≡ 9 (mod 19)
multiplying by mmi: 8
should solve b ≡ 15 (mod 19)
x = (3417 + (4199 * c))
Wait, didn't we have tests?
Oh right — the tests.
Those tests:
Rust code
#[ test]
fn test_solutions ( ) {
macro_rules! test {
( $list: literal, $solution: expr) => {
assert_eq!(
ProblemStatement::parse( concat!( "0\n" , $list, "\n" ) ) .solve( ) ,
$solution
)
} ;
}
test ! ( "17,x,13,19" , 3417 ) ;
test ! ( "67,7,59,61" , 754018 ) ;
test ! ( "67,x,7,59,61" , 779210 ) ;
test ! ( "67,7,x,59,61" , 1261476 ) ;
test ! ( "1789,37,47,1889" , 1202161486 ) ;
}
Well, if we didn't mess anything up... those should still work, right?
They just use ProblemStatement::solve
, which now uses our fancy math.
Shell session
$ cargo t -q
running 2 tests
..
test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
They do!
So now, if we just use the proper puzzle input...
Rust code
fn main ( ) {
println ! (
"✅ Solution: {}" ,
ProblemStatement::parse( include_str!( "input.txt" ) ) .solve( )
) ;
}
Shell session
$ cargo run --quiet
👉 x ≡ 0 (mod 19)
x = (19 * a)
👉 x ≡ 24 (mod 37)
should solve (19 * a) ≡ 24 (mod 37)
multiplying by mmi: 2
should solve a ≡ 11 (mod 37)
x = (209 + (703 * b))
👉 x ≡ 364 (mod 383)
should solve (209 + (703 * b)) ≡ 364 (mod 383)
adding -209 on both sides
should solve (320 * b) ≡ 155 (mod 383)
multiplying by mmi: 231
should solve b ≡ 186 (mod 383)
x = (130967 + (269249 * c))
👉 x ≡ 19 (mod 23)
should solve (130967 + (269249 * c)) ≡ 19 (mod 23)
adding -130967 on both sides
should solve (11 * c) ≡ 14 (mod 23)
multiplying by mmi: 21
should solve c ≡ 18 (mod 23)
x = (4977449 + (6192727 * d))
👉 x ≡ 7 (mod 13)
should solve (4977449 + (6192727 * d)) ≡ 7 (mod 13)
adding -4977449 on both sides
should solve (8 * d) ≡ 11 (mod 13)
multiplying by mmi: 5
should solve d ≡ 3 (mod 13)
x = (23555630 + (80505451 * e))
👉 x ≡ 10 (mod 29)
should solve (23555630 + (80505451 * e)) ≡ 10 (mod 29)
adding -23555630 on both sides
should solve e ≡ 7 (mod 29)
x = (587093787 + (2334658079 * f))
👉 x ≡ 407 (mod 457)
should solve (587093787 + (2334658079 * f)) ≡ 407 (mod 457)
adding -587093787 on both sides
should solve (2 * f) ≡ 353 (mod 457)
multiplying by mmi: 229
should solve f ≡ 405 (mod 457)
x = (946123615782 + (1066938742103 * g))
👉 x ≡ 22 (mod 41)
should solve (946123615782 + (1066938742103 * g)) ≡ 22 (mod 41)
adding -946123615782 on both sides
should solve (35 * g) ≡ 31 (mod 41)
multiplying by mmi: 34
should solve g ≡ 29 (mod 41)
x = (31887347136769 + (43744488426223 * h))
👉 x ≡ 1 (mod 17)
should solve (31887347136769 + (43744488426223 * h)) ≡ 1 (mod 17)
adding -31887347136769 on both sides
should solve (9 * h) ≡ 3 (mod 17)
multiplying by mmi: 2
should solve h ≡ 6 (mod 17)
x = (294354277694107 + (743656303245791 * i))
✅ Solution: 294354277694107
And finally, we have our answer!
But looks at estimated reading time did we really need to do all of that?
What a good-looking question.
It was only when I was 90% done with this, you gotta give it to me, amazing
solution that I went to read about the Chinese Remainder Theorem once more,
and, as it turns out... there's a direct construction method.
If you have a system of linear congruences, like so:
{ x ≡ a 1 ( m o d n 1 ) ⋮ x ≡ a k ( m o d n k )
\left{
\begin{aligned}
x &\equiv a_1 \pmod{n_1} \
\vdots \
x &\equiv a_k \pmod{n_k} \
\end{aligned}
\right.
⎩ ⎨ ⎧ x ⋮ x ≡ a 1 ( mod n 1 ) ≡ a k ( mod n k )
And, if the n i n_i n i are pairwise coprime (any two of them are coprime)...
Which they are for us, since they're all primes in the puzzle input!
We then let N i = N / n i N_i = N/n_i N i = N / n i be the product of all moduli but one.
Because n i n_i n i are pairwise coprime, then N i N_i N i and n i n_i n i are coprime as well.
From there, Bézout's identity applies, and we can say with certainty that
there exists integers M i M_i M i and m i m_i m i such that
M i N i + m i n i = 1
M_i N_i + m_i n_i = 1
M i N i + m i n i = 1
Which, expressed as a congruence modulo n i n_i n i , gives us:
M i N i + m i n i ≡ 1 ( m o d n i ) M i N i ≡ 1 ( m o d n i )
\begin{aligned}
M_i N_i + m_i n_i &\equiv 1 \pmod{n_i} \
M_i N_i &\equiv 1 \pmod{n_i} \
\end{aligned}
M i N i + m i n i M i N i ≡ 1 ( mod n i ) ≡ 1 ( mod n i )
In other words, we simply have M i ≡ N i − 1 ( m o d n i ) M_i \equiv N_i^{-1} \pmod{n_i} M i ≡ N i − 1 ( mod n i ) .
A solution of the system of congruences is:
x = ∑ i = 1 k a i M i N i
x = \sum_{i=1}^k a_i M_i N_i
x = ∑ i = 1 k a i M i N i
Which is the sum, for all i i i , of the remainder a i a_i a i , multiplied by
N i N_i N i , which is the product of all n j n_j n j except for j = i j = i j = i , and again
multiplied by M i M_i M i , which we've just established is the modular
multiplicative inverse of N i ( m o d n i ) N_i \pmod{n_i} N i ( mod n i ) .
Mhhh we can cook with that.
Rust code
fn solve_lincong_system_direct < I > ( congs : I ) -> i64
where
I : Iterator < Item = LinearCongruence > ,
{
// This time, we need to be able to index our linear congruences
let congs: Vec < _ > = congs. collect ( ) ;
fn remainder ( lc : & LinearCongruence ) -> i64 {
match & lc. rhs {
Expr:: Literal( lit) => * lit,
_ => panic ! ( ) ,
}
}
( 0 ..congs. len ( ) )
. map ( |i| {
let a_i = remainder ( & congs[ i] ) ;
let N_i = congs
. iter ( )
. enumerate ( )
. filter ( |& ( j, _) | j != i)
. map ( |( _, con) | con. modulo as i64 )
. product ( ) ;
let M_i = modular_multiplicative_inverse ( N_i, congs[ i] . modulo ) ;
a_i * N_i * M_i
} )
. sum ( )
}
Let's... give it a shot? If we use solve_lincong_system_direct
in
ProblemStatement::solve
... our tests stop passing:
Shell session
$ cargo t -q
running 2 tests
.F
failures:
---- test_solutions stdout ----
thread 'test_solutions' panicked at 'assertion failed: `(left == right)`
left: `49606`,
right: `3417`', src/main.rs:113:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
Ah. We should've found 3417 {3417} 3417 but we found 49606 {49606} 49606 .
Well, is 49606 {49606} 49606 even a solution?
The linear congruence system for the first test was:
{ x ≡ 0 ( m o d 17 ) x ≡ 11 ( m o d 13 ) x ≡ 16 ( m o d 19 )
\left{
\begin{aligned}
x &\equiv 0 \pmod {17} \
x &\equiv 11 \pmod {13} \
x &\equiv 16 \pmod {19} \
\end{aligned}
\right.
⎩ ⎨ ⎧ x x x ≡ 0 ( mod 17 ) ≡ 11 ( mod 13 ) ≡ 16 ( mod 19 )
And we have:
49606 m o d 17 = 0 49606 m o d 13 = 11 49606 m o d 19 = 16
\begin{aligned}
49606 \bmod {17} &= 0 \
49606 \bmod {13} &= 11 \
49606 \bmod {19} &= 16 \
\end{aligned}
49606 mod 17 49606 mod 13 49606 mod 19 = 0 = 11 = 16
So yes, it is a solution! Just not the first solution. In fact, the last
step we found when solving the example gave us all the solution , in the
following form:
x = 3417 + 4199 c
x = 3417 + 4199c
x = 3417 + 4199 c
So we can figure out what the value of c c c is!
49606 = 3417 + 4199 c 46189 = 4199 c c = 46189 4199 c = 11
\begin{aligned}
49606 &= 3417 + 4199c \
46189 &= 4199c \
c &= \frac{46189}{4199} \
c &= 11 \
\end{aligned}
49606 46189 c c = 3417 + 4199 c = 4199 c = 4199 46189 = 11
So the solution we found was 3417 + 4199 ⋅ 11 {3417 + 4199 \cdot 11} 3417 + 4199 ⋅ 11 .
So uhh... can we get the first solution using this direct construction
method?
I don't know. Someone else might know, but I sure don't.
So, had I pursued this solution first, I would've been stuck! Plus,
isn't it a lot more fun to write functions like distribute
, replace
,
reduce
, and solve
?
It sure is! Also, I'm fairly sure all those multiplications and additions
could end up giving us pretty larger numbers. At least with our solution
our numbers stay nice and small.
So we're in agreement, our solution was the only reasonable solution?
Yup. Let's not look at any other solutions, ever.
Until next time, take care, and happy winter holidays!