PROGRAM MOD_INV

!$INTEGER

PROCEDURE MUL_INV(A,B->T)
  LOCAL NT,R,NR,Q,TMP
  IF B<0 THEN B=-B
  IF A<0 THEN A=B-(-A MOD B)
  T=0  NT=1  R=B  NR=A MOD B
  WHILE NR<>0 DO
      Q=R DIV NR
      TMP=NT  NT=T-Q*NT  T=TMP
      TMP=NR  NR=R-Q*NR  R=TMP
  END WHILE
  IF (R>1) THEN T=-1 EXIT PROCEDURE  ! NO INVERSE
  IF (T<0) THEN T+=B
END PROCEDURE


BEGIN
     MUL_INV(42,2017->T) PRINT(T)
     MUL_INV(40,1->T) PRINT(T)
     MUL_INV(52,-217->T) PRINT(T)    ! pari semantics for negative modulus
     MUL_INV(-486,217->T)  PRINT(T)
     MUL_INV(40,2018->T) PRINT(T)
END PROGRAM