MODULE ModularInverse;
  FROM InOut IMPORT WriteString, WriteInt, WriteLn;

  TYPE Data = RECORD x : INTEGER;
                     y : INTEGER
              END;

  VAR c  : INTEGER;
      ab : ARRAY [1..5] OF Data;

PROCEDURE mi(VAR a, b : INTEGER): INTEGER;
  VAR t, nt, r, nr, q, tmp : INTEGER;

BEGIN
  b := ABS(b);
  IF a < 0 THEN a := b - (-a MOD b) END;
  t := 0; nt := 1; r := b; nr := a MOD b;
  WHILE (nr # 0) DO
    q := r / nr;
    tmp := nt; nt := t - q * nt; t := tmp;
    tmp := nr; nr := r - q * nr; r := tmp;
  END;
  IF (r > 1) THEN RETURN -1 END;
  IF (t < 0) THEN RETURN t + b END;
  RETURN t;
END mi;

BEGIN
  ab[1].x := 42;   ab[1].y := 2017;
  ab[2].x := 40;   ab[2].y := 1;
  ab[3].x := 52;   ab[3].y := -217;
  ab[4].x := -486; ab[4].y := 217;
  ab[5].x := 40;   ab[5].y := 2018;
  WriteLn;
  WriteString("Modular inverse");
  WriteLn;
  FOR c := 1 TO 5 DO
    WriteInt(ab[c].x, 6); WriteString(", ");
    WriteInt(ab[c].y, 6); WriteString(" = ");
    WriteInt(mi(ab[c].x, ab[c].y),6);
    WriteLn;
  END;
END ModularInverse.