# CRT

Display  (HP-41CX, Hewlett Packard 1983 and DM41X, SwissMicros 2020)

Overview
The CRT program represents a solution to the Chinese Remainder Theorem which states that a linear system of congruence equations with pairwise relatively prime moduli has a unique solution modulo the product of the moduli of the system.
Practically, it goes like this. Imagine a basket of eggs for which it is not known how many there are. Too lazy to count all of them one may know that if you take out three at a time, it ends up with two left-over. If one takes out five at a time, three are left-over, and by taking out seven at a time, two are left-over. This is enough information to figure out the least number of eggs that are in the basket. Here we go.

The basis for finding a solution for an integer number X which satisfies the congruences of modulo definitions as explained below.
Suppose that m1, m2,..,mk are pairwise relatively prime positive integers, and a1, a2,..,ak a series of integers, congruences exist as follows:

xai (mod mi)   for i=1..k and have a unique solution:

M = m1·m2·..·mk   which is given by:

xa1M1y1 + a2M2y2 + .. + akMkyk (mod M)    with:

Mi = M/mi    and    yi ≡ 1/Mi (mod mi)      for i=1..k

The values   yi  can be found by applying the Extended Euclidean Algorithm.

Example 1
Please note that my default FIX 5 setting which can be replaced by your preferred number of decimals at line 178. An example are the following three congruences:
x2 (mod 3)
x3 (mod 5)
x2 (mod 7)

in which M=LCM(3,5,7)=105 and the value of x is to be determined. Example 2
Please note that my default FIX 5 setting which can be replaced by your preferred number of decimals at line 179. An example are the following three congruences:
x = 5 (mod 7)
x = 7 (mod 11)
x = 14 (mod 31)
x = 8 (mod 45)

in which M=LCM(7,11,31,45)=107415 and the value of x is to be determined. Program Listing
The listing of CRT is given below with functions A-E in User Mode. Registers, Labels and Flags 