I suddenly came across these lines of code when looking at others' submissions: (M is a prime)

```
inv[1]=1;
for(i=2;i<N;i++)
inv[i]=(M-M/i)*inv[M%i]%M;
```

I tried to google it to understand the formula but ended up finding nothing. So could anyone give me the proof for this?

Thanks a lot <3 <3.

I wasn't aware of this until your post. Fyi the precedence of % and * is equal. So you can read it as ((M-M/i)*inv[M%i])%M)

The

inverse$$$\mod M$$$ of $$$i$$$ is the number $$$j$$$ such that $$$ij=1 \mod M$$$. It is unique if we insist that it be in $$$[0,M)$$$. Denote it $$$i^{-1}$$$.Suppose we know all the inverses $$$1^{-1},2^{-1},\ldots,(i-1)^{-1}$$$. The division algorithm gives $$$M = qi+r$$$ with $$$0\leq r < i$$$ which means in particular that we know $$$r^{-1}$$$. Then to prove that $$$i^{-1}=(M-q)r^{-1}$$$, just multiply $$$i$$$ with it:

$$$i(M-q)r^{-1}=-iqr^{-1}=(r-M)r^{-1}=rr^{-1}=1$$$ (all equalities are modulo $$$M$$$).

From

M % i = M — (M / i) * i

We have

M % i = -(M / i) * i

Multiply 2 sides by (i^-1) * (M % i)^-1

(M % i) * (i^-1) * (M % i)^-1 = -(M / i) * i * (i^-1) * (M % i)^-1

Result

i^-1 = -(M / i) * (M % i)^-1

If you assume M = i*p+r, The above equation reduces to, inv[i] = (M-p)*inv[r] = -p*inv[r].

You can see easily that this (-p*inv[r]) is indeed inv[i] as i*(-p*inv[r]) = (-i*p)*inv[r] = (r-M)*inv[r] = 1!

Thank you guys very much <3 <3.

I had a related thought that is more understandable but a clunkier. For $$$a$$$ coprime to prime $$$p$$$, $$$a^1, a^2, \dots, a^{k-1} \pmod p$$$ is a sequence of all distinct numbers between 1 and $$$p-1$$$ (exercise: prove this).

Assume $$$p$$$ is an odd prime so we can let $$$a=2$$$. Then we can compute $$$a^1, a^2, \dots, a^{p-1} \pmod p$$$ and store in two arrays, one mapping $$$k \to a^k$$$ and the other $$$a^k \to k$$$ (all values are $$$<p$$$). Then the inverse of $$$a^k$$$ is then $$$a^{p-1-k}$$$. To find $$$x^{-1}$$$, we lookup its exponent $$$k$$$, compute new exponent $$$p-1-k$$$, then lookup $$$a^{p-1-k}$$$.

This is wrong. Consider $$$p=7,a=2$$$, the sequence will be $$$2,4,1,2,4,1$$$.

ok you are right the period is actually defined by the Carmichael function. I confused for $$$a,2a,\dots,(p-1)a$$$ which I think is distinct

https://math.stackexchange.com/questions/124408/finding-a-primitive-root-of-a-prime-number [](https://math.stackexchange.com/questions/124408/finding-a-primitive-root-of-a-prime-number)

The $$$a$$$ such that $$$a,a^2,\ldots$$$ generate all of $$$(\mathbb{Z}/(p\mathbb{Z}))^\times$$$ are called primitive roots. As an example, 3 is a primitive root for 7: $$$3,3^2,3^3,\ldots$$$ = $$$3,2,6,4,5,1,\ldots \mod 7$$$. It looks like there isn't an efficient algorithm $$$O(p)$$$ to identify a primitive root of a prime, so your algorithm while correct, wouldn't be faster than the above.