2
$\begingroup$

b and m are relatively prime (m is prime and $b \in \mathbb Z_m^* $). In truth, I would like to be able to get to the following point (it is a simplified example):

$\frac{ab \mod m}{b \mod m} = a \mod m$

Is it possible?


EDIT

My apologies. Thanks to Henning Malkholm I noticed I had used the wrong notation. I actually meant this:

$(ab \mod m)(b^{-1} \mod m) \equiv abb^{-1} \mod m$

$abb^{-1} \mod m \equiv (a \mod m)(bb^{-1} \mod m) \equiv (a \mod m)$

Is this valid? Again, I apologise if this seems too silly. I just don't feel secure enough to trust what I've found.

$\endgroup$
1
$\begingroup$

Let $a = 3, b = 4, m = 5$. Then $$ab \mod m = 12 \mod 5 = 2$$ $$b \mod m = 4$$ $$a \mod m = 3$$ Thus, you can see that your assumption is not true.

$\endgroup$
0
$\begingroup$

It is possible, but it is not necessarily true.

For example, take $m=11$, $a=4$, $b=3$. Then $ab\bmod m=1$, $a\bmod m=4$ and $b\bmod m=3$, yet $$ \frac{1}{3} \ne 4 $$


In order to extend division to modular arithmetic, what you need to do is find the modular inverse $b^{-1}$ of $b$, defined as the solution to $$ xb \equiv 1 \pmod m$$ which is $3$.

Then you can let "$a$ divided by $b$, modulo $m$" mean $ab^{-1}\pmod m$.

$\endgroup$
0
$\begingroup$

It depends what the symbols mean. Most commonly, the $\mod m$ notation is used together with the $\equiv$ symbol meaning congruence, as in $15\equiv1\mod 7$.

However, you can also note that congruence modulo $m$ is an equivalence relation, and define $\mathbb{Z}_m$ as the set of congruence classes modulo $m$. Algebraically speaking, you get a ring, and you might write $a\bmod m$ for the equivalence class of $a$ modulo $m$. In which case, it is true by definition that $(a\bmod m)(b\bmod m)=ab\bmod m$, and you can then get the identity you ask for by dividing by $b\bmod m$ – provided that this is an invertible element of $\mathbb{Z}_m$, which is equivalent to $\gcd(b,m)=1$.

Finally, and this is somewhat more low-brow, you can define $a\bmod m$ to be the particular member of the congruence class of $a$ which is in $\{0,1,\ldots,m-1\}$. In which case, your conjecture is dead wrong, as already indicated by others.

$\endgroup$

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.