Congruences · Definition

Modular inverse

elementary number theorycongruences

Before you start you need to know

Dividing by a number in modular arithmetic requires multiplying by its inverse. This concept allows linear congruences to be solved systematically.

Definition

The modular inverse of an integer \(a\) modulo \(m\) is an integer \(b\) whose product with \(a\) is congruent to 1 modulo \(m\).

\[ab \equiv 1 \pmod{m}\]

If \(\gcd(a,m)=1\), Bézout's identity gives integers \(x\) and \(y\) with \(ax+my=1\). Reducing modulo \(m\) shows that \(x\) is an inverse of \(a\). The inverse is unique modulo \(m\): any two inverses are congruent to each other. Conversely, if \(ab\equiv 1\pmod{m}\), every common divisor of \(a\) and \(m\) divides 1; hence the inverse exists if and only if \(\gcd(a,m)=1\).

To find the inverse of \(7\) modulo \(26\), the Euclidean algorithm gives \(26=3\cdot 7+5\), \(7=1\cdot 5+2\), \(5=2\cdot 2+1\). Back-substituting yields \(1=3\cdot 5-2\cdot 7\) and finally \(1=3\cdot 26-11\cdot 7\), so the inverse is \(-11\equiv 15\).

A typical mistake is trying to invert a number that is not coprime to the modulus, such as \(6\) modulo \(9\). Since \(\gcd(6,9)=3\neq 1\), the congruence \(6b\equiv 1\pmod{9}\) has no solution.

Think about it

Why does \(6\) have no inverse modulo \(9\)?

Because \(\gcd(6,9)=3\neq 1\).

Exercises 10

  1. What is the necessary and sufficient condition for \(a\) to have an inverse modulo \(m\)?
  2. Does \(2\) have an inverse modulo \(4\)?
  3. State the uniqueness property of the modular inverse modulo \(m\).
  4. Which integer \(b\) satisfies \(3b\equiv 1\pmod{5}\)?
  5. Which of these congruences has a solution in \(b\)?
  6. Find the inverse of \(5\) modulo \(11\).
  7. Which pair of numbers are inverses of each other modulo \(10\)?
  8. Solve \(3x\equiv 2\pmod{7}\) using the inverse of \(3\).
  9. If \(b\) is an inverse of \(a\) modulo \(m\) and \(c\equiv a\pmod{m}\), what holds?
  10. Find the inverse of \(7\) modulo \(26\) and use it to solve \(7x\equiv 9\pmod{26}\).

References

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 4
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 2