I was working on this problem in the modular arithmetic section. When I looked at the implementation of the sum of the divisors I was confused.
Here is the line of code I was confused by.
div_sum = div_sum * (expo(p[i], k[i] + 1) - 1) % MOD * expo(p[i] - 1, MOD - 2) % MOD;
Why do we have to exponentiate the denominator by mod-2 and then multiply it to the numerator?
Thanks!!
its basically this
The modular inverse is the equivalent of the reciprocal in real-number arithmetic; to divide a by b, multiply a by the modular inverse of b.
Fermat’s Little Theorem (not to be confused with Fermat’s Last Theorem) states that all integers $a$not divisible by p satisfy a^{p - 1} \equiv 1 \pmod{p}.
Consequently, a^{p-2} \cdot a \equiv 1 \pmod{p}. Therefore, a^{p - 2} is a modular inverseof a modulo p.
Ohhh my god. I totally forgot about this property with modular arithmetic. Thanks so much!! 