### Libraion's blog

By Libraion, history, 6 weeks ago, ,

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.

• +29

 » 6 weeks ago, # | ← Rev. 3 →   +20 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$).
 » 6 weeks ago, # |   +8 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
 » 6 weeks ago, # | ← Rev. 3 →   +5 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!
 » 6 weeks ago, # |   +5 Thank you guys very much <3 <3.
 » 6 weeks ago, # | ← Rev. 3 →   0 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 $•  » » 6 weeks ago, # ^ | +1 This is wrong. Consider$p=7,a=2$, the sequence will be$2,4,1,2,4,1$. •  » » » 6 weeks ago, # ^ | ← Rev. 2 → 0 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 •  » » » » 6 weeks ago, # ^ | +1 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.