+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: HP Prime Software Library (/forum-15.html)
+--- Thread: Simplified Modulo Expressions (/thread-14066.html)
Simplified Modulo Expressions - Eddie W. Shore - 11-28-2019 06:34 PM
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.
HP Prime Program: SIMPMOD
CHAR(8801) or CHAR(#2261h) is the congruence symbol, ≡
Code:
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!
Blog link: http://edspi31415.blogspot.com/2019/11/ti-84-plus-ce-and-hp-prime-simplified.html