Wednesday, January 15, 2014

HP Prime and HP 32S: Solving a Single Linear Congruence Equation

Happy Mid-January! Enjoying the first full moon of 2014?

Solving a Single Linear Congruence Equation

The program solves for x in the equation:

A * x = B mod N

Examples:

4 * x = 6 mod 7
A = 4, B = 6, N = 7
Solution: 5

5 * x = 3 mod 17
A = 5, B = 3, N = 17
Solution: 4

11 * x = 3 mod 16
A = 11, B = 3, N = 16
Solution: 9

HP Prime Program: CONG

EXPORT CONG( )
BEGIN
LOCAL A,B,N,I;
// 2014-01-15 EWS

INPUT({A,B,N}, "Ax = B mod N",
{"A","B","N"}, { }, {0, 0, 0} );

// safe guard if the user does not enter integers (optional line)
A:=IP(A); B:=IP(B); N:=IP(N);

// Algorithm
FOR I FROM 1 TO N-1 DO

IF FP((A*I-B)/N) == 0 THEN
MSGBOX("x ="+STRING(I));
RETURN I;
KILL;
END;

END;
RETURN "No Solution";
END;



HP 32S Program: CONG

Main Routine: Label C
Subroutines: D, E
No pre-storing any variables required. If there is no solution, an error is produced.
To Run: XEQ C

Program:
C01 LBL C
C02 INPUT A
C03 INPUT B
C04 INPUT N
C05 1
C06 STO I

D01 LBL D
D02 RCL I
D03 RCL × A
D04 RCL - B
D05 RCL ÷ N
D06 FP
D07 x ≠ 0?
D08 GTO E
D09 RCL I
D010 RTN

E01 LBL E
E02 1
E03 STO + I
E04 RCL I
E05 RCL N
E06 x > y?
E07 GTO D
E08 0
E09 1/x
E10 RTN


I am working on a program for the Chinese Remainder Theorem for 2 or 3 linear congruence equations, to be posted soon (hopefully).

Have a great day!

Eddie


This blog is property of Edward Shore. 2014

HHC 2025 Videos

  HHC 2025 Videos The talks from the HHC 2025 conference in Orlando, Florida are starting to be up on hpcalc’s YouTube page within th...