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

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)$$$:

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll gcd_extended(ll a, ll b, ll& x, ll& y) { 
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll x1, y1;
    ll d = gcd_extended(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

ll mod_inv(ll a, ll m) {
    ll x, y;
    ll g = gcd_extended(a, m, x, y);

    return (g == 1) ? (x % m + m) % m : -1;
}

int main() {
    ll a = 30;
    ll b = 5; // b | a
    ll m = 7; // gcd(b, m) = 1

    a %= m; b %= m; // b no longer divides a

    ll inv_b_mod_m = mod_inv(b, m);

    // Incorrect value
    cout << (a / b) % m << endl;

    // Correct value
    cout << (30 / 5) % m << " ";
    cout << (a * inv_b_mod_m) % m << endl;

    return 0;
}

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

Hello friends, help me figure out why I'm getting a Runtime error on test 6 for 1883E - Look Back. I think my solution is mathematically correct however python or the log2 function may have something to do with this.

Here's my submission : 229312603