Modular Arithmetic in AMC 2010 10A #24

In modulo arithmetic, "division" means multiplying by the multiplicative inverse, e.g., $b = \frac{1}{a}$ means the value which when multiplied by $a$ gives $1$ modulo the value, e.g., $ba \equiv 1 \pmod n$. Note you may sometimes see $b = a^{-1}$ instead to avoid using explicit "division". This works, and gives a unique value, in any cases where the value you're dividing and the modulus are relatively prime.

More generally, it'll work in all cases of $\frac{c}{a} \equiv e \pmod n$ where $d = \gcd(a,n)$ and $d \mid c$ since this gcd value "cancels" in the division. Thus, the resulting equivalent modulo equation of $\frac{c'}{a'} \equiv e \pmod n$, where $c' = \frac{c}{d}$ and $a' = \frac{a}{d}$ has $\gcd(a',n) = 1$, has a solution. However, as Bill Dubuque's comment indicates, this assumes you're doing integer division to the extent of removing the common factor of $d$. Note that $a^{-1}$ doesn't exist modulo $n$ in this case. However, $(a')^{-1}$ does exist modulo $\frac{n}{d}$, so a possible interpretation would be $\frac{c'}{a'} \equiv c'(a')^{-1} \equiv e \pmod{\frac{n}{d}}$.

As for why the multiplicative inverse $b = a^{-1}$ exists modulo $n$ if $\gcd(a,n) = 1$, Bézout's identity states that in such cases there exist integers $x$ and $y$ such that

$$ax + ny = 1 \tag{1}\label{eq1}$$

As such $ax \equiv 1 \pmod n$ so $x \equiv a^{-1} = b \pmod n$. This value must be unique, modulo $n$, because if there was another value $x'$ such that $xa \equiv x'a \equiv 1 \pmod n$, then $(x - x')a \equiv 0 \pmod n$. Since $\gcd(a,n) = 1$, this means that $x - x' \equiv 0 \pmod n \; \iff \; x \equiv x' \pmod n$.

Bézout's identity also shows that if $a$ and $n$ are not relatively prime, e.g., $\gcd(a,n) = d \gt 1$, then \eqref{eq1} becomes

$$ax + ny = d \tag{2}\label{eq2}$$

with the integers of the form $ax + ny$ are always multiples of $d$, so it can't be congruent to $1$ and, thus, $a$ would not have a multiplicative inverse.

The Lemma below shows how modular division is compatible with integer division. In particular

$$\,(b,n)=1,\ c = \frac{a}b\in \Bbb Z\ \Rightarrow\,\bmod n\!:\,\ c \equiv \frac{a\bmod n}{b\bmod n} := (a\bmod n)(b\bmod n)^{-1}\qquad\quad $$

Lemma $\ $ If $\,a,b,c,n\in \Bbb Z\,$ and $\,(b,n)=1\,$ then $\ c = a/b\,\Rightarrow\,c\equiv a/b := ab^{-1}\pmod{\!n}\,$

Proof $\ a = bc\,\Rightarrow\, \bmod n\!:\ a\equiv bc\,\Rightarrow\, c\equiv ab^{-1}.\, $ Recall $\,b^{-1}$ exists $\!\bmod n\!\!\!\overset{\rm Bezout\!\!}\iff\! (b,n) = 1$