How to resolve the algorithm Modular inverse step by step in the Modula-2 programming language

Published on 12 May 2024 09:40 PM
#Modula-2

How to resolve the algorithm Modular inverse step by step in the Modula-2 programming language

Table of Contents

Problem Statement

From Wikipedia: In modular arithmetic,   the modular multiplicative inverse of an integer   a   modulo   m   is an integer   x   such that Or in other words, such that: It can be shown that such an inverse exists   if and only if   a   and   m   are coprime,   but we will ignore this for this task.

Either by implementing the algorithm, by using a dedicated library or by using a built-in function in your language,   compute the modular inverse of   42 modulo 2017.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Modular inverse step by step in the Modula-2 programming language

Source code in the modula-2 programming language

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.

You may also check:How to resolve the algorithm Department numbers step by step in the Modula-2 programming language
You may also check:How to resolve the algorithm Fast Fourier transform step by step in the Stata programming language
You may also check:How to resolve the algorithm String matching step by step in the EasyLang programming language
You may also check:How to resolve the algorithm Create a file step by step in the Julia programming language
You may also check:How to resolve the algorithm Window management step by step in the PicoLisp programming language