Thursday, November 28, 2019

TI 84 Plus CE and HP Prime: Simplified Modulo Expressions

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.

Casio fx-CG50: Sparse Matrix Builder

Casio fx-CG50: Sparse Matrix Builder Introduction The programs can create a sparse matrix, a matrix where most of the entries have zero valu...