In mathematics, particularly in the area of arithmetic, 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. In the standard notation of modular arithmetic this congruence is written as
a x ≡ 1 ( mod m ) , {\displaystyle ax\equiv 1{\pmod {m}},}
which is the shorthand way of writing the statement that m divides (evenly) the quantity ax − 1, or, put another way, the remainder after dividing ax by the integer m is 1. If a does have an inverse modulo m, then there is an infinite number of solutions of this congruence, which form a congruence class with respect to this modulus. Furthermore, any integer that is congruent to a (i.e., in a's congruence class) has any element of x's congruence class as a modular multiplicative inverse. Using the notation of w ¯ {\displaystyle {\overline {w}}} to indicate the congruence class containing w, this can be expressed by saying that the modulo multiplicative inverse of the congruence class a ¯ {\displaystyle {\overline {a}}} is the congruence class x ¯ {\displaystyle {\overline {x}}} such that:
a ¯ ⋅ x ¯ = 1 ¯ , {\displaystyle {\overline {a}}\cdot {\overline {x}}={\overline {1}},}
where the symbol ⋅ {\displaystyle \cdot } denotes the multiplication of equivalence classes modulo m. Written in this way, the analogy with the usual concept of a multiplicative inverse in the set of rational or real numbers is clearly represented, replacing the numbers by congruence classes and altering the binary operation appropriately. As with the analogous operation on the real numbers, a fundamental use of this operation is in solving, when possible, linear congruences of the form
a x ≡ b ( mod m ) . {\displaystyle ax\equiv b{\pmod {m}}.}
Finding modular multiplicative inverses also has practical applications in the field of cryptography, e.g. public-key cryptography and the RSA algorithm. A benefit for the computer implementation of these applications is that there exists a very fast algorithm (the extended Euclidean algorithm) that can be used for the calculation of modular multiplicative inverses.
Modular arithmetic
For a given positive integer m, two integers, a and b, are said to be congruent modulo m if m divides their difference. This binary relation is denoted by,
a ≡ b ( mod m ) . {\displaystyle a\equiv b{\pmod {m}}.}
This is an equivalence relation on the set of integers, Z {\displaystyle \mathbb {Z} } , and the equivalence classes are called congruence classes modulo m or residue classes modulo m. Let a ¯ {\displaystyle {\overline {a}}} denote the congruence class containing the integer a, then
a ¯ = { b ∈ Z ∣ a ≡ b ( mod m ) } . {\displaystyle {\overline {a}}=\{b\in \mathbb {Z} \mid a\equiv b{\pmod {m}}\}.}
A linear congruence is a modular congruence of the form
a x ≡ b ( mod m ) . {\displaystyle ax\equiv b{\pmod {m}}.}
Unlike linear equations over the reals, linear congruences may have zero, one or several solutions. If x is a solution of a linear congruence then every element in x ¯ {\displaystyle {\overline {x}}} is also a solution, so, when speaking of the number of solutions of a linear congruence we are referring to the number of different congruence classes that contain solutions. If d is the greatest common divisor of a and m then the linear congruence ax ≡ b (mod m) has solutions if and only if d divides b. If d divides b, then there are exactly d solutions. A modular multiplicative inverse of an integer a with respect to the modulus m is a solution of the linear congruence
a x ≡ 1 ( mod m ) . {\displaystyle ax\equiv 1{\pmod {m}}.}
The previous result says that a solution exists if and only if gcd(a, m) = 1, that is, a and m must be relatively prime (i.e. coprime). Furthermore, when this condition holds, there is exactly one solution, i.e., when it exists, a modular multiplicative inverse is unique: If b and b' are both modular multiplicative inverses of a respect to the modulus m, then
a b ≡ a b ′ ≡ 1 ( mod m ) , {\displaystyle ab\equiv ab'\equiv 1{\pmod {m}},}
therefore
a ( b − b ′ ) ≡ 0 ( mod m ) . {\displaystyle a(b-b')\equiv 0{\pmod {m}}.}
… excerpt ends here. Continue reading the full article.
