# Modular Multiplicative Inverse ## Metadata **Status**:: #x **Zettel**:: #zettel/fleeting **Created**:: [[2024-03-29]] **Topic**:: [[♯ Math]] ## Synopsis A **modular multiplicative inverse** of an integer $a$ is an integer $x$ such that the product $ax$ is congruent to 1 with respect to the modulus $m$. $ax \equiv 1 \pmod{m}$ ## Algorithm The integer $a$ has an inverse $x$ if it is relative prime with $m$. If $m$ is a prime number, every member in the modular set has an inverse. The inverse can be found by using the [extended Euclidean algorithm](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm), where the original [Euclidean algorithm](https://en.wikipedia.org/wiki/Greatest_common_divisor#Euclidean_algorithm) is used for computing the greatest common divisor. > [!note] Bézout's identity > Let _a_ and _b_ be integers with greatest common divisor _d_. Then there exist integers _x_ and _y_ such that $ax + by = d$. Moreover, the integers of the form $az + bt$ are exactly the multiples of _d_. > [!example] Python Example Code > ```python > import sys > from typing import Tuple > sys.setrecursionlimit(1000000) # long type, 32bit OS 4B, 64bit OS 8B (1bit for sign) > > def egcd(a: int, b: int) -> Tuple[int, int, int]: > """return (g, x, y) such that a*x + b*y = g = gcd(a, b)""" > if a == 0: > return (b, 0, 1) > else: > b_div_a, b_mod_a = divmod(b, a) > g, x, y = egcd(b_mod_a, a) > return (g, y - b_div_a * x, x) > ``` > ^0z3ynr See also [egcd.py at doitian/ecc-demo](https://github.com/doitian/ecc-demo/blob/main/ecc_demo/egcd.py). Attention that the result is required to be monic when operands are polynomials (See [[Extension Field Arithmetic]]). ![[Wikipedia Authors - Extended Euclidean Algorithm (Highlights)#^700420596]] ## Modular Division If $x$ is the multiplicative inverse of $a$, modular division is defined as: $b / a = bx \pmod{m}$ ## References - [[Wikipedia Authors - Modular Multiplicative Inverse (Highlights)]] - [Extended Euclidean algorithm - Wikipedia](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm) - [Algorithm Implementation/Mathematics/Extended Euclidean algorithm - Wikibooks, open books for an open world](https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm) - [Greatest common divisor - Wikipedia](https://en.wikipedia.org/wiki/Greatest_common_divisor) - [Bézout's identity - Wikipedia](https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity)