Division May Fail Modulo N

We know that addition, subtraction, and multiplication are preserved under congruences. That is, if $a\equiv b\pmod{n}$ and $c\equiv d\pmod{n}$, then: $$a+c\equiv b+d\pmod{n}$$ $$a-c\equiv b-d\pmod{n}$$ $$ac\equiv bd\pmod{n}$$

However, it is easy to see that division does not work in congruences (or at least, it does not work in the way we would wish). Consider the easy example: $$2\equiv 20\pmod{6}$$ $$\therefore 1\equiv 10\pmod{6}$$ The first statement is true, but the second statement, which "follows" by dividing both sides by $2$, is not true.

We shouldn't just give up on division just yet! In the above example, even though $1\equiv 10\pmod{6}$ is not true, $1\equiv 10\pmod{3}$ is still true! Thus, we have a weaker congruence, but still something we can work with.

Observe the following: $$0\times 2\equiv 3\times 2\pmod{6}$$ $$1\times 2\equiv 4\times 2\pmod{6}$$ $$2\times 2\equiv 5\times 2\pmod{6}$$ It seems that multiplying by $2$ "cuts out information" by making it impossible to distinguish between $0$ and $3$, between $1$ and $4$, and between $2$ and $5$. This gives us a clue as to how we should modify our claim so that division works in congruences.

In general, we can say the following: if $$ax\equiv bx\pmod{n}$$ then $$a\equiv b\pmod{n/(n,x)}$$

To prove it, we will use the following lemma:

Lemma: If $a|bc$, then $b/(a,b)|bc/a$.

Proof: Since $a|bc$, there exist $a_1, a_2$ such that $a_1a_2=a$, $a_1|b$, and $a_1|c$. Then, $ka=bc$ for some $k$, so $k=\frac{bc}{a}=\frac{b}{a_1}\times\frac{c}{a_2}$. Therefore, $b/a_1|c/a_2$. However, since $a_1|a$ and $a_1|b$, $a_1|(a,b)$. Therefore, $b/(a,b)|b/a_1$, so $b/(a,b)|bc/a$, and we are done proving the lemma.

Now, suppose that $ax\equiv bx\pmod{n}$. Then, $ax-bx=x(a-b)=kn$ for some $k\in\mathbb{Z}$, meaning that $a-b=\frac{kn}{x}$, which is an integer. Thus, $x|kn$. By the lemma, $n/(n,x)|kn/x$. Therefore, $$n/(n,x)|(a-b)$$ $$a\equiv b\pmod{n/(n,x)}$$ and the proof is complete.

As a special note, if $(x,n)=1$, then it follows immediately that division modulo $n$ will work as normal. Thus, for example, if $n$ is a prime number, then as long as $x$ is not a multiple of $n$, then division will work normally modulo $n$.

Suppose qu'il existe un $x$ tel que $ax\equiv b\pmod{n}$. On define la division par le processus trouver la valeur de $x$ qui marche.

La question est, quand est la division défini?

Les valeurs possibles de $x$ sont $\{0,1,\dots,n-1\}$. Donc, on peut trouver $x$ si et seulement si $b\in\{a\cdot0,a\cdot1,\dots,a\cdot(n-1)\}\pmod n$. Et tous les termes en cet ensemble ont le même pgcd avec $n$. En conclusion, nous pouvons trouver un $x$ si et seulement si $(b,n)\vert(a,n)$.

Après avoir réalisé ce fait, on peut diviser de la manière suivante: $ax\equiv b\pmod n\iff\frac{a}{(a,n)}x\equiv\frac{b}{(a,n)}\pmod{\frac{n}{(a,n)}}$, trouver l'inverse $y$ de $\frac{a}{(a,n)}\pmod{\frac{n}{(a,n)}}$ (parce qu'ils sont premiers entre eux), et $x\equiv y\frac{b}{(a,n)}\pmod{\frac{n}{(a,n)}}$. Modulo $n$, les valeurs possibles sont, par exemple, $x,x+\frac{n}{(a,n)},x+\frac{2n}{(a,n)},\dots\pmod n$.