HP Prime and TI-84+: Chinese Remainder Theorem - Solving Three Congruence Equations

Chinese Remainder Theorem - Sun Tzu (3rd to 5th century AD, China)

This program solves for X for the set of three linear congruence equations:
X = A mod B
X = C mod D
X = E mod F

B, D, and F are pairwise co-prime. B and D have a GCD of 1, B and F have a GCD of 1, and D and F have a GCD of 1.

A general solution takes the form
X = x1 * D * F * A + x2 * B * F * C + x3 * B * D * E

where (one method of solution)
D * F * x1 = 1 mod B
B * F * x2 = 1 mod D
B * D * x3 = 1 mod F

The program returns the solution X ± n*(B*D*F), X is the smallest positive integer and n is an integer.

Sources:
Chinese Remainder Theorem - General Information:
http://en.wikipedia.org/wiki/Chinese_remainder_theorem

Chinese Remainder Theorem - One method of solution:
http://youtu.be/3PkxN_r9up8

Solving a Linear Congruence Equation:
http://youtu.be/U9Eo6Bsvm4M

Examples:

X = 3 mod 8
X = 1 mod 9
X = 4 mod 11
X = 235 ± 792*n
{...-557, 235, 1027, 1819...}

X = 4 mod 5
X = 1 mod 7
X = 11 mod 16
X = 379 ± 560*n
{... -181, 379, 939, 1499...}

HP Prime Program CHINESE3
Output: [ X, B*D*F ]


// Declare subroutine
SUB1( );

// Main routine
EXPORT CHINESE3( )
BEGIN
LOCAL A,B,C,D,E,F,I,T:=0;

INPUT({A,B,C,D,E,F}, "X=A mod B=C mod D
=E mod F");

T := SUB1(D*F, B) * D * F * A + SUB1(B*F, D) * B * F * C
+ SUB1(B*D, F) * B * D * E;
T := T MOD (B*D*F);
RETURN [T, B*D*F];
END;

SUB1(X,Y)
BEGIN

FOR I FROM 1 TO X-1 DO
IF FP((X-1)/Y)==0 THEN
RETURN I;
END;
END;

RETURN "NO SOLUTION";

END;

TI-84+:
Main Routine: CHINESE3
Subroutine: CHIN3SUB
Output:
X
+/- N*
B*D*F


PROGRAM:CHINESE3
: ClrHome
: Disp "X=A MOD B"
: Disp "X=C MOD D"
: Disp "X=E MOD F"
: Prompt A,B,C,D,E,F
: 0 → T
: D * F → X : B → Y :prgmCHIN3SUB
: I * D * F * A → T
: B * F → X : D → Y : prgmCHIN3SUB
: T + I * B * F * C → T
: B * D → X : F → Y : prgmCHIN3SUB
: T +I * B * D * E → T
: remainder(T, B * D * F) → T
: Disp T
: Disp "+/- N*"
: Disp B * D * F

PROGRAM:CHIN3SUB (Subroutine)
: For(I, 1, X-1)
: fPart((X*I-1)/Y) → Z
: If Z=0
: Then
: Return
: End
: End
: Disp "NO SOLUTION"
: Stop