Let $c,d,m,k ∈ \mathbb{Z}$ such that $m ≥ 2$ and $k$ is not zero. Let $f = \gcd(k,m)$. If $c \equiv d \pmod m $ and $k$ divides both $c$ and $d$, then $$ \frac{c}{k} \equiv \frac{d}{k} \left({\bmod} \frac{m}{f}\right)$$

My lecturer asked me to prove this statement, as an exercise.

To prove this, I started by considering the two cases:

  1. If suppose $k$ and $m$ are relatively prime, meaning that the $f=1$, then by the Congruence and Division Cancellation Law, we know that $ \frac{c}{k} \equiv \frac{d}{k} \pmod m$. For this case, $ \frac{c}{k} \equiv \frac{d}{k} \big({\bmod} \frac{m}{f}\big)$ must be true since $\frac{m}{f} = \frac {m}{1} = m$
  2. Now, it remains to prove the other case, where $k$ and $m$ are not relatively prime. By the definition of divisibility, we know that $c \equiv d \pmod m $ is equivalent of saying $c = d+mj$. We divide both sides by the common divisor k, gives us $\frac{c}{k} = \frac{d}{k} + \frac{mj}{k}$. Now, we consider $f = \gcd(k,m)$. This implies that there must exists and integer i, such that $k=lf$, for some integer $l$. Thus, $\frac{c}{k} = \frac{d}{k} + \frac{mj}{k} = \frac{d}{k} + \frac{mj}{lf}$. (Is this true? -- since $l$ does not divide $m$ and the fact that it has to be integer, then $l$ must divide $j$)

I have no idea where to continue. Am I on the right track? Any hints to finish the proof?

  • 1
    $\begingroup$ $c\equiv d\pmod m$ is coded as c\equiv d\pmod m. I changed it. Notice that with (\textrm{mod}\ m) the space between "mod" and $m$ need not be added manually and the space before the left parenthesis is missing. (And note that if more than one character follows \pmod, then {braces} are needed: \pmod 21 appears as $\pmod 21$, but \pmod{21} appears as $\pmod{21}$. ${}\qquad{}$ $\endgroup$ Oct 25, 2014 at 1:37

1 Answer 1


Since $(k,m)=f$, we get $(k/f,m)=1$ so there is $x$ such that $(k/f)\cdot x\equiv 1\pmod m$ holds. Especially, we get $k\cdot(x/f)\equiv 1\pmod {m/f}$.

From $cx\equiv dx\pmod m$ we can derive $c\cdot (x/f)\equiv d\cdot (x/f)\pmod {m/f}$ and you can check that $c\cdot(x/f)\equiv c/k\pmod {m/f}$.

  • $\begingroup$ hi! can you explain to me how can you get from $(k/f)\cdot x\equiv 1\pmod m$ to this: $k\cdot(x/f)\equiv 1\pmod {m/f}$. $\endgroup$
    – Joshua
    Oct 25, 2014 at 0:47
  • $\begingroup$ @Aaron Since $m\mid (kx/f-1)$ implies $(m/f)\mid (kx/f-1)$... :) $\endgroup$
    – Hanul Jeon
    Oct 25, 2014 at 0:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .