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

Downloads
PDF format of program CRT.
RAW/TXT format of program CRT (in zip file).

References
Mathematical article: Chinese Remainder Theorem by University of Colorado Denver.
Interactive math website: Chinese Remainder Theorem by Cut the Knot.

This program is copyright and is supplied without representation or warranty of any kind. The author assumes no responsibility and shall have no liability, consequential or otherwise, of any kind arising from the use of this program material or any part thereof

© 1999-2020 by Auke Hoekstra

 
Don`t copy text!