Simplified Modulo Expressions - Printable Version +- 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