How to compute the remainder of a division $a/b$ to a modulus $M$, i.e. $a/b \pmod M$ 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.
 A: 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).
