Simplified Modulo Expressions

[Eddie W. Shore]

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/t...ified.html