What does it mean for two integers to be multiplicative inverses modulo m?

An integer a has an inverse modulo m if and only if the greatest common divisor of a and m is equal to 1, written as $(a,m)=1$. If the greatest common divisor between a and m is greater than 1, then there is no inverse modulo m.

Conditions: a is an integer.; m is the modulus.; (a,m) denotes the greatest common divisor of a and m.

18 is its own inverse modulo 19 because 18 is congruent to -1 modulo 19, and -1 is always its own multiplicative inverse since $(-1)(-1)=1$. Therefore, $18 \cdot 18 \equiv (-1)(-1) \equiv 1 \pmod{19}$.

Conditions: Working modulo 19.; Using the fact that 18 ≡ -1 (mod 19).

Negative residues make finding modular inverses easier by replacing a large positive representative with a smaller-magnitude equivalent residue modulo m. This often turns the problem into finding the inverse of a simpler number, like -1 or -2, which can be recognized immediately or factored more easily.

Conditions: The replacement must be congruent modulo the same m.; The resulting residue should still be invertible modulo m.

To find the inverse of a modulo m by hand, start with 1 and repeatedly add the modulus m to generate numbers congruent to 1 modulo m. Stop when you reach a number that is a multiple of a.

Conditions: Used to find an inverse of a modulo m.; One looks among integers congruent to 1 modulo m for a multiple of a.

5 has no inverse modulo 10 because the greatest common divisor of 5 and 10 is 5, which is not 1. According to the existence theorem, an integer has an inverse modulo m if and only if their gcd is 1.

Conditions: Modulus is 10.; Number whose inverse is requested: 5.