Solving modular linear equations

PROBLEM

Find solutions to the equations

MOD(A*X,N)=MOD(B,N)

IMPLEMENTATION

Unit: program

Parameters: an arbitrary integers A, B, a positive integer N

Output: program displays on the screen all solutions to the equations
MOD(A*X,N)=MOD(B,N)

Interface: functions EXEUCLID and MOD

/* Solving modular linear equations */
parse arg A B N
parse value EXEUCLID(A, N) with D X Y
if MOD(B, D) = 0
  then do
    X = MOD(X * (B / D), N)
    do I = 0 to D - 1
      say MOD(X + I * (N / D), N)
    end
  end
  else say "No solutions"
exit

CONNECTIONS

Euclid's GCD (and LCM) algorithm
Extended Euclid's algorithms
CEILING, FLOOR, MOD

Literature

Cormen T. H., Leiserson Ch. E., Rivest R. L. Introduction to Algorithms

The MIT Press, Cambridge, 1990