Simplified Modulo Expressions
11-28-2019, 06:34 PM
Post: #1 Eddie W. Shore Senior Member Posts: 1,015 Joined: Dec 2013
Simplified Modulo Expressions
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!