Intuition behind $\frac{a}{b}$ mod $(c)$

126 Views Asked by At

I read somewhere that $\frac{1}{3}$ mod $(11) = 4$ mod $(11)$. I tried adding $11$ to $\frac{1}{3}$ but that didn't seem to help in any way. I was simply unable to grasp the idea of what $\frac{a}{b}$ mod $(c)$ really means. Does it have a specific definition like $a^{\frac{b}{c}}$ which is $\sqrt[c]{a^{b}}$ ? I would appreciate any answers/hints to go from $\frac{1}{3}$ mod $(11)$ to $4$ mod $(11)$ and the intuition behind $\frac{a}{b}$ mod $(c)$.

1

There are 1 best solutions below

3
On BEST ANSWER

$\dfrac 13$ is an abuse of notations, what we are talking about is the inverse of $3$ noted $3^{-1}$ which is effectively $4$ due to the fact that:

$3\times 4\equiv 12\equiv (11+1)\equiv 1\pmod{11}\iff 3^{-1}\equiv 4\pmod{11}$

When $$uv\equiv vu\equiv 1\pmod{m}$$

We say that $v$ is the inverse of $u$, every number such that $\gcd(u,m)=1$ has an inverse modulo $m$ and it is noted $u^{-1}$ rather than $\dfrac 1u$.

When you need to solve $ax\equiv b\pmod{m}$ then instead of dividing by $a$ and have $x=\dfrac ba$, you multiply by the inverse of $a$ in $\mathbb Z/m\mathbb Z$ if it exists.

$$ax\equiv b\pmod{m}\iff x\equiv a^{-1}ax\equiv a^{-1}b\pmod{m}$$

But when $\gcd(a,m)\neq 1$ then $a$ has no inverse, same as $0$ as no inverse in $\mathbb R$.