What is the difference between the set Zn and Zn * In which set does each element have an additive inverse and/or multiplicative inverse?

Given two integers ‘a’ and ‘m‘, find modular multiplicative inverse of ‘a’ under modulo ‘m’.
The modular multiplicative inverse is an integer ‘x’ such that. 

a x ≅ 1 (mod m)

The value of x should be in { 1, 2, … m-1}, i.e., in the range of integer modulo m. ( Note that x cannot be 0 as a*0 mod m will never be 1 )
The multiplicative inverse of “a modulo m” exists if and only if a and m are relatively prime (i.e., if gcd(a, m) = 1).

Examples: 

Input: a = 3, m = 11 Output: 4 Since (4*3) mod 11 = 1, 4 is modulo inverse of 3(under 11). One might think, 15 also as a valid output as "(15*3) mod 11" is also 1, but 15 is not in range {1, 2, ... 10}, so not valid. Input: a = 10, m = 17 Output: 12 Since (10*12) mod 17 = 1, 12 is modulo inverse of 10(under 17).

Method 1 (Naive) 
A Naive method is to try all numbers from 1 to m. For every number x, check if (a*x)%m is 1. 

Below is the implementation of this method. 

C++

#include

using namespace std;

int modInverse(int a, int m)

{

    for (int x = 1; x < m; x++)

        if (((a%m) * (x%m)) % m == 1)

            return x;

}

int main()

{

    int a = 3, m = 11;

    cout << modInverse(a, m);

    return 0;

}

Java

import java.io.*;

class GFG {

    static int modInverse(int a, int m)

    {

        for (int x = 1; x < m; x++)

            if (((a%m) * (x%m)) % m == 1)

                return x;

        return 1;

    }

    public static void main(String args[])

    {

        int a = 3, m = 11;

        System.out.println(modInverse(a, m));

    }

}

Python3

def modInverse(a, m):

    for x in range(1, m):

        if (((a%m) * (x%m)) % m == 1):

            return x

    return -1

a = 3

m = 11

print(modInverse(a, m))

C#

using System;

class GFG {

    static int modInverse(int a, int m)

    {

        for (int x = 1; x < m; x++)

            if (((a%m) * (x%m)) % m == 1)

                return x;

        return 1;

    }

    public static void Main()

    {

        int a = 3, m = 11;

        Console.WriteLine(modInverse(a, m));

    }

}

PHP

<≅php

function modInverse( $a, $m)

{

    for ($x = 1; $x < $m; $x++)

        if ((($a%$m) * ($x%$m)) % $m == 1)

            return $x;

}

    $a = 3;

    $m = 11;

    echo modInverse($a, $m);

≅>

Javascript

Time Complexity: O(m)

Auxiliary Space: O(1)

Method 2 ( Works when m and a are coprime or gcd(a,m)=1 ) 
The idea is to use Extended Euclidean algorithms that takes two integers ‘a’ and ‘b’, finds their gcd and also find ‘x’ and ‘y’ such that 

ax + by = gcd(a, b)

To find multiplicative inverse of ‘a’ under ‘m’, we put b = m in above formula. Since we know that a and m are relatively prime, we can put value of gcd as 1.

ax + my = 1

If we take modulo m on both sides, we get

ax + my ≅ 1 (mod m)

We can remove the second term on left side as ‘my (mod m)’ would always be 0 for an integer y. 

ax ≅ 1 (mod m)

So the ‘x’ that we can find using Extended Euclid Algorithm is the multiplicative inverse of ‘a’

Below is the implementation of the above algorithm.  

C++

#include

using namespace std;

int gcdExtended(int a, int b, int* x, int* y);

void modInverse(int a, int m)

{

    int x, y;

    int g = gcdExtended(a, m, &x, &y);

    if (g != 1)

        cout << "Inverse doesn't exist";

    else

    {

        int res = (x % m + m) % m;

        cout << "Modular multiplicative inverse is " << res;

    }

}

int gcdExtended(int a, int b, int* x, int* y)

