# Let m, x be positive integers such that GCD(m, x) = 1. Then x has a multiplicative inverse modulo m, and it is unique (modulo m).

The theorem quoted in the title was actually stated differently in the problem I was reading. The original statement was as follows:

Let m be a positive integer and let S denote the set of positive integers less than m that are relatively prime to m. Prove that for each x in S, there exists a unique y in S such that xy is congruent to 1 modulo m.

The proof that I have encountered addresses the statement of the theorem given in the title:

Consider the sequence of m numbers 0, x, 2x, ..., (m−1)x. We claim that these are all distinct modulo m. Since there are only m distinct values modulo m, it must then be the case that ax = 1 mod m for exactly one a (modulo m). This a is the unique multiplicative inverse. To verify the above claim, suppose that ax = bx mod m for two distinct values a,b in the range 0 ≤ a,b ≤ m−1. Then we would have (a−b)x = 0 mod m, or equivalently, (a−b)x = km for some integer k (possibly zero or negative). But since x and m are relatively prime, it follows that a−b must be an integer multiple of m. This is not possible since a,b are distinct non-negative integers less than m.

As far as I can understand, this only proves that x always has a unique multiplicative inverse, but not that this inverse belongs to the set S (as defined by the original statement of the theorem). I understand that this proof is correct and I can see why it would work when m is prime (as the set S would then contain all positive integers less than m), however when m is any positive integer the set S would not necessarily contain m-1 elements. Therefore, it seems as if the proof does not exclude the possibility that the multiplicative inverse is not itself relatively prime to m.

• $ax+my = 1\,\Rightarrow\,\gcd(a,m) = 1,\,$ so $\,a\in S\,$ by $\,0\le a < m\ \$ – Bill Dubuque Jul 19 at 18:07
• You statement: "Prove that for each m in S, there exists a unique m in S such that xy is congruent to 1 modulo m. " doesn't make sense. Perhaps you wanted to define $S$ differently. – Anurag A Jul 19 at 18:07
• Sorry, that was a typo. – F. Munnelly Jul 19 at 18:10
• See here for a clearer more detailed presentation of this proof (and equivalents). – Bill Dubuque Jul 19 at 18:15

## 1 Answer

It sounds like you accept that for any $$x\in S$$ s that there exist a $$y\in \{1,\cdots, m-1\}$$ such that $$xy\equiv 1 \pmod m$$ but you are not convinced that $$y\in S$$

what is then $$\gcd(y,m)$$?

We know that $$xy - pm= 1$$ (for some integer $$p$$) therefore $$\gcd(y,m) = 1$$

• Is the fact that xy - pm = 1 ⇒ gcd(y, m) = 1 based on a theorem itself? I think it makes sense since if y and m shared a factor k greater than 1, then that could be factored out so that k(xq - pr) = 1, which would imply that k = 1 (along with xq-pr =1) anyway. – F. Munnelly Jul 19 at 18:50
• It falls out from the application of the Euclidean algorithm. – Doug M Jul 19 at 19:12
• @F.Munnelly It's the trivial direction of the Bezout identity (when stated in $\!\iff\!$ form). But it is an immediate consequence of divisibility laws: $\,d\mid y,m\,\Rightarrow\, d\mid xy,pm\,\Rightarrow\, d\mid xy+pm = 1.\,$ Equivalently, sets of (common) multiples $M$ are closed under both addition, and multiplication by any integer, therefore $\,y,m\in M\,\Rightarrow\, xy+pm\in M\,$ for any $x,p\in\Bbb Z\$ (here $M = d\Bbb Z =$ all multiples of $d).\,$ Such sets of (common) multiples are prototypical examples of ideals. – Bill Dubuque Jul 19 at 19:25
• @DougM One doesn't need the Euclidean algorithm or Bezout to deduce that trivial direction - see above. – Bill Dubuque Jul 19 at 19:26