This question already has an answer here:

This is my proof

Let $m$ be $\gcd(ka,kb)$ then exists $s$ and $t$ such that

$ska+ tkb = m => k(sa+tb) = m $

$=> sa + tb = m/k$ (1)

since (1) is linear combination of $a$ and $b$ and $m$ is smallest positive linear combination of $ka$ and $kb$ => $m/k$ is smallest positive then $\gcd(a,b) = m/k$.

Is this proof is good enough to prove $\gcd(ka,kb)=k\cdot \gcd(a,b)$


marked as duplicate by GAVD, Especially Lime, José Carlos Santos, Namaste, Théophile Sep 28 '17 at 14:40

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Why would m being the smallest linear combination of ka and kb imply that m/k is the smallest linear combination of a and b? Isn't that what you are proving. Also, in using Bezout's lemma, are you sure that you haven't assumed the result to begin with? Maybe the proof of Bezout's lemma doesn't require knowing this, but are you sure it doesn't? $\endgroup$ – fleablood Sep 28 '17 at 14:59
  • $\begingroup$ you are right.This proof not good enough $\endgroup$ – xuoimai Oct 3 '17 at 9:56

Let $a=p_{1}^{q_{1}}p_{2}^{q_{2}}...p_{k}^{q_{k}}$ and $b=p_{1}^{r_{1}}p_{2}^{r_{2}}...p_{k}^{r_{k}}$ be their respective prime decompositions.

Thus, $gcd(a,b)=p_{1}^{min(q_{1},r_{1})}p_{2}^{min(q_{2},r_{2})}...p_{k}^{min(q_{k},r_{k})}$

Now, if $k=p_{1}^{s_{1}}p_{2}^{s_{2}}...p_{k}^{s_{k}}$ , then

$ka=p_{1}^{s_{1}+q_{1}}p_{2}^{s_{2}+q_{2}}...p_{k}^{s_{k}+q_{k}}$ and $kb=p_{1}^{s_{1}+r_{1}}p_{2}^{s_{1}+r_{1}}...p_{k}^{s_{k}+r_{k}}$

Now, note that $min(i+x,j+x)=x+min(i,j)$. Hence,

$$gcd(ka,kb)=p_{1}^{min(s_{1}+q_{1},s_{1}+r_{1})}p_{2}^{min(s_{2}+q_{2},s_{1}+r_{1})}...p_{k}^{min(s_{k}+q_{k},s_{k}+r_{k})}$$ $$=(p_{1}^{s_{1}}p_{2}^{s_{2}}...p_{k}^{s_{k}})(p_{1}^{min(q_{1},r_{1})}p_{2}^{min(q_{2},r_{2})}...p_{k}^{min(q_{k},r_{k})})$$ $$=k.gcd(a,b)$$ Hence proved.

Basically, this has the simple intuition that by the definition of gcd, the gcd is the collection of the common factors. So, when we replace $a$ by $ka$ and $b$ by $kb$, there is one extra factor added to this collection, and that factor is nothing but $k$. Hence, we get the result.


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