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:
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
Disp “CHINESE REMAINDER”,”X=R MOD S”,”X=T MOD U”
Disp “NO SOLUTION”
x ≡ 3 mod 19
x ≡ 8 mod 11
Solution: [41, 209], 41 mod 209
x ≡ 4 mod 14
x ≡ 7 mod 17
Solution: [228, 238], 228 mod 238
Silverman, Joseph H. A Friendly Introduction to Number Theory Prentice Hall, Inc: Upper Saddle River, New Jersey 2001. ISBN 0-13-030954-0
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.