1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ $ax+my = 1\,\Rightarrow\,\gcd(a,m) = 1,\,$ so $\,a\in S\,$ by $\,0\le a < m\ \ $ $\endgroup$ – Bill Dubuque Jul 19 at 18:07
  • 1
    $\begingroup$ 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. $\endgroup$ – Anurag A Jul 19 at 18:07
  • $\begingroup$ Sorry, that was a typo. $\endgroup$ – F. Munnelly Jul 19 at 18:10
  • $\begingroup$ See here for a clearer more detailed presentation of this proof (and equivalents). $\endgroup$ – Bill Dubuque Jul 19 at 18:15
1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – F. Munnelly Jul 19 at 18:50
  • $\begingroup$ It falls out from the application of the Euclidean algorithm. $\endgroup$ – Doug M Jul 19 at 19:12
  • 1
    $\begingroup$ @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. $\endgroup$ – Bill Dubuque Jul 19 at 19:25
  • $\begingroup$ @DougM One doesn't need the Euclidean algorithm or Bezout to deduce that trivial direction - see above. $\endgroup$ – Bill Dubuque Jul 19 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.