Modular Division Proof

Revision en1, by Kefrov, 2024-08-19 22:11:11

This short video serves as proof for the following mathematical statement:


$$$ \textbf{(H)} : \frac{a}{b} \mod m = a \cdot b^{-1} \mod m \\ \text{such that } b \mid a \text{ and } \gcd(b, m) = 1 $$$


1999F - Expected Median urged me to study modular arithmetic, specifically modular division. However, no document or video I found contained this proof so I tried to prove it myself. It's not hard so maybe that's why I couldn't find it, or maybe I didn't search well enough.

Anyway, often we are tasked with calculating a huge number modulo $$$10^9 + 7$$$. For this, we need to perform some modular arithmetic tricks, but things get complicated when trying to do division, like in the case of the binomial coefficient $$$\binom{n}{p}$$$. The reason for that is when applying modulo to integers $$$a$$$ and $$$b$$$ such that $$$a \mid b$$$ , there is no guarantee that $$$(a \mod m) \mid (b \mod m)$$$.

Tags number theory, modular arithmetic, modular inverse

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Kefrov 2024-08-20 06:11:07 16 Tiny change: 'orithm</a>:\n\n<spoi' -> 'orithm</a> in $O(\log m)$:\n\n<spoi'
en2 English Kefrov 2024-08-20 01:35:57 1764 Tiny change: 'mod m)$.\nSo to ac' -> 'mod m)$.\n\nSo to ac' (published)
en1 English Kefrov 2024-08-19 22:11:11 1237 Initial revision (saved to drafts)