0

I don't understand the exact steps the following statement is using in regards to what is the multiplicative inverse of $13 \mod 40$

One can find a multiplicative inverse of $13$ by observing that:
$13 \cdot 3 = 39 \equiv -1 \mod 40$ (a)
Hence
$13 \cdot (-3) \equiv 1 \mod 40$ (b)
So $-3$ is a multiplicative inverse of $13 \mod 40$

Now I do understand (a).
I also understand that $13 \cdot (-3) = - 39 = -39 + 40 = 1 \equiv 1 \mod 40$ (c)

What is not clear to me is what rule is used so that we switch the multiplication from $3$ to $-3$.
$3$ and $-3$ are not multiplicative inverses $\mod 40$.
Was there some rule I am not aware or was what I described in c used?

I just would like to know if there is a specific rule used that allowed to go from $-1$ to $1$ by changing the sign in the lhs of the mod

Bill Dubuque
  • 272,048
Jim
  • 1,589
  • 6
    It is just multiplication by $-1$ on both sides. – arbashn Jul 08 '21 at 11:56
  • @arbashn: So congruence follows the same rules as equality? I thought that the usage of the term equality in regards to congruence was a more general term/analogy, so it did not occur to me that I could multiply by −1. Somehow I can not map in my mind congruence and equality as really equivalent – Jim Jul 08 '21 at 12:10
  • @Jim You can check yourself, really. $$a\equiv-b\pmod{40}$$ means by definition that $a-b$ is divisible by $40$. Does it automatically follow from there that $(-a)-(-b)$ is divisible by $40$? If so, you can freely swap signs on both sides. Does it follow that $7a-7b$ is divisible by $40$? If so, it works to multiply both sides by $7$. Does it follow that $(a-6)-(b-6)$ is divisible by $40$? If so, you can subtract $6$ from both sides. And so on ... – Arthur Jul 08 '21 at 13:47
  • 1
    Just as for equations, congruences are preserved by scaling both sides by an integer $,k.,$ by the Congruence Product Rule in the linked dupe. In particular we can negate congruences by scaling them by $-1$. – Bill Dubuque Jul 08 '21 at 16:47
  • Or, a direct proof: $,a-b = -(-a-(-b)),$ so $,n\mid a-b\iff n\mid -a-(-b),,$ i.e. $!\bmod n!:$ $,a\equiv b\iff -a\equiv -b.,$ Or, we can tweak the linked proof of the Congruence Sum Rule to get a Congruence Difference Rule $,A\equiv a,, B\equiv b\Rightarrow A-B\equiv a-b.,$ This yields the Negation Rule as the special case $,A\equiv 0\equiv a,,$ i.e. it yields $,B\equiv b\Rightarrow -B\equiv -b\ \ $ – Bill Dubuque Jul 08 '21 at 17:06

0 Answers0