0
$\begingroup$

Please forgive my cursory knowledge of modular arithmetic. My question is straightforward: is there a property of modular arithmetic that simplifies $\frac{a}{b}\mod n$?

I attempted using the fact that $a\cdot b\mod n \equiv ((a\mod n)\cdot(b\mod n))\mod n$ but found that $\frac{a\cdot n}{n} \mod n \equiv a \mod n$ does not hold.

Thank you. :)

$\endgroup$

closed as unclear what you're asking by user99914, José Carlos Santos, Shailesh, Taroccoesbrocco, Parcly Taxel Jul 22 '18 at 5:04

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ Is the / intended to be interpreted as division? You'll run into problems then in most scenarios and even run into problems defining it properly if you want to be strict. You can avoid the issue by instead talking about $a\cdot b^{-1}\pmod{n}$ but you'll find that $b^{-1}$ only exists if $\gcd(b,n)=1$. $\endgroup$ – JMoravitz Jul 21 '18 at 19:26
  • $\begingroup$ I often get very cautious and nervous when I see the divison symbol in contexts that only apply to $\mathbb{Z}$ (or non-fields in general). $\endgroup$ – JuliusL33t Jul 21 '18 at 19:32
  • $\begingroup$ I don't know. It's like a razor sharp chainsaw. $\frac 35 \equiv 11\mod 26$ can be a very useful tool in the right hands. Just make sure they are the right hands. $\endgroup$ – fleablood Jul 21 '18 at 20:14
  • $\begingroup$ This answer might be relevant to this question. Perhaps this question might even be a duplicate of Doing modular division when denominator and modulus not coprime $\endgroup$ – robjohn Jul 21 '18 at 21:49
2
$\begingroup$

It depends on what $\frac ab \mod n$ means.

Consider $\frac 84 \mod 6$. If you mean that to mean $q \mod 6$ where $q = \frac 84 = 2\in \mathbb Z$ then this is nothing more or less then $2 \mod 6$. No issue.

But if $q = \frac 13 \not \in \mathbb Z$ then $q\mod 6$... what do you mean?

You could, but probably don't, mean $[q]= \{q + k6|k \in \mathbb Z\}$ in many analysis/calculus/geometry context this make sense. In particular $\theta \mod 2\pi =\{\theta + 2k\pi\}$ has obvious practical applications.

But we almost never mean this in number theory. In number theory it is assume the we are working in the number system $\mathbb Z/n\mathbb Z = \{$ the set of complete residue systems $\mod n$. In which case $[x]$ when $x$ is not an integer simply makes no sense.

But In the case where $a*x \equiv 1 \mod n$ then $x$ acts practically as a multiplicative inverse to $a$ and we wish to say $x = a^{-1}\mod n$ (which means, by definition, that $ax \equiv 1 \mod n$. And we do right that as $x\equiv \frac 1a \mod n$.

Exampe $3*5 \equiv 1 \mod 14$ so $3 \equiv \frac 15 \mod 14$. It's important to realize that $\frac 15$ has NOTHING to do with the rational number $0.2$ but simply means ... the $x$ so that $x*5 \equiv 1 \mod 14$.

So in this case $\frac ab \mod n$ means the number $x$ so that $bx \equiv a \mod n$.....

.... if such a residue class exists

.... and if it is distinct.

There are two catches: 1) it might not exists; $\frac 32 \mod 6$ is is the integer $x$ so that $2x \equiv 3 \mod 6$. There is no solution to that. 2) there might be multiple solutions; $2*6\equiv 8*6\equiv 3 \mod 9$ so $\frac 36 \mod 9$ would be ill-defined.

But $\frac ab \mod n$ will have a distinct solution if and only if $b$ and $n$ are relatively prime. Then there will be a solution to $bx = 1 + kn$ and it is unique $\mod n$. And $\frac ab \equiv ax\mod n$ would be the unique value.

If $\gcd(b,n)=d\ne 1$ and $a$ is not a multiple of $d$ then there is no solution to $bx = a + kn$ and $d|b$ and $d|n$ but $d\not \mid a$. And if $a = md$ then $bx = a +kn$ will have a solution. But $b(x + \frac nd) =bx + \frac bd*n \equiv bx \equiv a \mod n$ is also a solution.

tl;dr

In number theory $\frac ab$ means the unique residue solution to $bx \equiv a \mod n$ which only exists if $\gcd(b, n) =1$ and which is equal to $ay\mod n$ where $y\equiv \frac 1b \mod n$ is the unique solution to $by \equiv 1 \mod n$.

$\endgroup$

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