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.