3
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ I suggest you look at this website: cs.brown.edu/courses/cs007/modmult/node2.html. Along the lines of what John Omielan has said, division should be interpreted as multiplying by a multiplicative inverse (which may or may not exist). $\endgroup$ – paulinho Jun 16 at 0:49
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ @recreationalmath If by the "first problem" you mean $N \bmod 25 = \cfrac{24}{2} = 12$, then you can either just do the division as stated or, since $\gcd(2,25) = 1$, then you can find that $2^{-1} \equiv 13 \pmod{25}$ since $2(13) = 26 \equiv 1 \pmod{25}$, and then use $N \equiv 24(2^{-1}) \equiv 24(13) = 312 \equiv 12 \pmod{25}$. Using multiplicative inverses works for the first problem, but it's simpler & easier to just divide directly instead. I just tried to give a general explanation of the mechanics & what works in all cases to help you analyze & solve more complicated cases. $\endgroup$ – John Omielan Jun 16 at 1:25
  • 1
    $\begingroup$ Sorry about that - my comment posted prematurely. Could you let me know if the following logic (using the mechanic you introduced) is correct? In the context of the "first problem", on the LHS when I divide by $2^{21}$, I'm actually multiplying by the multiplicative inverse of $2^{21}$ modulo-25, which is 13. So on the RHS, 24*13 = -1*13 = -13 = 12. I appreciate the general explanation of the mechanic btw - exactly what I was looking for here, though I still need to digest it. $\endgroup$ – recreationalmath Jun 16 at 1:31
  • 1
    $\begingroup$ The logic in your comment is correct. This shows there's more than one way to do modulus type calculations, with some being easier than others, but if they're done correctly they have to be consistent, i.e., they have to come up with the same answer. This is why you also got $12$ as the answer using your technique. $\endgroup$ – John Omielan Jun 16 at 1:36
  • 1
    $\begingroup$ @recreationalmath What John wrote is correct, but it does not go far enough to justify the correctness of the calculations in your question, since we need to know that the modular division will yield the same result as reducing the integer division. That is proved in my answer, so be sure to see that (and be sure to undersatnd why such a proof is necessary). $\endgroup$ – Bill Dubuque Jun 16 at 1:49
  • 1
    $\begingroup$ @recreationalmath One subtlety above is worth elaboration. The validity of cancellation of common factors from the top & bottom of fractions depends on whether or not the division denotes an integer or modular operation. For modular division we also need to cancel from the modulus too see here.. Using the same slash symbol for both integer and modular division can cause problems so it is essential to keep them straight. $\endgroup$ – Bill Dubuque Jun 16 at 2:08
3
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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*}

$\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.