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

A blog is that is all about mathematics and calculators, two of my passions in life.

## Friday, January 17, 2014

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

Subscribe to:
Post Comments (Atom)

### Calculator Python: Lambda Functions

Calculator Python: Lambda Functions Introduction to Lambda Functions Lambda functions are a quick, one expression, one line, python function...

## No comments:

## Post a Comment