Dividing both sides of congruence 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?
 A: $\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}$
A: 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.
A: 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.
