1
$\begingroup$

On the following page at the bottom there is an algorithm for calculating modular inverses. In the proof I am confused with the line 'Taking both sides modulo $m$'. How does that work getting a congruence from the above equation?

$\endgroup$
1
$\begingroup$

$j = k\,\Rightarrow\, \color{#0a0}{j\bmod m} = k\bmod m\,$ by $\,f(x) = x\bmod m\,$ is a function so $\,j=k\,\Rightarrow\, f(j) = f(k)$.

Your special case has $\, \color{#c00}0 \le \underbrace{m\bmod i}_{\Large\color{#0a0} j} < i < \color{#c00}m\,$ so $\,\color{#0a0}{j\bmod m = j}\,$ is already reduced $\!\bmod \color{#c00}m$

Remark $ $ Note that the modular inversion algorithm discussed there is the same as the algorithm I discussed in your prior question, i.e. Gauss's modular inversion algorithm (in non-fractional form).

$\endgroup$
  • $\begingroup$ Yes, I know it is the same. Was interesting to find another reference. :) $\endgroup$ – Michael Munta Aug 1 '19 at 15:06
0
$\begingroup$

The congruence $a\cdot x\equiv c\mod m$ means $m$ divides $a\cdot x -c$ and is thus equivalent to $a\cdot x+b\cdot m = c$ for some integer $b$. In this way, one can get a congruence from an equation and vice versa.

$\endgroup$
  • $\begingroup$ How is it equivalent to $ax + bm = c$, isnt it $ax - bm = c$? $\endgroup$ – Michael Munta Aug 1 '19 at 8:15
  • $\begingroup$ Replace $b$ by $-b$. $\endgroup$ – Wuestenfux Aug 1 '19 at 8:24
  • $\begingroup$ $-b$ is an integer if and only if $b$ is an integer. We don't have to specify (and we don't care) whether the integer is positive or negative (and if $b$ is negative $-b$ would be positive). So "$ax +bm =c$ for some integer $b$" is the exact same sentence as "$ax - bm=c$ for some integer $b$" The only difference is that the integer in the second sentence is the opposite sign as the integer in the first. $\endgroup$ – fleablood Aug 1 '19 at 14:48
-1
$\begingroup$

If $x=y$ then $x \equiv y (mod m)$, so far, so good.

Now, let's say we have what I think you may be struggling with $ax + bm = y$

Then $ax + bm \equiv y\space (mod m)$,

but $bm \equiv 0 \space (mod m)$, so that's why we get $ax \equiv y \space (mod m)$ To get there, you may want to subtract $bm$ from both sides

$\endgroup$
  • $\begingroup$ I understand that if $ax + bm = c$ it is $ax\equiv c$ (mod m) and also $bm \equiv c$ (mod x) for example. I am confused with take both sides modulo $m$ in a normal equation and then resulting in a congruence. I mean is it possible to do modulo on both sides of the equation in other cases? When equation is not in the form of division algorithm. $\endgroup$ – Michael Munta Aug 1 '19 at 12:49
  • $\begingroup$ An equality in $\mathbb{Z}/n\mathbb{Z}$ is called a congruency. Saying $5 \equiv 15 \space (mod m)$ is the same as saying $5=15$ in $\mathbb{Z}/n\mathbb{Z}$ $\endgroup$ – David Aug 1 '19 at 13:09
  • $\begingroup$ "I mean is it possible to do modulo on both sides of the equation in other cases?" Yes. If $a = b$ or $a \equiv b \mod n$ then $a \mod n = b\mod n$. I think the author was assuming, rightly or wrongly, that would be obvious to the reader. $\endgroup$ – fleablood Aug 1 '19 at 14:40
  • $\begingroup$ Sure!. You can transform any $a=b$ equation into a $a \mod n = b\mod n$ equation. Just note that you will be adding extra solutions (the "if" implication works only one way) For example, solutions of $2x=10$ are indeed solutions of $2x \equiv 10 (\mod 3)$, but solutions of $2x \equiv 10 (\mod 3)$ may or may not be solutions of $2x = 10$ It's similar to transforming $a=b$ into $a^2=b^2$ $\endgroup$ – David Aug 1 '19 at 14:43

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.