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