How to compute the remainder of a division $a/b$ to a modulus $M$, i.e. $a/b \pmod M$

Question

I am learning the usage of mod in programming to overcome the overflows.

I was able to deduce the following relation ships:

for example if I want to perform addition between $a$ and $b$ and the result must be modulo to M then i can perform the above operation as : $((a\%M)+(b\%M))\%M$ similarly for multiplication: $((a\%M)*(b\%M))\%M$

Right now I was stuck up with division can any body tell me how to perform the division between $a$ and $b$ & modulo the result by $M$.

Please suggest me some ways to get the solution.

What about the case if $M$ is prime and what about the case if $M$ is non-prime.

Answer 1

Think of the division $a/b$ modulo $m$ as multiplication by the inverse. Thus $a/b=ab^{-1}$ where $b^{-1}$ is the inverse of $b$. So, the problem is reduced to finding inverses modulo $m$. Now, the inverse of $b$ is that element $x$ such that $bx=1$ modulo $m$. It is not always possible to find such an $x$. In other words, not every element will have an inverse modulo $m$, and thus division is not always possible.

In general, if $\gcd(b,m)=1$, then an inverse of $b$ is guaranteed to exist. Finding it uses Bézout's identity: $\gcd(b,m)=xb+ym$ for suitable integers $x,y$, which can be found using the (extended) Euclidean algorithm. It follows immediately that $x$ is then the inverse of $b$ modulo $m$.

In particular, if $m=p$ if prime, then for all $1\le b<p$ it holds that $\gcd(b,m)=1$, and thus $b$ has an inverse. This is an important result that in fact implies that for prime $p$, the set of residue classes modulo $p$ form a field.

Remark: all of this falls under the general theory of groups (and fields).