# Modular inverse

Modular inverse
You are encouraged to solve this task according to the task description, using any language you may know.

From Wikipedia:

In modular arithmetic,   the modular multiplicative inverse of an integer   a   modulo   m   is an integer   x   such that

${\displaystyle a\,x\equiv 1{\pmod {m}}.}$

Or in other words, such that:

${\displaystyle \exists k\in \mathbb {Z} ,\qquad a\,x=1+k\,m}$

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.

## 8th

 \ return "extended gcd" of a and b; The result satisfies the equation:\     a*x + b*y = gcd(a,b): n:xgcd \ a b --  gcd x y  dup 0 n:= if    1 swap            \ -- a 1 0  else    tuck n:/mod    -rot recurse    tuck 4 roll    n:* n:neg n:+  then ; \ Return modular inverse of n modulo mod, or null if it doesn't exist (n and mod\ not coprime):: n:invmod \ n mod -- invmod  dup >r  n:xgcd rot 1 n:= not if    2drop null  else    drop dup 0 n:< if [email protected] n:+ then  then  rdrop ; 42 2017 n:invmod . cr bye
Output:
1969


 with Ada.Text_IO;use Ada.Text_IO;procedure modular_inverse is  -- inv_mod calculates the inverse of a mod n. We should have n>0 and, at the end, the contract is a*Result=1 mod n  -- If this is false then we raise an exception (don't forget the -gnata option when you compile   function inv_mod (a : Integer; n : Positive) return Integer with post=> (a * inv_mod'Result) mod n = 1 is     -- To calculate the inverse we do as if we would calculate the GCD with the Euclid extended algorithm     -- (but we just keep the coefficient on a)    function inverse (a, b, u, v : Integer) return Integer is     (if b=0 then u else inverse (b, a mod b, v, u-(v*a)/b));  begin    return inverse (a, n, 1, 0);  end inv_mod;begin   -- This will output -48 (which is correct)  Put_Line (inv_mod (42,2017)'img);  -- The further line will raise an exception since the GCD will not be 1  Put_Line (inv_mod (42,77)'img);  exception when others => Put_Line ("The inverse doesn't exist."); end modular_inverse;

## ALGOL 68

 BEGIN   PROC modular inverse = (INT a, m) INT :   BEGIN      PROC extended gcd = (INT x, y) []INT :CO   Algol 68 allows us to return three INTs in several ways.  A [3]INT   is used here but it could just as well be a STRUCT.CO      BEGIN	 INT v := 1, a := 1, u := 0, b := 0, g := x, w := y;	 WHILE w>0	 DO	    INT q := g % w, t := a - q * u;	    a := u; u := t;	    t := b - q * v;	    b := v; v := t;	    t := g - q * w;	    g := w; w := t	 OD;	 a PLUSAB (a < 0 | u | 0);	 (a, b, g)      END;      [] INT egcd = extended gcd (a, m);      (egcd[3] > 1 | 0 | egcd[1] MOD m)         END;   printf (($"42 ^ -1 (mod 2017) = ", g(0)$, modular inverse (42, 2017)))CO   Note that if ϕ(m) is known, then a^-1 = a^(ϕ(m)-1) mod m which   allows an alternative implementation in terms of modular   exponentiation but, in general, this requires the factorization of   m.  If m is prime the factorization is trivial and ϕ(m) = m-1.   2017 is prime which may, or may not, be ironic within the context   of the Rosetta Code conditions.COEND
Output:
42 ^ -1 (mod 2017) = 1969


## AutoHotkey

Translation of C.

