Thursday, November 22, 2018

TI-84 Plus and HP Prime: Chinese Remainder Theorem

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<0 font="">
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.