Modular Arithmetic in AMC 2010 10A #24

Question

Link to the problem/solution: https://artofproblemsolving.com/wiki/index.php/2010_AMC_10A_Problems/Problem_24

I'm trying to understand the following step in the solution to the aforementioned AMC problem.

Given:

1. $M = \cfrac{90!}{5^{21}}$
2. $N = \cfrac{90!}{10^{21}} = \cfrac{M}{2^{21}}$
3. $M \equiv 24 \bmod 25$
4. $2^{21} \equiv 2 \bmod 25$

Then:

$N \bmod 25 = \cfrac{24}{2} = 12$

In the above approach, we write N as a fraction, find the modulo-25 residue of the numerator and denominator, and divide the residues to find the modulo-25 residue of N.

I recently finished working through the Art of Problem Solving textbook "Introduction to Number Theory", so I'm familiar with the basics of solving modular congruence equations and modular arithmetic, but I was confused by this step. I was wondering: under what conditions can we divide modular congruent statements, and why does this step work? My understanding was that addition, multiplication, and exponentiation work with modular congruent statements, but I never saw an example in the book of dividing statements as in the above case.

For instance:

$98 \equiv 23 \bmod 25$

$49 \equiv 24 \bmod 25$

$2 \equiv ? \bmod 25$

In this example, I don't think division produces a meaningful result (perhaps it does, but I don't know how to evaluate 23/24?). Why does division fail here, but work above? (EDIT: -2 / -1 = 2, so I guess it works in this case too!)

My suspicion is that I'm missing something really basic here, perhaps even misinterpreting what the solution is doing. If you have any book recommendations that would help me improve and solidify my understanding of modular arithmetic/modular congruence, I'd greatly appreciate it!

Answer 1

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.

Answer 2

Division does not always work in modular arithmetic. You may be familiar with the fact that $\mathbb{Z}\setminus n\mathbb{Z}$ is an abelian (commutative) group under addition, so we can add and subtract as usual. But this isn't the case with multiplication. Instead, we must take the set $(\mathbb{Z}\setminus n\mathbb{Z})^\times$, the set of congruence classes mod $n$ that have a multiplicative inverse. Recall that a multiplicative inverse for $a$ is an element $b=a^{-1}$ such that $a\cdot b=1$. In the example provided above, we have \begin{align*} M & \equiv 24 \mod 25 \\ 2^{21} & \equiv 2\mod 25 \end{align*} Notice that $2$ has a multiplicative inverse, since $2\cdot 13 \equiv 26\equiv 1\mod 25$. Similarly, $24\cdot24\equiv 1\mod 25$. Thus we have \begin{align*} M\div2^{21} &\equiv M\times (2^{21})^{-1}\mod 25 \\ & \equiv 24 \times 2^{-1}\mod 25 \\ & \equiv 24\times 13\mod 25 \\ & \equiv 312 \mod 25 \\ & \equiv 12 \mod 25 \end{align*}

Answer 3

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$