0
$\begingroup$

I need to show that:

If $a\mid b$ then $\gcd(a,c) \leq \gcd(b,c)$ where $a,b,c$ are positive integers.

I've come up with this, but I'm not 100% sure that it's correct:

Assume $a\mid b$, then $a \leq b$. Multiply both sides by an integer, $x$, such that $ax \leq bx$. Then add $cy$ for positive integer, $c$, and some integer, $y$, to both sides such that $ax + cy \leq bx + cy$. Then by EEA, $ax + cy = \gcd(a,c)$ and $bx + cy = \gcd(b,c)$. Therefore, $\gcd(a,c) \leq \gcd(b,c)$

$\endgroup$
  • 1
    $\begingroup$ Be-careful $3 \mid -3$ but $3 > -3$ $\endgroup$ – alkabary Jun 14 '15 at 21:32
  • $\begingroup$ Hint for the original question: If $d\mid a$ then $d\mid b$. $\endgroup$ – Thomas Andrews Jun 14 '15 at 21:32
  • $\begingroup$ You can write $\gcd(b,c)=bx+cy$, but one among $x$ and $y$ is negative. $\endgroup$ – egreg Jun 14 '15 at 21:33
  • $\begingroup$ @alkabary Is it reasonable to assume $a|b$ implies $a \leq b$ if both a and b are positive integers? $\endgroup$ – DayDreamerz Jun 14 '15 at 21:34
  • 1
    $\begingroup$ yes @DayDreamerz, I just didn't see + integers $\endgroup$ – alkabary Jun 14 '15 at 21:34
3
$\begingroup$

This doesn’t work, I’m afraid. The extended Euclidean algorithm gives you some pair of integers $x$ and $y$ such that $ax+cy=\gcd(a,c)$, but there’s no guarantee that $bx+cy=\gcd(b,c)$ for that same pair of integers.

HINT: Since $a\mid b$, you know that for every $d$, if $d\mid a$, then $d\mid b$.

$\endgroup$
  • $\begingroup$ Ah okay, how about, consider $\gcd(b,c) = bg + ck$ for some integers $g$ and $k$. If $d|a$ then $d|b$ by TD, and $d|c$ then $d | (bx + cy)$ for all integers $x,y$ by DIC. Then, let $x = g$ and $y = k$. Then $d | (bg + ck) = \gcd(b,c)$. Thus, $\gcd(a,c) = d \leq \gcd(b,c)$ $\endgroup$ – DayDreamerz Jun 14 '15 at 21:41
  • 1
    $\begingroup$ @DayDreamerz: You can do it this way, but you’re making it far more complicated than is necessary. Just let $d=\gcd(a,c)$. Then $d\mid a$ and $d\mid c$, so $d\mid b$ and $d\mid c$, and therefore $d\mid\gcd(b,c)$. $\endgroup$ – Brian M. Scott Jun 14 '15 at 21:43
  • $\begingroup$ Oh my gosh, that is much more simpler than the spaghetti I came up with. Thank you very much for your help! $\endgroup$ – DayDreamerz Jun 14 '15 at 21:45
  • 1
    $\begingroup$ @DayDreamerz: You’re very welcome! $\endgroup$ – Brian M. Scott Jun 14 '15 at 21:45
0
$\begingroup$

Let $\,b = an.\,$ If $\,d\mid a,c\,$ then $\,d\mid an,c,\,$ so the set $S = $ common divisors of $\,a,c\,$ is a subset of $T = $ common divisors of $\,an,c,\ $ so $\ S\subseteq T\Rightarrow \max S \le \max T,\ $ i.e $\ (a,c)\le (an,c).$


Alternatively: $\,\ (a,c)\mid an,c\,\Rightarrow\,(a,c)\mid(an,c),\,$ therefore $\ (a,c)\le (an,c).$

$\endgroup$

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.