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?

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


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.