**TI-84 Plus and HP Prime: Chinese Remainder Theorem**

**Introduction**

The Chinese Remainder Theorem deals with solving the following congruences:

x ≡ r₀ mod m₀

x ≡ r₁ mod m₁

x ≡ r₂ mod m₂

…

where m₀, m₁, m₂, etc are all relatively prime. Two integers are relatively prime when both integers have a GCD (greatest common divisor) is 1.

We are going to focus on the two congruent system:

(I)

x ≡ r mod s

x ≡ t mod u

where the solution is x mod s*u.

**HP Prime Function CAS.inchinrem**

To solve the Chinese Remainder Theorem, use the function inchinrem.

Syntax (reference (I) above):

Home/Programming Mode Syntax: CAS.inchinrem([r, s], [t, u]).

CAS Mode Syntax: inchinrem([r, s], [t, u])

The answer returned is x mod s*u in vector form [x, s*u].

Where to find inchinrem: [Toolbox], (CAS), 5. Integer, 7. Division, 3. Chinese Remainder

**TI-84 Plus Program CTR2**

“2018-11-18 EWS”

Disp “CHINESE REMAINDER”,”X=R MOD S”,”X=T MOD U”

Prompt R,S,T,U

If gcd(S,U)≠1

Then

Disp “NO SOLUTION”

Stop

T-R→W

U*fPart(abs(W)/U)→W

If T-R

U-W→W

0→Y

0→N

Repeat W=N

1+Y→Y

U*fPart(S*Y/U)→N

End

S*Y+R→X

S*U→M

Disp “SOLUTION:”,X,”MOD”,M

**Examples**

Example 1:

x ≡ 3 mod 19

x ≡ 8 mod 11

Solution: [41, 209], 41 mod 209

Example 2:

x ≡ 4 mod 14

x ≡ 7 mod 17

Solution: [228, 238], 228 mod 238

Source:

Silverman, Joseph H. *A Friendly Introduction to Number Theory *Prentice Hall, Inc: Upper Saddle River, New Jersey 2001. ISBN 0-13-030954-0

Happy Thanksgiving!

Eddie

All original content copyright, © 2011-2018. Edward Shore. Unauthorized use and/or unauthorized distribution for commercial purposes without express and written permission from the author is strictly prohibited. This blog entry may be distributed for noncommercial purposes, provided that full credit is given to the author. Please contact the author if you have questions.