Modular multiplicative inverse from 1 to m-1

Here we calculate inverse modulo from 1 to m-1, and m must be prime number.

For every number i we calculate i^-1 . For this we can write,

                                                        

                             m mod i = m - (m / i) * i     ------------- (1)

In equation (1) taking modulo m both sides and we get,

                

                             m mod i = - (m / i) * i  mod m

Multiple both sides by i^-1 * (m mod i)^-1 and we get,

                   (m mod i) * i^-1 * (m mod i)^-1 ⩭  - (m / i) * i * i^-1 * (m mod i)^-1  mod m

                   i^-1  ⩭  - (m / i) * (m mod i)^-1  mod m

[ Notice that if we calculate,

                                             (-100) mod 6 = - 4 

if we mod any negative value we just make it positive than modulo it after modulo we get a answer then we make this answer negative than we get the answer, here  -100 it will be 100 then (100 mod 6) = 4 then 4 will be -4, this -4 will be our answer ]

#include<bits/stdc++.h>

using namespace std;

void mod_inverse(int m)

{

    int inv[m+1];

    inv[0] = inv[1] = 1;

    for(int i=2; i<m; i++)

        inv[i] = m - (m/i) * inv[m%i] % m;

    cout << "\nModuler Multiplicative Inverse From 1 to " << m-1 << " :: ";

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

        cout << inv[i] << " ";

cout << "\n";

}

int main()

{

    int m;

    cout << "Enter a prime number :: ";

    cin >> m;

mod_inverse(m);

    return 0;

}