2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ I don't think that OP is looking for $2/3 \pmod{10}$ to be $4 \equiv 2 \cdot 7 \pmod{10}$ (where $7$ is the multiplicative inverse of $3$ modulo $10$)... But I'm not sure what exactly OP is looking for. $\endgroup$ – Lord_Farin Jun 17 '13 at 8:44
  • $\begingroup$ Can Any body explain me with one example .. $\endgroup$ – user82800 Jun 19 '13 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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