TI 84 Plus CE and HP Prime: Simplified Modulo Expressions
I hope you are having a great, at least sane Thanksgiving. It's Turkey Day (or the vegan equivalent of turkey day) in the United States. Disclosure: I'm not vegan.
Introduction
Let A, B, and M be positive integers where:
A ≡ B mod M
Let A = a * c (A = a when c = 1)
B = b * c (B = b when c = 1)
M = m
A "cancellation" theorem states that if:
a * c ≡ b * c mod m and gcd(c,m) = 1, then
a ≡ b mod c
Also, if a * c ≡ b * c mod m with gcd(c,m) = d, then
a ≡ b mod (m/d)
The program SIMPMOD uses the second theorem to find equivalent congruence for A ≡ B mod M. The user inputs B and M, A and equivalent congruence will be calculated.
TI-84 Plus CE Program: SIMPMOD
Firmware version 5.3 or greater is required because of the toString command. For earlier versions, you will have edit the last few lines.
"2019-10-27 EWS"
"84+ CE 5.3"
ClrHome
Disp "A = B MOD M"
Disp "A>0, B>0, M>0"
Input "B? ",B
Input "M? ",M
remainder(B,M)→A
Disp "A= ",A
iPart(√(B))→S
{1,B}→L_1
For(K,2,S)
B/K→T
If fPart(T)=0
augment(L_1,{K,T})→L_1
End
dim(L_1)→D
For(K,1,D)
L_1(K)→C
If fPart(A/C)=0
Then
A/C→R
B/C→S
M/gcm(M,C)→T
toString(R)+" = "+toString(S)+" MOD "+toString(T)→Str1
Disp Str1
End
End
Disp "DONE"
L_1 is the L1 list variable, [2nd] [ 1 ]
HP Prime Program: SIMPMOD
CHAR(8801) or CHAR(#2261h) is the congruence symbol, ≡
EXPORT SIMPMOD()
BEGIN
// 2019-10-27 EWS
// A ≡ B MOD M
LOCAL B,M;
LOCAL A,R,S,T,K,l1,l2,D;
INPUT({B,M},
"A "+CHAR(8801)+" B MOD M",
{"B?","M?"});
A:=B MOD M;
PRINT();
l1:=CAS.idivis(B);
l2:=SIZE(l1);
D:=l2(1);
FOR K FROM 1 TO D DO
C:=l1(K);
IF FP(A/C)==0 THEN
R:=A/C;
S:=B/C;
T:=M/CAS.gcd(M,C);
PRINT(R+" "+CHAR(8801)+" "+
S+" MOD "+T);
END;
END;
PRINT("DONE");
END;
Examples
Example 1
20 ≡ 500 MOD 30
Inputs: B = 500, M = 30
20 ≡ 500 MOD 30
10 ≡ 250 MOD 15
5 ≡ 125 MOD 15
4 ≡ 100 MOD 6
2 ≡ 50 MOD 3
1 ≡ 25 MOD 3
Example 2
4 ≡ 364 MOD 60
Input: B = 364, M = 60
4 ≡ 364 MOD 60
2 ≡ 182 MOD 30
1 ≡ 91 MOD 15
Example 3
28 ≡ 3528 MOD 100
Input: B = 3528, M = 100
28 ≡ 3528 MOD 100
14 ≡ 1764 MOD 50
7 ≡ 882 MOD 25
4 ≡ 504 MOD 100
2 ≡ 252 MOD 50
1 ≡ 126 MOD 25
Source:
Dudley, Underwood. Elementary Number Theory 2nd Edition. Dover Publications, Inc: Mineola, NY 1978 ISBN 978-0-486-46931-7 (2008 reprint)
Happy Thanksgiving!
Eddie
All original content copyright, © 2011-2019. 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.
I hope you are having a great, at least sane Thanksgiving. It's Turkey Day (or the vegan equivalent of turkey day) in the United States. Disclosure: I'm not vegan.
Introduction
Let A, B, and M be positive integers where:
A ≡ B mod M
Let A = a * c (A = a when c = 1)
B = b * c (B = b when c = 1)
M = m
A "cancellation" theorem states that if:
a * c ≡ b * c mod m and gcd(c,m) = 1, then
a ≡ b mod c
Also, if a * c ≡ b * c mod m with gcd(c,m) = d, then
a ≡ b mod (m/d)
The program SIMPMOD uses the second theorem to find equivalent congruence for A ≡ B mod M. The user inputs B and M, A and equivalent congruence will be calculated.
TI-84 Plus CE Program: SIMPMOD
Firmware version 5.3 or greater is required because of the toString command. For earlier versions, you will have edit the last few lines.
"2019-10-27 EWS"
"84+ CE 5.3"
ClrHome
Disp "A = B MOD M"
Disp "A>0, B>0, M>0"
Input "B? ",B
Input "M? ",M
remainder(B,M)→A
Disp "A= ",A
iPart(√(B))→S
{1,B}→L_1
For(K,2,S)
B/K→T
If fPart(T)=0
augment(L_1,{K,T})→L_1
End
dim(L_1)→D
For(K,1,D)
L_1(K)→C
If fPart(A/C)=0
Then
A/C→R
B/C→S
M/gcm(M,C)→T
toString(R)+" = "+toString(S)+" MOD "+toString(T)→Str1
Disp Str1
End
End
Disp "DONE"
L_1 is the L1 list variable, [2nd] [ 1 ]
HP Prime Program: SIMPMOD
CHAR(8801) or CHAR(#2261h) is the congruence symbol, ≡
EXPORT SIMPMOD()
BEGIN
// 2019-10-27 EWS
// A ≡ B MOD M
LOCAL B,M;
LOCAL A,R,S,T,K,l1,l2,D;
INPUT({B,M},
"A "+CHAR(8801)+" B MOD M",
{"B?","M?"});
A:=B MOD M;
PRINT();
l1:=CAS.idivis(B);
l2:=SIZE(l1);
D:=l2(1);
FOR K FROM 1 TO D DO
C:=l1(K);
IF FP(A/C)==0 THEN
R:=A/C;
S:=B/C;
T:=M/CAS.gcd(M,C);
PRINT(R+" "+CHAR(8801)+" "+
S+" MOD "+T);
END;
END;
PRINT("DONE");
END;
Examples
Example 1
20 ≡ 500 MOD 30
Inputs: B = 500, M = 30
20 ≡ 500 MOD 30
10 ≡ 250 MOD 15
5 ≡ 125 MOD 15
4 ≡ 100 MOD 6
2 ≡ 50 MOD 3
1 ≡ 25 MOD 3
Example 2
4 ≡ 364 MOD 60
Input: B = 364, M = 60
4 ≡ 364 MOD 60
2 ≡ 182 MOD 30
1 ≡ 91 MOD 15
Example 3
28 ≡ 3528 MOD 100
Input: B = 3528, M = 100
28 ≡ 3528 MOD 100
14 ≡ 1764 MOD 50
7 ≡ 882 MOD 25
4 ≡ 504 MOD 100
2 ≡ 252 MOD 50
1 ≡ 126 MOD 25
Source:
Dudley, Underwood. Elementary Number Theory 2nd Edition. Dover Publications, Inc: Mineola, NY 1978 ISBN 978-0-486-46931-7 (2008 reprint)
Happy Thanksgiving!
Eddie
All original content copyright, © 2011-2019. 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.