MsgBox, % ModInv(42, 2017) ModInv(a, b) {	if (b = 1)		return 1	b0 := b, x0 := 0, x1 :=1	while (a > 1) {		q := a // b		, t  := b		, b  := Mod(a, b)		, a  := t		, t  := x0		, x0 := x1 - q * x0		, x1 := t	}	if (x1 < 0)		x1 += b0	return x1}
Output:
1969

## AWK

 # syntax: GAWK -f MODULAR_INVERSE.AWK# converted from CBEGIN {    printf("%s\n",mod_inv(42,2017))    exit(0)}function mod_inv(a,b,  b0,t,q,x0,x1) {    b0 = b    x0 = 0    x1 = 1    if (b == 1) {      return(1)    }    while (a > 1) {      q = int(a / b)      t = b      b = int(a % b)      a = t      t = x0      x0 = x1 - q * x0      x1 = t    }    if (x1 < 0) {      x1 += b0    }    return(x1)}
Output:
1969


## Batch File

Based from C's second implementation

Translation of: Perl
@echo offsetlocal enabledelayedexpansion	%== Calls the "function" ==%call :ModInv 42 2017 resultecho !result!call :ModInv 40 1 resultecho !result!call :ModInv 52 -217 resultecho !result!call :ModInv -486 217 resultecho !result!call :ModInv 40 2018 resultecho !result!pause>nulexit /b 0 	%== The "function" ==%:ModInv	set a=%1	set b=%2 	if !b! lss 0 (set /a b=-b)	if !a! lss 0 (set /a a=b - ^(-a %% b^)) 	set t=0&set nt=1&set r=!b!&set /a nr=a%%b 	:while_loop	if !nr! neq 0 (		set /a q=r/nr		set /a tmp=nt		set /a nt=t - ^(q*nt^)		set /a t=tmp 		set /a tmp=nr		set /a nr=r - ^(q*nr^)		set /a r=tmp		goto while_loop	) 	if !r! gtr 1 (set %3=-1&goto :EOF)	if !t! lss 0 set /a t+=b	set %3=!t!	goto :EOF
Output:
1969
0
96
121
-1

## Bracmat

Translation of: Julia
( ( mod-inv  =   a b b0 x0 x1 q    .   !arg:(?a.?b)      & ( !b:1        |   (!b.0.1):(?b0.?x0.?x1)          &   whl            ' ( !a:>1              & div$(!a.!b):?q & (!b.mod$(!a.!b)):(?a.?b)              & (!x1+-1*!q*!x0.!x0):(?x0.?x1)              )          & (!x:>0|!x1+!b0)        )  )& out$(mod-inv$(42.2017))};

Output

1969

## C

#include <stdio.h> int mul_inv(int a, int b){	int b0 = b, t, q;	int x0 = 0, x1 = 1;	if (b == 1) return 1;	while (a > 1) {		q = a / b;		t = b, b = a % b, a = t;		t = x0, x0 = x1 - q * x0, x1 = t;	}	if (x1 < 0) x1 += b0;	return x1;} int main(void) {	printf("%d\n", mul_inv(42, 2017));	return 0;}

The above method has some problems. Most importantly, when given a pair (a,b) with no solution, it generates an FP exception. When given b=1, it returns 1 which is not a valid result mod 1. When given negative a or b the results are incorrect. The following generates results that should match Pari/GP for numbers in the int range.

Translation of: Perl
#include <stdio.h> int mul_inv(int a, int b){        int t, nt, r, nr, q, tmp;        if (b < 0) b = -b;        if (a < 0) a = b - (-a % b);        t = 0;  nt = 1;  r = b;  nr = a % b;        while (nr != 0) {          q = r/nr;          tmp = nt;  nt = t - q*nt;  t = tmp;          tmp = nr;  nr = r - q*nr;  r = tmp;        }        if (r > 1) return -1;  /* No inverse */        if (t < 0) t += b;        return t;}int main(void) {        printf("%d\n", mul_inv(42, 2017));        printf("%d\n", mul_inv(40, 1));        printf("%d\n", mul_inv(52, -217));  /* Pari semantics for negative modulus */        printf("%d\n", mul_inv(-486, 217));        printf("%d\n", mul_inv(40, 2018));        return 0;}
Output:
1969
0
96
121
-1


## C++

Translation of: C
#include <iostream> using namespace std; int mul_inv(int a, int b){	int b0 = b, t, q;	int x0 = 0, x1 = 1;	if (b == 1) return 1;	while (a > 1) {		q = a / b;		t = b, b = a % b, a = t;		t = x0, x0 = x1 - q * x0, x1 = t;	}	if (x1 < 0) x1 += b0;	return x1;} int main(void) {	cout<<mul_inv(42, 2017)<<endl;	return 0;}

Recursive implementation

#include <iostream> short ObtainMultiplicativeInverse(int a, int b, int s0 = 1, int s1 = 0){    return b==0? s0: ObtainMultiplicativeInverse(b, a%b, s1, s0 - s1*(a/b));} int main(int argc, char* argv[]){    std::cout << ObtainMultiplicativeInverse(42, 2017) << std::endl;    return 0;}

## C#

public class Program{    static void Main()    {        System.Console.WriteLine(42.ModInverse(2017));    }} public static class IntExtensions{    public static int ModInverse(this int a, int m)    {        if (m == 1) return 0;        int m0 = m;        (int x, int y) = (1, 0);         while (a > 1) {            int q = a / m;            (a, m) = (m, a % m);            (x, y) = (y, x - q * y);        }        return x < 0 ? x + m0 : x;    }}

## Clojure

(ns test-p.core  (:require [clojure.math.numeric-tower :as math])) (defn extended-gcd  "The extended Euclidean algorithm--using Clojure code from RosettaCode for Extended Eucliean  (see http://en.wikipedia.orwiki/Extended_Euclidean_algorithm)  Returns a list containing the GCD and the Bézout coefficients  corresponding to the inputs with the result: gcd followed by bezout coefficients "  [a b]  (cond (zero? a) [(math/abs b) 0 1]        (zero? b) [(math/abs a) 1 0]        :else (loop [s 0                     s0 1                     t 1                     t0 0                     r (math/abs b)                     r0 (math/abs a)]                (if (zero? r)                  [r0 s0 t0]                  (let [q (quot r0 r)]                    (recur (- s0 (* q s)) s                           (- t0 (* q t)) t                           (- r0 (* q r)) r)))))) (defn mul_inv  " Get inverse using extended gcd.  Extended GCD returns    gcd followed by bezout coefficients. We want the 1st coefficients   (i.e. second of extend-gcd result).  We compute mod base so result    is between 0..(base-1) "  [a b]  (let [b (if (neg? b) (- b) b)        a (if (neg? a) (- b (mod (- a) b)) a)        egcd (extended-gcd a b)]      (if (= (first egcd) 1)        (mod (second egcd) b)        (str "No inverse since gcd is: " (first egcd)))))  (println (mul_inv 42 2017))(println (mul_inv 40 1))(println (mul_inv 52 -217))(println (mul_inv -486 217))(println (mul_inv 40 2018))

Output:

1969
0
96
121
No inverse since gcd is: 2


## Common Lisp

 ;;;; Calculates the GCD of a and b based on the Extended Euclidean Algorithm. The function also returns;; the Bézout coefficients s and t, such that gcd(a, b) = as + bt.;;;; The algorithm is described on page http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Iterative_method_2;;(defun egcd (a b)  (do ((r (cons b a) (cons (- (cdr r) (* (car r) q)) (car r))) ; (r+1 r) i.e. the latest is first.       (s (cons 0 1) (cons (- (cdr s) (* (car s) q)) (car s))) ; (s+1 s)       (u (cons 1 0) (cons (- (cdr u) (* (car u) q)) (car u))) ; (t+1 t)       (q nil))      ((zerop (car r)) (values (cdr r) (cdr s) (cdr u)))       ; exit when r+1 = 0 and return r s t    (setq q (floor (/ (cdr r) (car r))))))                     ; inside loop; calculate the q ;;;; Calculates the inverse module for a = 1 (mod m). ;;;; Note: The inverse is only defined when a and m are coprimes, i.e. gcd(a, m) = 1.”;;(defun invmod (a m)  (multiple-value-bind (r s k) (egcd a m)    (unless (= 1 r) (error "invmod: Values ~a and ~a are not coprimes." a m))       s))
Output:
* (invmod 42 2017)

-48
* (mod -48 2017)

1969


## D

Translation of: C
T modInverse(T)(T a, T b) pure nothrow {    if (b == 1)        return 1;    T b0 = b,      x0 = 0,      x1 = 1;     while (a > 1) {        immutable q = a / b;        auto t = b;        b = a % b;        a = t;        t = x0;        x0 = x1 - q * x0;        x1 = t;    }    return (x1 < 0) ? (x1 + b0) : x1;} void main() {    import std.stdio;    writeln(modInverse(42, 2017));}
Output:
1969

## EchoLisp

 (lib 'math) ;; for egcd = extended gcd (define (mod-inv x m)    (define-values (g inv q) (egcd x m))    (unless (= 1 g) (error 'not-coprimes (list x m) ))    (if (< inv 0) (+ m inv) inv)) (mod-inv 42 2017)  → 1969(mod-inv 42 666)🔴 error: not-coprimes (42 666)

## Elixir

Translation of: Ruby
defmodule Modular do  def extended_gcd(a, b) do    {last_remainder, last_x} = extended_gcd(abs(a), abs(b), 1, 0, 0, 1)    {last_remainder, last_x * (if a < 0, do: -1, else: 1)}  end   defp extended_gcd(last_remainder, 0, last_x, _, _, _), do: {last_remainder, last_x}  defp extended_gcd(last_remainder, remainder, last_x, x, last_y, y) do    quotient   = div(last_remainder, remainder)    remainder2 = rem(last_remainder, remainder)    extended_gcd(remainder, remainder2, x, last_x - quotient*x, y, last_y - quotient*y)  end   def inverse(e, et) do      {g, x} = extended_gcd(e, et)      if g != 1, do: raise "The maths are broken!"      rem(x+et, et)    end  end IO.puts Modular.inverse(42,2017)
Output:
1969


## Phix

Translation of: C
function mul_inv(integer a, n)    if n<0 then n = -n end if    if a<0 then a = n - mod(-a,n) end if    integer t = 0,  nt = 1,            r = n,  nr = a;       while nr!=0 do        integer q = floor(r/nr)        {t, nt} = {nt, t-q*nt}        {r, nr} = {nr, r-q*nr}    end while    if r>1 then return "a is not invertible" end if    if t<0 then t += n end if    return tend function ?mul_inv(42,2017)?mul_inv(40, 1)?mul_inv(52, -217)  /* Pari semantics for negative modulus */?mul_inv(-486, 217)?mul_inv(40, 2018)
Output:
1969
0
96
121
"a is not invertible"


## PHP

Algorithm Implementation

<?phpfunction invmod($a,$n){        if ($n < 0)$n = -$n; if ($a < 0) $a =$n - (-$a %$n);	$t = 0;$nt = 1; $r =$n; $nr =$a % $n; while ($nr != 0) {		$quot= intval($r/$nr);$tmp = $nt;$nt = $t -$quot*$nt;$t = $tmp;$tmp = $nr;$nr = $r -$quot*$nr;$r = $tmp; } if ($r > 1) return -1;	if ($t < 0)$t += $n; return$t;}	printf("%d\n", invmod(42, 2017));?>
Output:
1969

## PicoLisp

Translation of: C
(de modinv (A B)   (let (B0 B  X0 0  X1 1  Q 0  T1 0)      (while (< 1 A)         (setq            Q (/ A B)            T1 B            B (% A B)            A T1            T1 X0            X0 (- X1 (* Q X0))            X1 T1 ) )      (if (lt0 X1) (+ X1 B0) X1) ) ) (println   (modinv 42 2017) ) (bye)

## PL/I

Translation of: REXX
*process source attributes xref or(!); /*-------------------------------------------------------------------- * 13.07.2015 Walter Pachl *-------------------------------------------------------------------*/ minv: Proc Options(main); Dcl (x,y) Bin Fixed(31); x=42; y=2017; Put Edit('modular inverse of',x,' by ',y,' ---> ',modinv(x,y))         (Skip,3(a,f(4))); modinv: Proc(a,b) Returns(Bin Fixed(31)); Dcl (a,b,ob,ox,d,t) Bin Fixed(31); ob=b; ox=0; d=1;  If b=1 Then; Else Do;   Do While(a>1);     q=a/b;     r=mod(a,b);     a=b;     b=r;     t=ox;     ox=d-q*ox;     d=t;     End;   End; If d<0 Then   d=d+ob; Return(d); End; End;
Output:
modular inverse of  42 by 2017 ---> 1969

## PowerShell

function invmod($a,$n){        if ([int]$n -lt 0) {$n = -$n} if ([int]$a -lt 0) {$a =$n - ((-$a) %$n)} 	$t = 0$nt = 1	$r =$n	$nr =$a % $n while ($nr -ne 0) {		$q = [Math]::truncate($r/$nr)$tmp = $nt$nt = $t -$q*$nt$t = $tmp$tmp = $nr$nr = $r -$q*$nr$r = $tmp } if ($r -gt 1) {return -1}	if ($t -lt 0) {$t += $n} return$t} invmod 42 2017
Output:
PS> .\INVMOD.PS1
1969
PS> 

## PureBasic

Using brute force.

EnableExplicitDeclare main()Declare.i mi(a.i, b.i) If OpenConsole("MODULAR-INVERSE")  main() : Input() : EndEndIf Macro ModularInverse(a, b)    PrintN(~"\tMODULAR-INVERSE(" + RSet(Str(a),5) + "," +          RSet(Str(b),5)+") = " +          RSet(Str(mi(a, b)),5))   EndMacro Procedure main()  ModularInverse(42, 2017)  ; = 1969  ModularInverse(40, 1)     ; = 0  ModularInverse(52, -217)  ; = 96  ModularInverse(-486, 217) ; = 121  ModularInverse(40, 2018)  ; = -1EndProcedure Procedure.i mi(a.i, b.i)  Define x.i = 1,         y.i = Int(Abs(b)),         r.i = 0    If y = 1 : ProcedureReturn 0 : EndIf    While x < y    r = (a * x) % b       If r = 1 Or (y + r) = 1      Break    EndIf    x + 1  Wend  If x > y - 1 : x = -1 : EndIf    ProcedureReturn x  EndProcedure
Output:
        MODULAR-INVERSE(   42, 2017) =  1969
MODULAR-INVERSE(   40,    1) =     0
MODULAR-INVERSE(   52, -217) =    96
MODULAR-INVERSE( -486,  217) =   121
MODULAR-INVERSE(   40, 2018) =    -1

## Python

### Iteration and error-handling

Implementation of this pseudocode with this.

>>> def extended_gcd(aa, bb):    lastremainder, remainder = abs(aa), abs(bb)    x, lastx, y, lasty = 0, 1, 1, 0    while remainder:        lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)        x, lastx = lastx - quotient*x, x        y, lasty = lasty - quotient*y, y    return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1) >>> def modinv(a, m):	g, x, y = extended_gcd(a, m)	if g != 1:		raise ValueError	return x % m >>> modinv(42, 2017)1969>>>

### Recursion and an option type

Or, using functional composition as an alternative to iterative mutation, and wrapping the resulting value in an option type, to allow for the expression of computations which establish the absence of a modular inverse:

from functools import (reduce)from itertools import (chain)  # modInv :: Int -> Int -> Maybe Intdef modInv(a):    return lambda m: (        lambda ig=gcdExt(a)(m): (            lambda i=ig[0]: (                Just(i + m if 0 > i else i) if 1 == ig[2] else (                    Nothing()                )            )        )()    )()  # gcdExt :: Int -> Int -> (Int, Int, Int)def gcdExt(x):    def go(a, b):        if 0 == b:            return (1, 0, a)        else:            (q, r) = divmod(a, b)            (s, t, g) = go(b, r)        return (t, s - q * t, g)    return lambda y: go(x, y)  #  TEST --------------------------------------------------- # Numbers between 2010 and 2015 which do yield modular inverses for 42: # main :: IO ()def main():    print (        mapMaybe(            lambda y: bindMay(modInv(42)(y))(                lambda mInv: Just((y, mInv))            )        )(            enumFromTo(2010)(2025)        )    ) # -> [(2011, 814), (2015, 48), (2017, 1969), (2021, 1203)]  # GENERIC ABSTRACTIONS ------------------------------------  # enumFromTo :: Int -> Int -> [Int]def enumFromTo(m):    return lambda n: list(range(m, 1 + n))  # bindMay (>>=) :: Maybe  a -> (a -> Maybe b) -> Maybe bdef bindMay(m):    return lambda mf: (        m if m.get('Nothing') else mf(m.get('Just'))    )  # Just :: a -> Maybe adef Just(x):    return {'type': 'Maybe', 'Nothing': False, 'Just': x}  # mapMaybe :: (a -> Maybe b) -> [a] -> [b]def mapMaybe(mf):    return lambda xs: reduce(        lambda a, x: maybe(a)(lambda j: a + [j])(mf(x)),        xs,        []    )  # maybe :: b -> (a -> b) -> Maybe a -> bdef maybe(v):    return lambda f: lambda m: v if m.get('Nothing') else (        f(m.get('Just'))    )  # Nothing :: Maybe adef Nothing():    return {'type': 'Maybe', 'Nothing': True}  # MAIN ---main()
Output:
[(2011, 814), (2015, 48), (2017, 1969), (2021, 1203)]

## Racket

 (require math)(modular-inverse 42 2017)
Output:
 1969

/*REXX program calculates and displays the  modular inverse  of an integer  X  modulo Y.*/parse arg x y .                                  /*obtain two integers from the C.L.    */if x=='' | x==","  then x=   42                  /*Not specified?  Then use the default.*/if y=='' | y==","  then y= 2017                  /* "      "         "   "   "     "    */say  'modular inverse of '      x       " by "       y        ' ───► '         modInv(x,y)exit                                             /*stick a fork in it,  we're all done. *//*──────────────────────────────────────────────────────────────────────────────────────*/modInv: parse arg a,b 1 ob;     z=0              /*B & OB are obtained from the 2nd arg.*/        $=1 if b\=1 then do while a>1 parse value a/b a//b b z with q b a t z=$ - q*z;              $=trunc(t) end /*while*/ if$<0  then $=$+ob        return $ output when using the default inputs of: 42 2017 modular inverse of 42 by 2017 ───► 1969  ## Ring  see "42 %! 2017 = " + multInv(42, 2017) + nl func multInv a,b b0 = b x0 = 0 multInv = 1 if b = 1 return 0 ok while a > 1 q = floor(a / b) t = b b = a % b a = t t = x0 x0 = multInv - q * x0 multInv = t end if multInv < 0 multInv = multInv + b0 ok return multInv  Output: 42 %! 2017 = 1969  ## Ruby #based on pseudo code from http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Iterative_method_2 and from translating the python implementation.def extended_gcd(a, b) last_remainder, remainder = a.abs, b.abs x, last_x, y, last_y = 0, 1, 1, 0 while remainder != 0 last_remainder, (quotient, remainder) = remainder, last_remainder.divmod(remainder) x, last_x = last_x - quotient*x, x y, last_y = last_y - quotient*y, y end return last_remainder, last_x * (a < 0 ? -1 : 1)end def invmod(e, et) g, x = extended_gcd(e, et) if g != 1 raise 'The maths are broken!' end x % etend  > invmod(42,2017) => 1969 Simplified equivalent implementation  def modinv(a, m) # compute a^-1 mod m if possible raise "NO INVERSE - #{a} and #{m} not coprime" unless a.gcd(m) == 1 return m if m == 1 m0, inv, x0 = m, 1, 0 while a > 1 inv -= (a / m) * x0 a, m = m, a % m inv, x0 = x0, inv end inv += m0 if inv < 0 invend  > modinv(42,2017) => 1969  ## Run BASIC print multInv(42, 2017)end function multInv(a,b) b0 = b multInv = 1 if b = 1 then goto [endFun] while a > 1 q = a / b t = b b = a mod b a = t t = x0 x0 = multInv - q * x0 multInv = int(t) wend if multInv < 0 then multInv = multInv + b0[endFun]end function Output: 1969  ## Rust fn mod_inv(a: isize, module: isize) -> isize { let mut mn = (module, a); let mut xy = (0, 1); while mn.1 != 0 { xy = (xy.1, xy.0 - (mn.0 / mn.1) * xy.1); mn = (mn.1, mn.0 % mn.1); } while xy.0 < 0 { xy.0 += module; } xy.0} fn main() { println!("{}", mod_inv(42, 2017))} Output: 1969  Alternative implementation  fn modinv(a0: isize, m0: isize) -> isize { if m0 == 1 { return 1 } let (mut a, mut m, mut x0, mut inv) = (a0, m0, 0, 1); while a > 1 { inv -= (a / m) * x0; a = a % m; std::mem::swap(&mut a, &mut m); std::mem::swap(&mut x0, &mut inv); } if inv < 0 { inv += m0 } inv} fn main() { println!("{}", modinv(42, 2017))} Output: 1969  ## Scala Based on the Handbook of Applied Cryptography, Chapter 2. See http://cacr.uwaterloo.ca/hac/ .  def gcdExt(u: Int, v: Int): (Int, Int, Int) = { @tailrec def aux(a: Int, b: Int, x: Int, y: Int, x1: Int, x2: Int, y1: Int, y2: Int): (Int, Int, Int) = { if(b == 0) (x, y, a) else { val (q, r) = (a / b, a % b) aux(b, r, x2 - q * x1, y2 - q * y1, x, x1, y, y1) } } aux(u, v, 1, 0, 0, 1, 1, 0)} def modInv(a: Int, m: Int): Option[Int] = { val (i, j, g) = gcdExt(a, m) if (g == 1) Option(if (i < 0) i + m else i) else Option.empty} Translated from C++ (on this page)  def modInv(a: Int, m: Int, x:Int = 1, y:Int = 0) : Int = if (m == 0) x else modInv(m, a%m, y, x - y*(a/m))  Output: scala> modInv(2,4) res1: Option[Int] = None scala> modInv(42, 2017) res2: Option[Int] = Some(1976)  ## Seed7 The library bigint.s7i defines the bigInteger function modInverse. It returns the modular multiplicative inverse of a modulo b when a and b are coprime (gcd(a, b) = 1). If a and b are not coprime (gcd(a, b) <> 1) the exception RANGE_ERROR is raised. const func bigInteger: modInverse (in var bigInteger: a, in var bigInteger: b) is func result var bigInteger: modularInverse is 0_; local var bigInteger: b_bak is 0_; var bigInteger: x is 0_; var bigInteger: y is 1_; var bigInteger: lastx is 1_; var bigInteger: lasty is 0_; var bigInteger: temp is 0_; var bigInteger: quotient is 0_; begin if b < 0_ then raise RANGE_ERROR; end if; if a < 0_ and b <> 0_ then a := a mod b; end if; b_bak := b; while b <> 0_ do temp := b; quotient := a div b; b := a rem b; a := temp; temp := x; x := lastx - quotient * x; lastx := temp; temp := y; y := lasty - quotient * y; lasty := temp; end while; if a = 1_ then modularInverse := lastx; if modularInverse < 0_ then modularInverse +:= b_bak; end if; else raise RANGE_ERROR; end if; end func; Original source: [1] ## Sidef Built-in: say 42.modinv(2017) Algorithm implementation: func invmod(a, n) { var (t, nt, r, nr) = (0, 1, n, a % n) while (nr != 0) { var quot = int((r - (r % nr)) / nr); (nt, t) = (t - quot*nt, nt); (nr, r) = (r - quot*nr, nr); } r > 1 && return() t < 0 && (t += n) t} say invmod(42, 2017) Output: 1969  ## Tcl Translation of: Haskell proc gcdExt {a b} { if {$b == 0} {	return [list 1 0 $a] } set q [expr {$a / $b}] set r [expr {$a % $b}] lassign [gcdExt$b $r] s t g return [list$t [expr {$s -$q*$t}]$g]}proc modInv {a m} {    lassign [gcdExt $a$m] i -> g    if {$g != 1} { return -code error "no inverse exists of$a %! $m" } while {$i < 0} {incr i $m} return$i}

Demonstrating

puts "42 %! 2017 = [modInv 42 2017]"catch {    puts "2 %! 4 = [modInv 2 4]"} msg; puts \$msg
Output:
42 %! 2017 = 1969
no inverse exists of 2 %! 4


## tsql

;WITH Iterate(N,A,B,X0,X1)	AS (		SELECT 			1			,CASE WHEN @a < 0 THEN @b-(-@a % @b) ELSE @a END			,CASE WHEN @b < 0 THEN -@b ELSE @b END			,0			,1		UNION ALL		SELECT 			N+1			,B			,A%B			,X1-((A/B)*X0)			,X0		FROM Iterate		WHERE A != 1 AND B != 0	),	ModularInverse(Result)	AS (		SELECT			-1			FROM Iterate			WHERE A != 1 AND B = 0		UNION ALL		SELECT			TOP(1)			CASE WHEN X1 < 0 THEN X1+@b ELSE X1 END AS Result			FROM Iterate			WHERE (SELECT COUNT(*) FROM Iterate WHERE A != 1 AND B = 0) = 0			ORDER BY N DESC	)	SELECT *	FROM ModularInverse

## uBasic/4tH

Translation of: C
Print FUNC(_MulInv(42, 2017))End _MulInv Param(2)  Local(5)   [email protected] = [email protected]  [email protected] = 0  [email protected] = 1   If [email protected] = 1 Then Return   Do While [email protected] > 1    e@ = [email protected] / [email protected]    [email protected] = [email protected]    [email protected] = [email protected] % [email protected]    [email protected] = [email protected]     [email protected] = [email protected]    [email protected] = [email protected] - [email protected] * [email protected]    [email protected] = [email protected]  Loop   If [email protected] < 0 Then [email protected] = [email protected] + [email protected]Return ([email protected])
Translation of: Perl
Print FUNC(_mul_inv(42, 2017))Print FUNC(_mul_inv(40, 1))Print FUNC(_mul_inv(52, -217))Print FUNC(_mul_inv(-486, 217))Print FUNC(_mul_inv(40, 2018)) End _mul_inv Param(2)  Local(6)   If ([email protected] < 0) [email protected] = [email protected]  If ([email protected] < 0) [email protected] = [email protected] - ([email protected] % [email protected])  [email protected] = 0 : [email protected] = 1 :  [email protected] = [email protected] :  [email protected] = [email protected] % [email protected]   Do Until ([email protected] = 0)    [email protected] = [email protected]/[email protected]    [email protected] = [email protected] :  [email protected] = [email protected] - [email protected]*[email protected] :  [email protected] = [email protected]    [email protected] = [email protected] :  [email protected] = [email protected] - [email protected]*[email protected] :  [email protected] = [email protected]  Loop   If ([email protected] > 1) Return (-1)  ' No inverse'  If ([email protected] < 0) [email protected] = [email protected] + [email protected]Return ([email protected])
Output:
1969
0
96
121
-1

0 OK, 0:156

## VBA

Translation of: Phix
 Private Function mul_inv(a As Long, n As Long) As Variant    If n < 0 Then n = -n    If a < 0 Then a = n - ((-a) Mod n)    Dim t As Long: t = 0    Dim nt As Long: nt = 1    Dim r As Long: r = n    Dim nr As Long: nr = a    Dim q As Long    Do While nr <> 0        q = r \ nr        tmp = t        t = nt        nt = tmp - q * nt        tmp = r        r = nr        nr = tmp - q * nr    Loop    If r > 1 Then        mul_inv = "a is not invertible"    Else        If t < 0 Then t = t + n        mul_inv = t    End IfEnd FunctionPublic Sub mi()    Debug.Print mul_inv(42, 2017)    Debug.Print mul_inv(40, 1)    Debug.Print mul_inv(52, -217) '/* Pari semantics for negative modulus */    Debug.Print mul_inv(-486, 217)    Debug.Print mul_inv(40, 2018)End Sub
Output:
 1969
0
96
121
a is not invertible

## XPL0

code IntOut=11, Text=12;int  X;def  A=42, M=2017;[for X:= 2 to M-1 do    if rem(A*X/M) = 1 then [IntOut(0, X);  exit];Text(0, "Does not exist");]
Output:
1969


## zkl

fcn gcdExt(a,b){   if(b==0) return(1,0,a);   q,r:=a.divr(b); s,t,g:=gcdExt(b,r); return(t,s-q*t,g);}fcn modInv(a,m){i,_,g:=gcdExt(a,m); if(g==1) {if(i<0)i+m} else Void}
modInv(2,4)  //-->Void