0

Suppose

$$ac\equiv -b \bmod{n}.$$ Let $c^{-1}$ be modular multiplicative inverse of $c$ modulo $n$.

Eventually, Why we can conclude that

$$a\equiv -bc^{-1} \bmod{n} \;?$$

I read this page but I couldn't found a helpful description about my issue.

Gary
  • 27,290
  • 3
  • 31
  • 53
Jut
  • 159
  • 10
  • By the [Congruence Product Rule](https://math.stackexchange.com/a/879262/242) in the linked dupe, congruences are preserve by scalings, so scaling your first congruence by $c^{-1}$ yields your second congruence. Note $c$ is invertible $\!\bmod n\iff c$ is coprime to $n\ \ $ – Bill Dubuque Dec 31 '22 at 07:54
  • Specifically, apply the following instance of the Product Rule: $$\bmod n\!:\,\ A\equiv B\ \ \&\ \ C\equiv C\ \Rightarrow\ {AC\equiv BC}\qquad$$ where $\,A = ac,\ B = -b,\ C = c^{-1}.\ $ It's the congruence analog of the fact that equation are preserved under scalings (or [application of any *function*](https://math.stackexchange.com/q/805937/242)) – Bill Dubuque Dec 31 '22 at 08:01
  • @BillDubuque $AC=ac\frac{1}{c}$? – Jut Dec 31 '22 at 08:05
  • $AC = (ac)c^{-1} \equiv a(cc^{-1})\ \equiv a(1)\equiv a.\ $ The idea is we are dividing both sides by $c$ by scaling by $c^{-1},\,$ just like for normal equations (congruences are *generalized* equations). – Bill Dubuque Dec 31 '22 at 08:07
  • You can use fractions in modular arithmetic such as $c^{-1} \equiv \dfrac{1}{c}$ but you [need to be extra careful](https://math.stackexchange.com/a/921093/242) to ensure you don't divide by zero (or a zero-divisors), i.e. we can only divide by *invertibles*, so denominators must be coprime to the modulus. – Bill Dubuque Dec 31 '22 at 08:11
  • @BillDubuque I read this from MIT slides: we have $$I)\; a_0(x_0-y_0)\equiv -\sum_{i=1}^ra_i(x_i-y_i) \mod m$$ since $$II)\;\;(x_0\neq y_0)$$ an inverse $(x_0-y_0)^{-1}$ must exist, which implies that $$ III)\;\;a_0\equiv -\sum_{i=1}^ra_i(x_i-y_i)(x_0-y_0)^{-1} \mod m$$ My problem is how we can achieve by this assumption that $I,II$ be true? – Jut Dec 31 '22 at 08:24
  • $c := x_0-y_0$ is invertible $\!\bmod m\iff c\,$ is coprime to $m\ \ $ – Bill Dubuque Dec 31 '22 at 09:00

0 Answers0