Inverse (Editorial)

Since $n$ is a prime number, Fermat's Little Theorem gives

This equality can be rewritten as:

which means that the modular inverse of $i$ is j = i^{n-2}~mod~n.

The modular inverse can also be found using the Extended Euclidean Algorithm. Consider the problem of finding a number $x$ satisfying the congruence

This congruence is equivalent to the Diophantine equation:

Using the Extended Euclidean Algorithm, we can find one of its solutions (x_0, y_0). Then:

Consider this equality modulo $n$. We obtain:

Therefore, x_0 is the modular inverse of $a$ modulo $n$. If x_0 is negative, we need to add $n$ to it to obtain a number in the range [1, n - 1].

Thus, in both algorithms, finding the inverse for each number i~(1 \le i < n) takes O(log_2n) time. Therefore, the overall asymptotic complexity of the algorithm is O(nlog_2n).

Consider a solution with an asymptotic complexity of $O(n)$.

Theorem. If $inv[i]$ is the modular inverse of $i$ modulo $n$, then

Proof. It is known that n~mod~i = n - \left\lfloor \frac{n}{i} \right\rfloor \cdot i

Consider this equality modulo $n$: n~mod~i = - \left\lfloor \frac{n}{i} \right\rfloor \cdot i~mod~n

Multiply both sides of the equality by i^{-1} \cdot~(n~mod~i)^{-1}:

After simplification, we obtain:

According to the formula given in the theorem, the value of $inv[i]$ for each i~(1 \le i < n) can be computed in $O(1)$ time. Therefore, all modular inverses can be found in linear time $O(n)$.

Example

Let n = 5. Construct a table for computing the modular inverses:

Find the inverses using the formula from the theorem:

inv[1] = 1 (base case)

inv[2] = = (-2 \cdot inv[1])~mod~5 = -2~mod~5 = 3

inv[3] = = (-1 \cdot inv[2])~mod~5 = -3~mod~5 = 2

inv[4] = = (-1 \cdot inv[1])~mod~5 = -1~mod~5 = 4

Algorithm implementation

The function Pow returns the value x^n~mod~m.

long long Pow(long long x, long long n, long long m)
{
  if (n == 0) return 1;
  if (n % 2 == 0) return Pow((x * x) % m, n / 2, m);
  return (x * Pow(x, n - 1, m)) % m;
}

The main part of the program. Read the input value $n$.

scanf("%d",&n);

For each value i~(1 \le i < n) print the modular inverse modulo $n$ using the formula i^{n-2}~mod~n.

for(i = 1; i < n; i++)
  printf("%lld ",Pow(i,n-2,n));
printf("\n");

Algorithm implementation – extended Euclidean algorithm

#include <stdio.h> 

int n, i, d, x, y;

void gcdext(int a, int b, int &d, int &x, int &y)
{
  if (b == 0)
  {
    d = a; x = 1; y = 0;
    return;
  }

  gcdext(b, a % b, d, x, y);

  int s = y;
  y = x - (a / b) * y;
  x = s;
}

int main(void)
{
  scanf("%d", &n);
  for (i = 1; i < n; i++)
  {
    // i * x + n * y = 1
    gcdext(i, n, d, x, y);
    if (x < 0) x += n;
    printf("%d ", x);
  }
  printf("\n");
  return 0;
}

Algorithm implementation – O(n)

Declare an array $inv$ where we'll store the modular inverses:

#define MAX 1000001
int inv[MAX];

Read the input value $n$.

scanf("%d", &n);

Compute the inverses according to the formula from the theorem.

inv[1] = 1;
for (i = 2; i <= n; i++)
  inv[i] = n - 1LL * (n / i) * inv[n % i] % n;

Print the answer.

for (i = 1; i < n; i++)
  printf("%d ", inv[i]);

Java implementation

import java.util.*;
 
public class Main
{
  static long PowMod(long x, long n, long m)
  {
    if (n == 0) return 1;
    if (n % 2 == 0) return PowMod((x * x) % m, n / 2, m);
    return (x * PowMod(x, n - 1, m)) % m;
  }

  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    long n = con.nextLong();
    
    for(int i = 1; i < n; i++)
      System.out.print(PowMod(i,n-2,n) + " ");
    System.out.println();
    con.close();
  }
}

Java implementation – linear solution

import java.util.*;

public class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int inv[] = new int[n];
    
    inv[1] = 1;
    for (int i = 2; i < n; i++)
      inv[i] = (int) (n - 1L * (n / i) * inv[n % i] % n);
    
    for(int i = 1; i < n; i++)
      System.out.print(inv[i] + " ");
    System.out.println();
    con.close();
  }
}

Python implementation – linear solution

Read the input value $n$.

n = int(input())

Declare a list $inv$ to store the modular inverses.

inv = [0 for _ in range(n + 1)]

Compute the inverses according to the formula from the theorem.

inv[1] = 1;
for i in range(2,n):
  inv[i] = n - (n // i) * inv[n % i] % n;

Print the answer.

for i in range(1,n):
  print(inv[i], end= " ")