# $a\equiv b\pmod{n}\iff a/x\equiv b/x\pmod{n/\gcd(x,n)}$ for integers $a,b,x~(x\neq 0)$ and $n\in\Bbb Z^+$?

I'm trying to prove/disprove the following:

If $$a,b,x$$ be three integers (where $$x\neq 0$$) such that $$x\mid a,b$$ and $$n$$ be a positive integer, then the following congruence holds:

$$a\equiv b\pmod{n}\iff a/x\equiv b/x\pmod{n/\gcd(x,n)}$$

My intuition says it's true and below here is my attempt at a proof. Can the community verify if it's correct? Thanks.

Proof.

Necessity: If $$a/x\equiv b/x\pmod{n/\gcd(x,n)}$$, then we can write $$(a-b)/x=nl/\gcd(x,n)$$ for some integer $$l$$, so that we have,

$$(a-b)/n = lx/\gcd(x,n) = l\ast (x/\gcd(x,n))$$

Since $$\gcd(x,n)\mid x$$ by definition of $$\gcd$$, we see that $$(a-b)/n$$ is an integer and hence $$a\equiv b\pmod n$$

Sufficiency: If $$a\equiv b\pmod n$$, then we can write $$a-b=np$$ for some integer $$p$$, so that we have,

\begin{align}a-b=np&\implies (a-b)\gcd(x,n)=np\gcd(x,n)\\&\implies \frac{(a-b)\gcd(x,n)}{nx}=\frac{p\gcd(x,n)}{x}\end{align}

By Bezout's Lemma, there exists integers $$b_1,b_2$$ such that $$\gcd(x,n)=b_1x+b_2n$$, so we have,

$$\frac{(a-b)\gcd(x,n)}{nx}=\frac{p(b_1x+b_2n)}{x}=pb_1+\frac{b_2np}{x}=pb_1+b_2\frac{a-b}{x}$$

Since $$x\mid a,b$$, we have $$x\mid a-b$$ and so we can write $$a-b=xq$$ for some integer $$q$$. Then,

$$\frac{(a-b)\gcd(x,n)}{nx}=pb_1+qb_2$$

So, we conclude that $$\dfrac{(a-b)\gcd(x,n)}{nx}$$ is an integer, i.e, $$\dfrac{(a-b)/x}{n/\gcd(x,n)}$$ is an integer, so $$\frac ax-\frac bx$$ is divisible by $$n/\gcd(x,n)$$ which shows that $$a/x\equiv b/x\pmod{n/\gcd(x,n)}$$

Your proof looks correct. An easier way to do the sufficiency statement would be as follows:

We have $n|(a-b)$ and $x|(a-b)$, therefore if we let $L= lcm(n,x)$ then $L|(a-b)$. Now let $a-b = Lk$ for an integer $k$. Now divide through by $x$ and use the fact that $nx = gcd(n,x)lcm(n,x)$ to get $(a-b)/x = Lk/x = \frac{n}{gcd(n,x)} k$, which implies $a/x=b/x$ mod $\frac{n}{gcd(n,x)}$

More simply, write $\ \bar a = a/x,\ \bar b = b/x\$ and $y = \bar a - \bar b.\$ Then we get a $1$-line proof:

$$\,n\mid a\!-\!b=xy\iff n\mid xy,ny\color{#0a0}\iff n\mid (xy,ny)\!\color{#c00}{\overset{\rm D}{=}}\!(x,n)y \iff n/(x,n)\mid y$$

We employed the universal property $\color{#0a0}\iff$ along with the $\,\color{#c00}{\overset{\rm D}{=}}$ Distributive Law of the gcd.

Assume that $a \equiv b \pmod n$. Then there exist an integer $k$ such that $a-b = kn$. Now as $x$ divides the RHS we will have $\frac{x}{gcd(x,n)} \mid k$. So now we have:

$$\frac{a}{x} - \frac{b}{x} = \frac{k}{\frac{x}{gcd(x,n)}} \cdot \frac{n}{gcd(x,n)}$$

So as $\frac{k}{\frac{x}{gcd(x,n)}} \in \mathbb{Z}$ we have that $\frac{a}{x} \equiv \frac{b}{x} \pmod {\frac{n}{gcd(x,n)}}$

Now assume that $\frac{a}{x} \equiv \frac{b}{x} \pmod {\frac{n}{gcd(x,n)}}$. Then there exist integer $k$ such that $\frac{a}{x} - \frac{b}{x} = k \cdot \frac{n}{gcd(x,n)}$. Multiply by $x$ and you will get:

$$a - b = \left(k \cdot \frac{x}{gcd(x,n)}\right) \cdot n \implies a \equiv b \pmod n$$

Therefore as we proved both sides we get that:

$$a \equiv b \pmod n \iff \frac{a}{x} \equiv \frac{b}{x} \pmod{\frac{n}{gcd(x,n)}} \quad \text{, where: }x=gcd(a,b)$$