1 Definition and basic properties
1.1 Congruence formulation of an inverse
For integers \(a\) and \(m\) with \(m\ge 1\), an integer \(x\) is called a modular inverse of \(a\) modulo \(m\) if \[ ax \equiv 1 \pmod m. \] This means that \(m\) divides \(ax-1\). The condition treats \(a\) and \(x\) as residue classes modulo \(m\), so the inverse is a property of \(a\) within modular arithmetic rather than of the particular integer representative chosen.
1.2 Existence criterion: gcd condition
A modular inverse of \(a\) modulo \(m\) exists exactly when \[ \gcd(a,m)=1. \] Equivalently, there must be integers \(u\) and \(v\) such that Bézout’s identity holds: \[ ua+vm=1. \] Reducing this equation modulo \(m\) gives \(ua\equiv 1\pmod m\), so \(u\) is an inverse of \(a\). Conversely, if \(ax\equiv 1\pmod m\), then \(m\mid ax-1\), so any common divisor of \(a\) and \(m\) would also divide \(1\), forcing the gcd to be \(1\).
1.3 Uniqueness modulo \(m\)
When an inverse exists, it is unique modulo \(m\). If \(x\) and \(y\) both satisfy \[ ax\equiv 1\pmod m,\qquad ay\equiv 1\pmod m, \] then subtracting yields \(a(x-y)\equiv 0\pmod m\). With \(\gcd(a,m)=1\), cancellation implies \(x-y\equiv 0\pmod m\), so \(x\equiv y\pmod m\). Thus, there is a single inverse residue class modulo \(m\).
1.4 Non-existence examples and intuition
If \(\gcd(a,m)\ne 1\), the congruence \(ax\equiv 1\pmod m\) cannot hold. For example, let \(a=6\) and \(m=15\). Since \(\gcd(6,15)=3\), every product \(6x\) is divisible by \(3\), so \(6x\) cannot be congruent to \(1\) modulo \(15\) (which is not divisible by \(3\)). More generally, non-coprimality reflects an obstruction to “undoing” multiplication by \(a\) modulo \(m\); multiplication by \(a\) cannot reach residue \(1\).
2 Computing modular inverses
2.1 Brute-force search method
A straightforward method is to test residues \(x=0,1,2,\dots,m-1\) until \(ax\equiv 1\pmod m\). This always works for small \(m\), but it is inefficient for large moduli because it requires up to \(m\) checks. It also provides limited insight into why inverses exist or fail.
2.2 Extended Euclidean algorithm
The extended Euclidean algorithm computes \(\gcd(a,m)\) and coefficients that express the gcd as a linear combination: \[ \gcd(a,m)=sa+tm. \] If \(\gcd(a,m)=1\), then reducing \(sa\equiv 1\pmod m\) shows that \(s\) is the modular inverse of \(a\) modulo \(m\). This method is efficient and robust, with time complexity comparable to the Euclidean algorithm.
2.2.1 Back-substitution to obtain the inverse
The extended algorithm produces remainders via successive divisions. Back-substitution rewrites the final remainder \(1\) as a combination of \(a\) and \(m\). The coefficient of \(a\) in that expression is then taken modulo \(m\) to yield an inverse. Conceptually, each back-substitution step “tracks” how to write the current remainder using the earlier ones until \(1\) is expressed in the form \(sa+tm\).
2.2.2 Worked example with step-by-step coefficients
Compute the inverse of \(a=7\) modulo \(m=26\).
- Apply the Euclidean algorithm:
\[ 26 = 3\cdot 7 + 5, \] \[ 7 = 1\cdot 5 + 2, \] \[ 5 = 2\cdot 2 + 1. \]
- Back-substitute to express \(1\) as a combination of \(7\) and \(26\):
- From \(5=2\cdot 2+1\), get
\[ 1 = 5 - 2\cdot 2. \]
- From \(7=1\cdot 5+2\), get \(2=7-5\). Substitute:
\[ 1 = 5 - 2(7-5)=5-2\cdot 7+2\cdot 5 = 3\cdot 5 - 2\cdot 7. \]
- From \(26=3\cdot 7+5\), get \(5=26-3\cdot 7\). Substitute:
\[ 1 = 3(26-3\cdot 7)-2\cdot 7 = 3\cdot 26 - 9\cdot 7 - 2\cdot 7 = 3\cdot 26 - 11\cdot 7. \]
- Reduce modulo \(26\):
\[ 1 \equiv -11\cdot 7 \pmod{26}. \] Hence \(-11\) is an inverse of \(7\) modulo \(26\). A standard representative in \(\{0,\dots,25\}\) is \[ -11 \equiv 15 \pmod{26}. \] Check: \[ 7\cdot 15=105\equiv 1\pmod{26}. \]
2.3 Using modular arithmetic identities
2.3.1 Inverse of negative residues
If \(a^{-1}\) denotes the inverse of \(a\) modulo \(m\), then the inverse of \(-a\) is \(-(a^{-1})\) modulo \(m\). Indeed, \[ (-a)(-a^{-1})=a\,a^{-1}\equiv 1\pmod m. \] Thus, one can often reduce the computation to a positive representative and then adjust the sign.
2.3.2 Scaling and normalization
If \(a^{-1}\) is known, then for any integer \(k\) coprime to \(m\), the inverse of \(ka\) can be expressed using inverses of \(k\) and \(a\): \[ (ka)^{-1} \equiv a^{-1}\,k^{-1}\pmod m, \] because \((ka)(a^{-1}k^{-1})=1\) modulo \(m\). More generally, after computing an inverse as an integer (possibly negative or larger than \(m\)), it is normalized by taking the result modulo \(m\) into the chosen residue range.
3 Inverses in linear congruences
3.1 Solving \(ax \equiv b \pmod m\)
A linear congruence of the form \[ ax \equiv b \pmod m \] can be solved efficiently when \(\gcd(a,m)=1\). In that case, multiply both sides by the inverse \(a^{-1}\) modulo \(m\): \[ x \equiv a^{-1}b \pmod m. \] Because the inverse is unique modulo \(m\), the solution residue class is also unique.
3.2 Case analysis when \(\gcd(a,m)\neq 1\)
If \(d=\gcd(a,m)\) does not equal \(1\), the congruence may have no solutions or multiple solutions. A standard criterion is:
- Solutions exist iff \(d \mid b\).
When solutions exist, there are exactly \(d\) distinct solution classes modulo \(m\). One common approach is to divide the congruence by \(d\) after verifying \(d\mid b\), then solve the reduced congruence modulo \(m/d\). The resulting solutions lift back to modulo \(m\) in a controlled way.
3.3 Equivalent transformations and simplification
Congruences allow transformations that preserve solution sets, such as:
- adding multiples of \(m\) to either side,
- multiplying both sides by an integer that is coprime to \(m\) (when applicable),
- reducing coefficients modulo \(m\).
When \(\gcd(a,m)=1\), the “modular division” step of multiplying by \(a^{-1}\) is valid and yields a simplified congruence for \(x\). Care is needed when \(\gcd(a,m)\ne 1\), since cancellation may not hold.
3.4 Relation to modular division
In everyday arithmetic, dividing by \(a\) in an equation corresponds to multiplying by \(1/a\). In modular arithmetic, division is interpreted through the inverse: if \(a\) has an inverse modulo \(m\), then “dividing by \(a\)” means multiplying by \(a^{-1}\). When no inverse exists, the idea of modular division breaks down, reflecting the failure of cancellation.
4 Algebraic structure and group-theoretic viewpoint
4.1 Units modulo \(m\)
An integer class modulo \(m\) is called a unit if it has a multiplicative inverse modulo \(m\). The set of all units is precisely the set of residue classes represented by integers \(a\) with \(\gcd(a,m)=1\). Thus, the gcd criterion from basic theory is reinterpreted as membership in an algebraic structure.
4.2 The group \((\mathbb{Z}/m\mathbb{Z})^\times\)
The units modulo \(m\) form a group under multiplication, denoted \((\mathbb{Z}/m\mathbb{Z})^\times\). The group axioms follow from:
- closure: the product of two coprime residues remains coprime to \(m\),
- associativity: inherited from integer multiplication,
- identity: the residue class of \(1\),
- inverses: guaranteed by the gcd condition.
The size of this group is \(\varphi(m)\), Euler’s totient function, which counts how many residues are coprime to \(m\).
4.3 Inverses and cancellation laws
In a group, inverses enable cancellation: if \(ab\equiv ac\pmod m\) and \(a\) is a unit modulo \(m\), then multiplying by \(a^{-1}\) gives \(b\equiv c\pmod m\). This provides a precise algebraic justification for the earlier cancellation argument based on \(\gcd(a,m)=1\). When \(a\) is not a unit, cancellation can fail, mirroring the non-existence of inverses.
4.4 Orders, cycles, and inverse powers
Within \((\mathbb{Z}/m\mathbb{Z})^\times\), each unit \(a\) has a multiplicative order: the smallest positive \(k\) such that \[ a^k\equiv 1\pmod m. \] The powers of \(a\) then cycle through a finite set of residues. The inverse of \(a\) can be expressed using the order: if \(a^k\equiv 1\), then \(a^{-1}\equiv a^{k-1}\pmod m\). This connects modular inverses to periodic behavior in modular exponentiation.
5 Applications and contexts
5.1 Modular rational expressions
Modular inverses allow expressions resembling fractions. For instance, an expression like \(b/a\) in modular arithmetic is interpreted as \(b\cdot a^{-1}\) provided \(\gcd(a,m)=1\). This technique is used to rewrite formulas so that division by an integer is replaced by multiplication by its inverse, keeping computations within the modular system.
5.2 Chinese remainder theorem and inverses
5.2.1 Constructing CRT solutions using inverses
The Chinese remainder theorem (CRT) reconstructs an integer solution modulo \(M\) from solutions modulo coprime factors. In the constructive form, inverses appear explicitly. For example, if \(M=m_1m_2\) with \(\gcd(m_1,m_2)=1\), one can build a solution from residues \(x_1\) modulo \(m_1\) and \(x_2\) modulo \(m_2\) using coefficients that involve inverses of \(m_1\) modulo \(m_2\) (and vice versa). These inverses ensure the combined value satisfies both congruences simultaneously.
5.3 Fast computations in algorithms
Modular inverses are computational building blocks in algorithms for solving congruences, manipulating modular equations, and supporting efficient arithmetic. In many settings, computing an inverse via the extended Euclidean algorithm is substantially faster than brute force, especially when working with large moduli. Modular inverses also help keep expressions small and structured during iterative computations.
6 Special cases and common pitfalls
6.1 Prime moduli and Fermat’s little theorem connection (overview)
When \(m\) is prime \(p\) and \(a\not\equiv 0\pmod p\), Fermat’s little theorem gives \[ a^{p-1}\equiv 1\pmod p. \] From this, \(a^{p-2}\) serves as the inverse of \(a\) modulo \(p\): \[ a\cdot a^{p-2}=a^{p-1}\equiv 1\pmod p. \] This offers an alternative computation strategy using modular exponentiation, often effective when inverses are needed repeatedly in prime-modulus contexts.
6.2 Composite moduli: why inverses may fail
For composite \(m\), not all nonzero residues have inverses. Even if \(a\not\equiv 0\pmod m\), it can still share a nontrivial gcd with \(m\), preventing \(ax\equiv 1\pmod m\). Practical computations must therefore check \(\gcd(a,m)=1\) (or the relevant divisibility conditions) before treating modular division as valid.
6.3 Handling \(a \equiv 0 \pmod m\)
If \(a\equiv 0\pmod m\), then \(ax\equiv 0\pmod m\) for all \(x\), so the congruence \(ax\equiv 1\pmod m\) is impossible. More generally, if \(a\) is divisible by \(m\), it cannot be a unit modulo \(m\), and no inverse exists.
6.4 Multiple representations of the same inverse
Although the inverse is unique as a residue class modulo \(m\), it admits many integer representatives. If \(x\) is an inverse, then so is \(x+km\) for any integer \(k\). Confusion can arise if two computations produce inverses that appear different as integers but are congruent modulo \(m\). Verification should therefore be performed modulo \(m\), not by exact integer equality.
7 Notation and verification
7.1 Verifying \(a x \equiv 1 \pmod m\)
To confirm a purported inverse \(x\), compute \(ax-1\) and check whether it is divisible by \(m\). Equivalently, reduce the product \(ax\) modulo \(m\) and ensure the remainder is \(1\). This verification is straightforward and can be used regardless of how the inverse was computed.
7.2 Typical conventions for inverse notation
Notation varies by context. A common convention writes \(a^{-1}\pmod m\) for the inverse residue class of \(a\) modulo \(m\). The symbol \(\bmod m\) clarifies that the inverse is taken with respect to \(m\), not as a rational number inverse. In computational settings, it is also common to present an inverse in a specific range, such as \(0\le x < m\).
7.3 Checking consistency across different residues
When comparing two inverses produced by different methods, they should be tested for congruence: \[ x\equiv y\pmod m. \] If they are congruent, they represent the same inverse residue class even if their integer values differ. Consistent modular verification avoids mistakes caused by mixing representatives or using identities outside their valid conditions.