Modular Inverse via Fermat
Divide under a modulus safely.
Modular Inverse via Fermat is a free Coding Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Division Breaks Under Mod
Add, subtract, and multiply behave nicely under a modulus, but plain division does not. You cannot just divide and take the remainder. ⚠️
Replace Divide with Multiply
The fix is the modular inverse: dividing by x becomes multiplying by the inverse of x. So a / b mod m turns into a times b's inverse.
What an Inverse Is
The inverse of x is the number that gives 1 when multiplied by x under the modulus. It plays the role of 1/x in ordinary arithmetic.
# x * inv(x) % m == 1Primes Make It Possible
An inverse exists only when x shares no factor with m. Using a prime modulus like 1e9+7 guarantees every nonzero x has one.
Enter Fermat's Little Theorem
Fermat's little theorem says that for a prime p, x to the power p minus 1 is congruent to 1, as long as x is not a multiple of p.
# x^(p-1) % p == 1Derive the Inverse
Split off one factor of x and the rest must be its inverse. So the inverse of x is x raised to the power p minus 2, taken mod p.
# inv(x) = x^(p-2) % pCompute It with Fast Power
That exponent is huge, so use the fast exponentiation from the last lesson. In Python, one call to pow does the whole job for you.
inv = pow(x, MOD - 2, MOD)Use It to Divide
To compute a divided by b under the mod, multiply a by the inverse of b. The remainder is exactly the true quotient mod p.
ans = a * pow(b, MOD - 2, MOD) % MODNever Invert Zero
There is no inverse of 0, since nothing times zero is one. Guard against dividing by a value that reduces to zero under the modulus.
Cost of One Inverse
Each Fermat inverse is one fast power, so it costs O(log p) time. That is cheap for a few divisions but adds up if you do millions.
Batch Inverses Hint
When you need many inverses, precompute them with a clever linear pass instead of a pow per element. You will rely on that for nCr next.
Quick Check
Which power gives the modular inverse under a prime?
Recap
You now divide under a prime modulus by multiplying with the modular inverse, found as x to the p minus 2 via pow. Just never invert zero. ✅
Frequently asked questions
Is the “Modular Inverse via Fermat” lesson free?
Yes — the full text of “Modular Inverse via Fermat” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Modular Inverse via Fermat”?
Divide under a modulus safely. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Modular Inverse via Fermat” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Work Modulo a Prime
- Fast Modular Exponentiation
- Modular Inverse via Fermat
- nCr with Precomputed Factorials