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.


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,


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


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


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.


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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.