关于mod 26下非所有数有逆元及13无逆元其他原因的技术问询

Great question—this cuts straight to the core of how modular arithmetic works with multiplicative inverses. Let’s break this down step by step to make it totally clear:

First, What’s a Multiplicative Inverse Modulo m? #

A number a has a multiplicative inverse modulo m if there’s some integer x where:
a * x ≡ 1 mod m
In simple terms: when you multiply a by x, dividing the result by m leaves a remainder of 1.

The Critical Rule: Inverses Only Exist When a and m Are Coprime #

The key mathematical truth here is: a number has a multiplicative inverse modulo m if and only if it shares no common factors with m other than 1 (formally, gcd(a, m) = 1, where gcd stands for "greatest common divisor").

For modulo 26, 26 factors into 2 * 13. That means any number that’s even (shares a factor of 2 with 26) or a multiple of 13 (shares a factor of 13 with 26) can’t have an inverse modulo 26.

Why 13 Specifically Has No Inverse Modulo 26 #

Let’s prove this with a concrete contradiction. Suppose 13 did have an inverse x modulo 26. By definition, that would mean:
13x ≡ 1 mod 26
Translating this to standard integer arithmetic, that’s:
13x - 1 = 26k for some integer k
Rearranging the equation gives:
1 = 13x - 26k = 13(x - 2k)
But this implies 1 is a multiple of 13—which is obviously impossible. There’s no integer x that can make this equation true, so 13 cannot have an inverse modulo 26.

To Wrap It Up #

Only numbers coprime with 26 (i.e., odd numbers not divisible by 13: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25) have multiplicative inverses modulo 26. All other numbers either share a factor of 2 or 13 with 26, making it mathematically impossible to find an x that satisfies the inverse definition.

内容的提问来源于stack exchange，提问作者Moose