Proof for Modular Division trick

Правка en3, от Kefrov, 2024-08-20 06:11:07

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


$$$ \displaystyle \textbf{(H)} : \frac{a}{b} \mod m = a \cdot b^{-1} \mod m $$$
$$$ \displaystyle \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 large number modulo $$$10^9 + 7$$$. For this, we need to perform some modular arithmetic tricks, but things get complicated when trying to perform division, like in the case of the binomial coefficient $$$\binom{n}{p}$$$. The reason for this is that when applying modulo to integers $$$a$$$ and $$$b$$$ such that $$$b \mid a$$$, there is no guarantee that $$$(b \mod m) \mid (a \mod m)$$$. So to actually calculate $$$\frac{a}{b} \mod m$$$, we need to use the Modular Multiplicative Inverse of $$$b$$$ as shown in the statement above.

We can easily find $$$b^{-1}$$$ using the Extended Euclidean Algorithm in $$$O(\log m)$$$:

Code

It makes more sense to prove that $$$(\frac{a}{b} \mod m = r_a \cdot r_b^{-1} \mod m)$$$ such that $$$(r_a = a \mod m)$$$ and $$$(r_b = b \mod m)$$$. However, I wanted to keep things simple. This can still be proven in a similar fashion.

SecondThread's video is great, it doesn't include this proof which I was looking for but I really recommend it.

Hope this helped! <3

Теги number theory, modular arithmetic, modular inverse

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский 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 Английский Kefrov 2024-08-20 01:35:57 1764 Tiny change: 'mod m)$.\nSo to ac' -> 'mod m)$.\n\nSo to ac' (published)
en1 Английский Kefrov 2024-08-19 22:11:11 1237 Initial revision (saved to drafts)