0
$\begingroup$

(a / b) % c = ((a % c) * (b^{-1} % c)) % c

How to calculate b^{-1}? I know it is not 1/b. Is there more than one way to calculate this?

$\endgroup$
0
0
$\begingroup$

Well, one generally uses the generalized Euclidean algorithm. If the gcd between $b$ and $c\geq 2$ is $1$, the algorithm yields $$sb+tc=1$$ for some integers $s,t$. Then the inverse of $b$ modulo $c$ is $s$, since $sb\equiv 1\mod c$.

$\endgroup$
0
$\begingroup$

The naive approach, of course, would be to simply go through the numbers $1,2,...,c-1$ and see which, upon being multiplied by $b$, gives you something congruent to $1$ mod $c$. This number will be, by definition, $b^{-1}$.

A better approach would be to use the Extended Euclidean Algorithm to find integers $x,y$ such that $$bx+cy=\gcd(b,c).$$ Assuming $b$ and $c$ are relatively prime, an inverse of $b$ modulo $c$ will be $x$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.