Dividing both sides of congruence

Question

I am having trouble understanding division in modular arithmetic. I didn't manage to find any good resources online on that.

Usually it is explained like this:

If we have $a \equiv b$ (mod $n$) with $a = ka'$ and $b = kb'$. Then by definition we have $k(a' - b') = qn$ for some integer $q$. Then they say that from this last equation we are sure that $n$ divides $(a' - b')$, but not $k$. Why is that?

Also it is said that one should divide $n$ with the $GCD(n,k)$, but I can not see how that comes into play.

Can anyone show modular division more generally or provide a good resource to study it?

Answer 1

$\begin{align} \bmod n&\!:\ kx\equiv ka\\[.2em] \iff\ \ \ \, n&\mid k\,(x-a)\\[.2em] \iff \color{#c00}{n/d}&\mid (\color{#c00}{k/d})(x-a),\ \ {\rm by\ cancelling}\ \ d = \gcd(n,k)\ \ {\rm from\ prior}\\[.2em] \iff n/d&\mid x-a,\ \ {\rm by}\ \ {\rm Euclid's\ Lemma}\ \ \&\ \gcd(\color{#c00}{n/d,k/d}) = \gcd(n,k)/d = \color{#c00}1\\[.2em] \iff \bmod n/d&\!:\, x\equiv a \end{align}$

Answer 2

This is a useful link

I have made some rough calculations assuming $a,b$ both non zero, this may help you. As given $a\equiv b(\mod n)$ so clearly $b<a$ as all are natural numbers further the residue of the division implies $n \not | a$.

If possible suppose that, $n|k$ where $a=ka',b=kb'$ as defined in your problem. Then $n|ka'\implies n|a$ this contradicts the above mentioned fact.

For the second one, we see that $gcd(k,\frac{n}{gcd(n,k)})=1$ provided $gcd(n,k)\ne 1$, then the quantity $\frac{n}{gcd(n,k)}$ is relatively prime to $k$ and hence doesnot divide $k$.

Hope this works.

Answer 3

I will give you a proof that was very easy for me to understand when I was first studying congruences.

From $a \equiv b \text{ (mod } n)$ it follows that $a-b=qn$ for some $q \in \mathbb{Z}$. Dividing both sides by $k$ we get $$a'-b'=q \cdot \frac{n}{k}$$ If we write $n$ and $k$ as $n=\text{GCD(}n,k)\cdot n_1$ and $k=\text{GCD(}n,k)\cdot k_1$, then we get $$a'-b'=q \cdot \frac{\text{GCD(}n,k)\cdot n_1}{\text{GCD(}n,k)\cdot k_1} = q \cdot \frac{n_1}{k_1}$$

Since $n_1$ and $k_1$ are mutually prime ($\text{GCD(}n_1,k_1)=1$) and we know that $a'-b'$ must be an integer, we conclude that $k_1 | q$ and $\frac{q}{k_1}$ is an integer.

Thus, $a'-b'=\frac{q}{k_1}\cdot n_1$ which is equivalent to $$a' \equiv b' \text{ (mod } \frac{n}{\text{GCD(}n,k)})$$

To illustrate why the division by GCD is necessary I will show an example. Let $a=6, b=12, n=2$. We have the congruence $$6 \equiv 12 \text{ (mod } 2)$$ which is the same as $6-12=-3 \cdot 2$. We can see that $q=-3$. Now, if we divide both sides with $k=2$, we get $3-6=-3$, and $2\not|-3$.

Therefore, the congruence $3 \equiv 6 \text{ (mod } 2)$ does not hold.