{

    if (a == 0)

    {

        *x = 0, *y = 1;

        return b;

    }

    int x1, y1;

    int gcd = gcdExtended(b % a, a, &x1, &y1);

    *x = y1 - (b / a) * x1;

    *y = x1;

    return gcd;

}

int main()

{

    int a = 3, m = 11;

    modInverse(a, m);

    return 0;

}

C

#include

int gcdExtended(int a, int b, int* x, int* y);

void modInverse(int a, int m)

{

    int x, y;

    int g = gcdExtended(a, m, &x, &y);

    if (g != 1)

        printf("Inverse doesn't exist");

    else

    {

        int res = (x % m + m) % m;

        printf("Modular multiplicative inverse is %d", res);

    }

}

int gcdExtended(int a, int b, int* x, int* y)

{

    if (a == 0)

    {

        *x = 0, *y = 1;

        return b;

    }

    int x1, y1;

    int gcd = gcdExtended(b % a, a, &x1, &y1);

    *x = y1 - (b / a) * x1;

    *y = x1;

    return gcd;

}

int main()

{

    int a = 3, m = 11;

    modInverse(a, m);

    return 0;

}

Java

public class GFG {

  public static int x;

  public static int y;

  static int gcdExtended(int a,int b){   

    if (a == 0){

      x = 0;

      y = 1;

      return b;

    }

    int gcd = gcdExtended(b % a, a);

    int x1 = x;

    int y1 = y;

    int tmp = b/a;

    x = y1 - tmp * x1;

    y = x1;

    return gcd;

  } 

  static void modInverse(int a,int m){

    int g = gcdExtended(a, m);

    if (g != 1){

      System.out.println("Inverse doesn't exist");

    }

    else

    {

      int res = (x % m + m) % m;

      System.out.println("Modular multiplicative inverse is " + res);       

    }

  }

  public static void main(String[] args) {

    int a = 3, m = 11;

    modInverse(a, m);

  }

}

Python3

x, y = 0, 1

