Multiplicative Inverse
(模數乘法反元素)
sjLin
February 28, 2022
假設a ∈ Z, n ∈ Z
+
，ax ≡ 1 (mod n)，則稱x為a在 mod n下的multiplicative inverse，而這個x有無限個，符合最小正整
數x，稱為a在 mod n下的最小乘法反元素(least multiplicative inverse)，這最小乘法反元素記作a
−1
(mod n)。
定定定理理理
假設a ∈ Z, n ∈ Z
+
，若gcd(a, n) = 1, 則a在 mod n的乘法反元素存在。
證證證明明明
因為gcd(a, n) = 1，所以a, n互質，使得∃s, t ∈ Z，則as + nt = 1⇒ as + nt ≡ 1 (mod n)。因為nt ≡ 0 (mod n)，
所以as ≡ 1 (mod n)。
因此s為a在 (mod n)下的乘法反元素。
例例例題題題-92 台台台大大大資資資工工工
Find the inverse of 4 modulo 7.
Ans.
∃s, t ∈ Z，使得4s + 7t = 1。
由Eulidean Algorithm得知，
7 = 1 · 4 + 3
4 = 1 · 3 + 1
⇒ 1 = 4 − 1 · 3
1 = 4 − 1(7 − 1 · 4)
整理
1 = (−1) · 7 + 2 · 4
⇒ 1 = (−1 − 4k) · 7 + (2 + 7k) · 4, ∀k ∈ Z
因此，2 + 7k, ∀k ∈ Z為4在 (mod 7)下的乘法反元素。
1
例例例題題題-98政政政大大大資資資料料料
Find the least positive integer x satisfying he congruence:
531x ≡ 1 (mod 1769)
Ans.
由Eulidean Algorithm得知，
1769 = 3 · 531 + 176
531 = 3 · 176 + 3
176 = 58 · 3 + 2
3 = 1 · 2 + 1
⇒ 1 = 3 − 2
= 3 − (176 − 58 · 3)
= 3 − 176 + 58 · 3
= (−1) · 176 + 59 · 3
= (−1) · 176 + 59 · 531 − 177 · 176
= (−178) · 176 + 59 · 53
= (−178) · (1769 − 3 · 531) + 59 · 531
= (−178) · 1769 + 593 · 531
∴ 531
−1
在 (mod 1769)下的最小乘法反元素為593。
推推推廣廣廣
乘法反元素可以推廣到解一般的方程式ax ≡ b (mod n)
例例例題題題-98清清清大大大資資資工工工
Solve the linear congruence 7x ≡ 13 (mod 19) to find all the integer solutions x.
Ans.
因為gcd(7, 19) = 1，所以有整數解(s, t)，使得7s + 19t = 1，由Eulidean Algorithm得知，
19 = 2 · 7 + 5
7 = 1 · 5 + 2
5 = 2 · 2 + 1
⇒ 1 = 5 − 2 · 2
= 5 − 2(7 − 5)
= 3 · 5 + (−2) · 7
= 3(19 − 2 · 7) + (−2) · 7
= 3 · 19 + (−8) · 7
左右同乘13，即計算7x ≡ 13 (mod 19)
⇒ 13 = 39 · 19 + (−104) · 7
通式13 = (39 − 7k) · 19 + (−104 + 19k) · 7, ∀k ∈ Z
⇒ −104 ≡ 10 (mod 19)
∴ 10 + 19k, ∀k ∈ Z為x的所有可能解。
2
引引引理理理
假設a ∈ Z且p為一質數，則a為a在 (mod p)下的乘法反元素↔ a ≡ ±1 (mod p)
證證證明明明
(→)
因為a為a在 (mod p)下的乘法反元素，
⇒ a
2
≡ 1 (mod p)
p|(a
2
− 1)
p|(a − 1)(a + 1)
所以p|(a − 1)或p|(a + 1)
因為同餘的兩數相減的值，會被 mod 的值整除
所以a ≡ −1 (mod p)或a ≡ 1 (mod p)
(←)
因為a ≡ ±1 (mod p)，所以a
2
≡ 1 (mod p)
因此，a為a在 (mod p)下的乘法反元素。
3
