# 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, \ldots, (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 \le a,b \le 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\ \$ Jul 19 '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. Jul 19 '19 at 18:07
• Sorry, that was a typo. Jul 19 '19 at 18:10
• See here for a clearer more detailed presentation of this proof (and equivalents). Jul 19 '19 at 18:15

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$$
• @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. Jul 19 '19 at 19:25