def gcdExtended(a, b):

    global x, y

    if (a == 0):

        x = 0

        y = 1

        return b

    gcd = gcdExtended(b % a, a)

    x1 = x

    y1 = y

    x = y1 - (b // a) * x1

    y = x1

    return gcd

def modInverse(a, m):

    g = gcdExtended(a, m)

    if (g != 1):

        print("Inverse doesn't exist")

    else:

        res = (x % m + m) % m

        print("Modular multiplicative inverse is ", res)

a = 3

m = 11

modInverse(a, m)

C#

using System;

public class GFG

{

    public static int x, y;

    static int gcdExtended(int a, int b)

    {

        if (a == 0)

        {

            x = 0;

            y = 1;

            return b;

        }

        int gcd = gcdExtended(b % a, a);

        int x1 = x;

        int y1 = y;

        x = y1 - (b / a) * x1;

        y = x1;

        return gcd;

    }

    static void modInverse(int a, int m)

    {

        int g = gcdExtended(a, m);

        if (g != 1)

            Console.Write("Inverse doesn't exist");

        else

        {

            int res = (x % m + m) % m;

            Console.Write("Modular multiplicative inverse is " + res);

        }

    }

    public static void Main(string[] args)

    {

        int a = 3, m = 11;

        modInverse(a, m);

    }

}

PHP

<≅php

function modInverse($a, $m)

{

    $x = 0;

    $y = 0;

    $g = gcdExtended($a, $m, $x, $y);

    if ($g != 1)

        echo "Inverse doesn't exist";

    else

    {

        $res = ($x % $m + $m) % $m;

        echo "Modular multiplicative " .

                   "inverse is " . $res;

    }

}

function gcdExtended($a, $b, &$x, &$y)

{

    if ($a == 0)

    {

        $x = 0;

        $y = 1;

        return $b;

    }

    $x1;

    $y1;

    $gcd = gcdExtended($b%$a, $a, $x1, $y1);

    $x = $y1 - (int)($b/$a) * $x1;

    $y = $x1;

    return $gcd;

}

$a = 3;

$m = 11;

modInverse($a, $m);

≅>

Javascript

Output

Modular multiplicative inverse is 4

Time Complexity: O(log m)

Auxiliary Space: O(log m)   because of the internal recursion stack.

 Iterative Implementation: 

C++

#include

using namespace std;

int modInverse(int a, int m)

{

    int m0 = m;

    int y = 0, x = 1;

    if (m == 1)

        return 0;

    while (a > 1) {

        int q = a / m;

        int t = m;

        m = a % m, a = t;

        t = y;

        y = x - q * y;

        x = t;

    }

    if (x < 0)

        x += m0;

    return x;

}

int main()

{

    int a = 3, m = 11;

    cout << "Modular multiplicative inverse is "<< modInverse(a, m);

    return 0;

}

C

#include

int modInverse(int a, int m)

{

    int m0 = m;

    int y = 0, x = 1;

    if (m == 1)

        return 0;

    while (a > 1) {

        int q = a / m;

        int t = m;

        m = a % m, a = t;

        t = y;

        y = x - q * y;

        x = t;

    }

    if (x < 0)

        x += m0;

    return x;

}

int main()

{

    int a = 3, m = 11;

    printf("Modular multiplicative inverse is %d\n",

           modInverse(a, m));

    return 0;

}

Java

class GFG {

    static int modInverse(int a, int m)

    {

        int m0 = m;

        int y = 0, x = 1;

        if (m == 1)

            return 0;

        while (a > 1) {

            int q = a / m;

            int t = m;

            m = a % m;

            a = t;

            t = y;

            y = x - q * y;

            x = t;

        }

        if (x < 0)

            x += m0;

        return x;

    }

    public static void main(String args[])

    {

        int a = 3, m = 11;

        System.out.println("Modular multiplicative "

                           + "inverse is "

                           + modInverse(a, m));

    }

}

Python3

def modInverse(a, m):

    m0 = m

    y = 0

    x = 1

    if (m == 1):

        return 0

    while (a > 1):

        q = a // m

        t = m

        m = a % m

        a = t

        t = y

        y = x - q * y

        x = t

    if (x < 0):

        x = x + m0

    return x

a = 3

m = 11

print("Modular multiplicative inverse is",

      modInverse(a, m))

C#

using System;

class GFG {

    static int modInverse(int a, int m)

    {

        int m0 = m;

        int y = 0, x = 1;

        if (m == 1)

            return 0;

        while (a > 1) {

            int q = a / m;

            int t = m;

            m = a % m;

            a = t;

            t = y;

            y = x - q * y;

            x = t;

        }

        if (x < 0)

            x += m0;

        return x;

    }

    public static void Main()

    {

        int a = 3, m = 11;

        Console.WriteLine("Modular multiplicative "

                          + "inverse is "

                          + modInverse(a, m));

    }

}

PHP

<≅php

function modInverse($a, $m)

{

    $m0 = $m;

    $y = 0;

    $x = 1;

    if ($m == 1)

    return 0;

    while ($a > 1)

    {

        $q = (int) ($a / $m);

        $t = $m;

        $m = $a % $m;

        $a = $t;

        $t = $y;

        $y = $x - $q * $y;

        $x = $t;

    }

    if ($x < 0)

    $x += $m0;

    return $x;

}

    $a = 3;

    $m = 11;

    echo "Modular multiplicative inverse is\n",

                            modInverse($a, $m);

≅>

Javascript

Output

Modular multiplicative inverse is 4

Time Complexity: O(log m)

Auxiliary Space: O(1)

  
Method 3 (Works when m is prime) 
If we know m is prime, then we can also use Fermats’s little theorem to find the inverse. 

am-1 ≅ 1 (mod m)

If we multiply both sides with a-1, we get 

a-1 ≅ a m-2 (mod m)

Below is the implementation of the above idea. 

C++

#include

using namespace std;

int gcd(int a, int b);

int power(int x, unsigned int y, unsigned int m);

void modInverse(int a, int m)

{

    int g = gcd(a, m);

    if (g != 1)

        cout << "Inverse doesn't exist";

    else

    {

        cout << "Modular multiplicative inverse is "

             << power(a, m - 2, m);

    }

}

int power(int x, unsigned int y, unsigned int m)

{

    if (y == 0)

        return 1;

    int p = power(x, y / 2, m) % m;

    p = (p * p) % m;

    return (y % 2 == 0) ? p : (x * p) % m;

}

int gcd(int a, int b)

{

    if (a == 0)

        return b;

    return gcd(b % a, a);

}

int main()

{

    int a = 3, m = 11;

    modInverse(a, m);

    return 0;

}

Java

import java.io.*;

class GFG {

    static void modInverse(int a, int m)

    {

        int g = gcd(a, m);

        if (g != 1)

            System.out.println("Inverse doesn't exist");

        else

        {

            System.out.println(

                "Modular multiplicative inverse is "

                + power(a, m - 2, m));

        }

    }

      static int power(int x, int y, int m)

    {

        if (y == 0)

            return 1;

        int p = power(x, y / 2, m) % m;

        p = (int)((p * (long)p) % m);

        if (y % 2 == 0)

            return p;

        else

            return (int)((x * (long)p) % m);

    }

    static int gcd(int a, int b)

    {

        if (a == 0)

            return b;

        return gcd(b % a, a);

    }

    public static void main(String args[])

    {

        int a = 3, m = 11;

        modInverse(a, m);

    }

}

Python3

def modInverse(a, m):

    g = gcd(a, m)

    if (g != 1):

        print("Inverse doesn't exist")

    else:

        print("Modular multiplicative inverse is ",

              power(a, m - 2, m))

def power(x, y, m):

    if (y == 0):

        return 1

    p = power(x, y // 2, m) % m

    p = (p * p) % m

    if(y % 2 == 0):

        return p

    else:

        return ((x * p) % m)

def gcd(a, b):

    if (a == 0):

        return b

    return gcd(b % a, a)

a = 3

m = 11

modInverse(a, m)

C#

using System;

class GFG {

    static void modInverse(int a, int m)

    {

        int g = gcd(a, m);

        if (g != 1)

            Console.Write("Inverse doesn't exist");

        else {

            Console.Write(

                "Modular multiplicative inverse is "

                + power(a, m - 2, m));

        }

    }

    static int power(int x, int y, int m)

    {

        if (y == 0)

            return 1;

        int p = power(x, y / 2, m) % m;

        p = (p * p) % m;

        if (y % 2 == 0)

            return p;

        else

            return (x * p) % m;

    }

    static int gcd(int a, int b)

    {

        if (a == 0)

            return b;

        return gcd(b % a, a);

    }

    public static void Main()

    {

        int a = 3, m = 11;

        modInverse(a, m);

    }

}

PHP

<≅php

function modInverse( $a, $m)

{

    $g = gcd($a, $m);

    if ($g != 1)

        echo "Inverse doesn't exist";

    else

    {

        echo "Modular multiplicative inverse is "

                        , power($a, $m - 2, $m);

    }

}

function power( $x, $y, $m)

{

    if ($y == 0)

        return 1;

    $p = power($x, $y / 2, $m) % $m;

    $p = ($p * $p) % $m;

    return ($y % 2 == 0)? $p : ($x * $p) % $m;

}

function gcd($a, $b)

{

    if ($a == 0)

        return $b;

    return gcd($b % $a, $a);

}

$a = 3;

$m = 11;

modInverse($a, $m);

≅>

Javascript

Output

Modular multiplicative inverse is 4

Time Complexity:O(log m)

Auxiliary Space: O(log m)    because of the internal recursion stack.

We have discussed three methods to find multiplicative inverse modulo m. 
1) Naive Method, O(m) 
2) Extended Euler’s GCD algorithm, O(Log m) [Works when a and m are coprime] 
3) Fermat’s Little theorem, O(Log m) [Works when ‘m’ is prime]

Applications: 
Computation of the modular multiplicative inverse is an essential step in RSA public-key encryption method.

References: 
https://en.wikipedia.org/wiki/Modular_multiplicative_inverse 
http://e-maxx.ru/algo/reverse_element
This article is contributed by Ankur. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

What is Zn * in number theory?

What is difference between multiplicative inverse and additive inverse?

What is Zn in modular arithmetic?