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.
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.