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$.
Best 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$