# A statement related to greatest common divisor

Assume $k$, $m$ and $N$ are all positive integers.

Can we have the following identity: \begin{eqnarray} (k\cdot(m,N),N)=(k\cdot m,N), \end{eqnarray} where $(x,y)$ denotes the greatest common divisor of $x$ and $y$.

How to prove it or give a counterexample otherwise?

• Try the special case where all the numbers are powers of $2$. – Lord Shark the Unknown Oct 29 '17 at 6:15
• @Lord Shark the Unknown I have tried this possibility, but it does not seem to be a counterexample. – Smart Yao Oct 29 '17 at 6:19
• How about the case where all numbers are a power of a prime $p$? – Lord Shark the Unknown Oct 29 '17 at 6:20
• @Lord Shark the Unknown For any $p$ power, it is not a counterexample. – Smart Yao Oct 29 '17 at 6:24
• Good, if you can prove it for prime powers, you can then prove it for arbitrary numbers! – Lord Shark the Unknown Oct 29 '17 at 6:25

Write $d=(m,n)$, then exist relatively prime $x$ and $y$ so that $m=dx$ and $n=dy$.

Let $d_1 = (k,y)$ and $d_2 = (kx,y)$, then $$(k(m,n),n) = (kd,dy) =d(k,y) =d\cdot d_1$$ and $$(km,n) = (kdx,dy) = d(kx,y) =d\cdot d_2$$

We need to prove $d_1=d_2$.

Since $d_1\mid k$ we see $d_1\mid kx$ and since $d_1\mid y$ we have $d_1|d_2$.

Since $d_2\mid y$ we see that $(d_2,x)=1$ so by Euclid lemma we have $d_2|k$ so $d_2\mid d_1$.

Conclusion $d_1=d_2$.

Left-hand side of the identity is \begin{eqnarray} \text{LHS}&=&\left(k,\frac{N}{(m,N)}\right)\cdot(m,N)\nonumber\\ &=&\left(k\cdot\frac{m}{(m,N)},\frac{N}{(m,N)}\right)\cdot(m,N)\nonumber\\ &=&\text{RHS}, \end{eqnarray} where the fact that $m/(m,N)$ coprimes with $N/(m,N)$ has been made use of.