1
$\begingroup$

I don't believe there are any counter examples that can be used for this (I think it is true). Could someone help me prove it?

I understand why it's true (if I was right about that), but the proof itself is a bit tricky.

$\endgroup$
0

4 Answers 4

Reset to default
2
$\begingroup$

On one hand, and since everything's positive here, $\;gcd(a,b)\le a,b\;$ , but on the other $\;a\mid a\;\;and\;\;a\mid b\;$ , so

$$a\le gcd(a,b)\le a\implies gcd(a,b)=a$$

$\endgroup$
3
  • $\begingroup$ Could you go into more detail about this? I don't fully understand what you wrote. $\endgroup$
    – bert
    Nov 12, 2013 at 19:50
  • $\begingroup$ since $\;gcd(a,b)\;$ is the largest divisor of both $\;a,b\;$ the first inequality in my answer follows, and since $\;a\;$ is one of those divisors according to the given info, the leftmost inequality in the last line follows, too...so we get equality! $\endgroup$
    – DonAntonio
    Nov 12, 2013 at 19:52
  • $\begingroup$ More generally if $\,a\mid b\,$ then $\,d\mid a,b\iff d\mid a,\,$ so $\,a,b,$ and $\,a\,$ have the same set $S$ of common divisors $\,d,\,$ hence the same greatest common divisor (= max $S$), i.e. apply the universal property characterizing the gcd. $\endgroup$
    – Bill Dubuque
    Nov 30, 2021 at 0:45
1
$\begingroup$

If $a|b$, then there is some integer $n$ such that $b = na$. Now the Euclidian algorithm says that $$ \gcd(a, b) = \gcd(a, na) = \gcd(a, na - na) = \gcd(a, 0) = a $$

$\endgroup$
1
$\begingroup$

Hint: Use the fact that

$gcd(a,b)=d$ iff $gcd(\frac{a}{d},\frac{b}{d})=1$.

Note: This result can be proved using the theorem that states that gcd can be expressed as a linear combination of the numbers.

$\endgroup$
1
-1
$\begingroup$

Suppose that $a,b>0$ and $a|b$.

  1. $a$ is a common divisor of $a,b$.
  2. If $c$ is also a common divisor of $a,b$, then $c|a$.

This is the usual definition of gcd.

$\endgroup$
2
  • $\begingroup$ Sorry, but where did the c come from? $\endgroup$
    – bert
    Nov 12, 2013 at 19:52
  • $\begingroup$ The definition I am using is that $gcd(a,b)$ is the greatest common divisor. That is, it is a common divisor, and it is greatest in the sense that all other common divisors divide it. $\endgroup$
    – vadim123
    Nov 12, 2013 at 22:08

You must log in to answer this question.

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