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$
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$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Could you go into more detail about this? I don't fully understand what you wrote. $\endgroup$ – bert Nov 12 '13 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 '13 at 19:52
0
$\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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Sorry, but where did the c come from? $\endgroup$ – bert Nov 12 '13 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 '13 at 22:08
0
$\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 $$

| cite | improve this answer | |
$\endgroup$
0
$\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.

| cite | improve this answer | |
$\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.