Solving a Single Congruence Equation

[Eddie W. Shore]

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

Code:


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;