0
$\begingroup$

In ax $\equiv$ 1 (mod m) , when gcd(a, m) = 1, there is exactly one solution, i.e., when it exists, a modular multiplicative inverse is unique.

This is written in wikipedia. I am confused because i keep on thinking if a = 2 and m = 3. Then x can be 2,5,8 etc. I know i am missing something but i am unable to get it. I am on my own and thus would be happy if someone can clear my doubt.

$\endgroup$
  • 2
    $\begingroup$ That solutions of a congruence equation are unique means any two solutions are congruent (vs. equal). $\endgroup$ – Bill Dubuque May 15 at 15:56
  • $\begingroup$ Thanks, I understand totally. $\endgroup$ – Prasoon Mishra May 16 at 3:37
1
$\begingroup$

The important idea here is that we are working in the ring $\mathbb{Z}/m$, and questions about uniqueness of inverses should be asked in this context. Taking the $m$ elements of $\mathbb{Z}/m$, there is only one of them that's an inverse to any given $x$.

In your example, all of $2$, $5$, $8$, $11$, $14$ and so on are inverses to $2 (mod 3)$. But they're all equal to $2 (mod 3)$, so as far as $\mathbb{Z}/3$ is concerned that's the only inverse.

$\endgroup$
  • $\begingroup$ The first paragraph may be misleading. While there is a relationship between congruences and quotients rings, it may confuse beginners to make vague remarks like congruences are "working in the" quotient ring since in ENT students often learn congruences long before (quotient) rings. $\endgroup$ – Bill Dubuque May 15 at 15:18
  • $\begingroup$ @BillDubuque That's a good point. Any ideas about how I can improve it? That relationship definitely appears to be where OP's source is taking it, and it's the interpretation I use myself, so I'm not sure what changes should be made. $\endgroup$ – Chessanator May 15 at 15:28
  • $\begingroup$ Without knowing more context that's difficult to say. In some courses they do do essentially construct the quotient ring but without using any knowledge of ring theory. $\endgroup$ – Bill Dubuque May 15 at 15:49
0
$\begingroup$

If we have $a=2$ and $m=3$ then we have the equation $2x=1\mod3$, there are multiple solutions to this notably $x=3n+2$ for $n \in \mathbb{Z}$.

Just an edit: Even though there are lots of solutions, there will only be one solution for $\mod3$ and in $\mod3$ there are the numbers $\{0,1,2\}$. Where the only solution to this is $2$.

$\endgroup$

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.