Hey there! Let's break down what a modular multiplicative inverse is, and unpack that key statement from J. Gallian's book clearly.

什么是模n乘法逆元？ #

Think of it like the "modular version" of a reciprocal. For integers a and n, an integer x is called the modular multiplicative inverse of a modulo n if multiplying a by x gives a result that leaves a remainder of 1 when divided by n. In mathematical terms, that's:
a * x ≡ 1 (mod n)

Unlike regular reciprocals (where a*(1/a)=1), this only works in the context of modular arithmetic—we don't need a*x to equal 1 exactly, just that when you divide a*x by n, the leftover is 1.

Quick example: #

Take n=7 and a=3. If we pick x=5, we get 3*5=15, and 15 mod 7 = 1 (since 7*2=14, 15-14=1). So 5 is the modular inverse of 3 modulo 7.

解读Gallian的结论：“整数a存在模n乘法逆元当且仅当a与n互素” #

First, let's clarify what "integer a's modular multiplicative inverse modulo n" means here—it's exactly the x we defined above: an integer that satisfies a*x ≡ 1 (mod n).

This biconditional statement has two parts:

• Forward direction: If a and n are coprime (their greatest common divisor, gcd(a,n), is 1), then such an inverse x definitely exists.
  • Example: a=4, n=9 (gcd(4,9)=1). The inverse is 7, because 4*7=28, and 28 mod 9 = 1.
• Reverse direction: If an inverse x exists for a modulo n, then a and n must be coprime.
  • Example: a=6, n=9 (gcd(6,9)=3). No matter what integer x you pick, 6x is a multiple of 3. When you divide 6x by 9, the remainder can only be 0, 3, or 6—never 1. So no inverse exists, which lines up with the conclusion.

One quick side note: The inverse isn't unique, but all valid inverses are congruent modulo n. For example, 5, 12, 19, etc., all work as inverses of 3 modulo 7—they all leave a remainder of 5 when divided by 7.

内容的提问来源于stack exchange，提问作者Aashish Loknath Panigrahi