Let "MTar" mean a Modulus-Target pair. So I can describe the congruence
x =42= 34
by the MTar (42, 34).
================================================================
FIRST EXAMPLE: (fuse-many-MTars '(42 34) '(27 12))
Our goal is to solve this system of congruences:
C1: x =42= 34. C2: x =27= 12.
/--------------------------------------------------------\
With A:=42 and B:=27, is there an x with
x =A= 34 and | Alas, NO. This, since
x =B= 12 ? | Gcd(A,B)=3 does not divide 34-12 .
\________________________________________________________/
================================================================
SECOND EXAMPLE: (fuse-many-MTars '(12 7) '(21 1) '(35 22))
Our goal is to solve this system of congruences:
C1: x =12= 7. C2: x =21= 1. C3: x =35= 22.
/--------------------------------------------------------\
With A:=12 and B:=21, is there an x with
x =A= 7 and | YES, since D := Gcd(A,B)=3 divides 7-1 =: F.
x =B= 1 ? | Their ratio is R := F/D = 2.
LBolt gives 2A + -1B = D. So 4A - 2B = R*D = 7 - 1.
Thus x + 4A = 7. So x := -41 solves the two given congruences.
Reducing this modulo L := Lcm(A,B)=84 gives x := [-41 mod L] = 43.
Upshot: We can fuse the two (Modulus Target) pairs into a single (M T):
(12 7) fuse (21 1) = (L x) =note= (84 43) .
\________________________________________________________/
/--------------------------------------------------------\
With A:=84 and B:=35, is there an x with
x =A= 43 and | YES, since D := Gcd(A,B)=7 divides 43-22 =: F.
x =B= 22 ? | Their ratio is R := F/D = 3.
LBolt gives -2A + 5B = D. So -6A - -15B = R*D = 43 - 22.
Thus x + -6A = 43. So x := 547 solves the two given congruences.
Reducing this modulo L := Lcm(A,B)=420 gives x := [547 mod L] = 127.
Upshot: We can fuse the two (Modulus Target) pairs into a single (M T):
(84 43) fuse (35 22) = (L x) =note= (420 127) .
\________________________________________________________/
================================================================
THIRD EXAMPLE: Here, the first fusion succeeds but the second fusion fails.
(fuse-many-MTars '(18 1) '(20 7) '(21 2))
Our goal is to solve this system of congruences:
C1: x =18= 1. C2: x =20= 7. C3: x =21= 2.
/--------------------------------------------------------\
With A:=18 and B:=20, is there an x with
x =A= 1 and | YES, since D := Gcd(A,B)=2 divides 1-7 =: F.
x =B= 7 ? | Their ratio is R := F/D = -3.
LBolt gives -1A + 1B = D. So 3A - 3B = R*D = 1 - 7.
Thus x + 3A = 1. So x := -53 solves the two given congruences.
Reducing this modulo L := Lcm(A,B)=180 gives x := [-53 mod L] = 127.
Upshot: We can fuse the two (Modulus Target) pairs into a single (M T):
(18 1) fuse (20 7) = (L x) =note= (180 127) .
\________________________________________________________/
/--------------------------------------------------------\
With A:=180 and B:=21, is there an x with
x =A= 127 and | Alas, NO. This, since
x =B= 2 ? | Gcd(A,B)=3 does not divide 127-2 .
\________________________________________________________/
================================================================
FOURTH EXAMPLE: Here, the target value changes after each fusion.
(fuse-many-MTars '(22 5) '(14 11) '(21 18) '(15 3))
Our goal is to solve this system of congruences:
C1: x =22= 5. C2: x =14= 11. C3: x =21= 18. C4: x =15= 3.
/--------------------------------------------------------\
With A:=22 and B:=14, is there an x with
x =A= 5 and | YES, since D := Gcd(A,B)=2 divides 5-11 =: F.
x =B= 11 ? | Their ratio is R := F/D = -3.
LBolt gives 2A + -3B = D. So -6A - -9B = R*D = 5 - 11.
Thus x + -6A = 5. So x := 137 solves the two given congruences.
Reducing this modulo L := Lcm(A,B)=154 gives x := [137 mod L] = 137.
Upshot: We can fuse the two (Modulus Target) pairs into a single (M T):
(22 5) fuse (14 11) = (L x) =note= (154 137) .
\________________________________________________________/
/--------------------------------------------------------\
With A:=154 and B:=21, is there an x with
x =A= 137 and | YES, since D := Gcd(A,B)=7 divides 137-18 =: F.
x =B= 18 ? | Their ratio is R := F/D = 17.
LBolt gives 1A + -7B = D. So 17A - 119B = R*D = 137 - 18.
Thus x + 17A = 137. So x := -2481 solves the two given congruences.
Reducing this modulo L := Lcm(A,B)=462 gives x := [-2481 mod L] = 291.
Upshot: We can fuse the two (Modulus Target) pairs into a single (M T):
(154 137) fuse (21 18) = (L x) =note= (462 291) .
\________________________________________________________/
/--------------------------------------------------------\
With A:=462 and B:=15, is there an x with
x =A= 291 and | YES, since D := Gcd(A,B)=3 divides 291-3 =: F.
x =B= 3 ? | Their ratio is R := F/D = 96.
LBolt gives -1A + 31B = D. So -96A - -2976B = R*D = 291 - 3.
Thus x + -96A = 291. So x := 44643 solves the two given congruences.
Reducing this modulo L := Lcm(A,B)=2310 gives x := [44643 mod L] = 753.
Upshot: We can fuse the two (Modulus Target) pairs into a single (M T):
(462 291) fuse (15 3) = (L x) =note= (2310 753) .
\________________________________________________________/
;;;; End of "fuse-example.txt" ;;;;