# Taking modulo of both sides

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?

$$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).

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

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.

• How is it equivalent to $ax + bm = c$, isnt it $ax - bm = c$? – Michael Munta Aug 1 '19 at 8:15
• Replace $b$ by $-b$. – Wuestenfux Aug 1 '19 at 8:24
• $-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. – fleablood Aug 1 '19 at 14:48

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

• 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. – Michael Munta Aug 1 '19 at 12:49
• 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}$ – David Aug 1 '19 at 13:09
• "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. – fleablood Aug 1 '19 at 14:40
• 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$ – David Aug 1 '19 at 14:43