1
$\begingroup$

According to >this proof<, the author is saying that

$g=\gcd(a,b)$, $g'\in\mathbb{N}$, and $g'=\gcd(a,b)$.

The author then states that $g'|g$ and $g|g'$.

From my understanding, $g'*k_1=a$ and $g*k_2=a$ [where $k_1$ and $k_2$ are integers].

It follows that $g'*k_1=g*k_2$.

But from that, how can one reach the conclusion that $g'|g$ and $g|g'$?

Edit:

The given definition of Greatest Common Divisor:

$g$ is the greatest common divisor of a and b, where $a$ and $b$ are non-zero integers if:

  1. $g|a$ and $g|b$

  2. if $c$ is any integer such that $c|a$ and $c|b$, then $c\leq{g}$

Edit2:

I'm assuming that $g$ and $g'$ are some greatest common divisors of $a$ and $b$.

$\endgroup$
  • 1
    $\begingroup$ g and g' are same numbers... $\endgroup$ – windircurse Oct 9 '16 at 22:04
  • $\begingroup$ @DietrichBurde But we don't know that the GCD is unique. Maybe a pair of integers has two GCD. I think the OP is trying to prove it's unique. $\endgroup$ – Stefan4024 Oct 9 '16 at 22:07
  • $\begingroup$ When proving the uniqueness of a number (like $g = \gcd(a, b)$), for the purpose of contradiction, one supposes that another number exists ($g' = \gcd(a, b)$) and then goes on to conclude that the two numbers are, in fact, equal ($g = g'$) $\endgroup$ – Namaste Oct 9 '16 at 22:08
  • $\begingroup$ @Stefan4024 I only commented on the first line: $g=gcd(a,b)=g'$. There is no way to avoid the conclusion $g=g'$, and hence $g\mid g'$, $g'\mid g$. $\endgroup$ – Dietrich Burde Oct 9 '16 at 22:10
  • $\begingroup$ Ignoring that $g$ and $g'$ are obviously equal because there exists only one gcd for any two numbers, I'm looking for how the conclusion is reached from the point that one only knows that $g=gcd(a,b)$ and $g'=gcd(a,b)$. How is it proven, that $g'|g$ and $g|g'$ from that point? $\endgroup$ – luis_garibay Oct 9 '16 at 22:11
3
$\begingroup$

Your statement is rather ambiguous. You probably want to show that if $g$ and $g'$ both satisfy the requirements for being a greatest common divisor of $a$ and $b$, then $g=g'$. (You cannot use $g=\gcd(a,b)$ until you have proved uniqueness, so this is why your statement is ambiguous.)

This depends on what definition of greatest common divisor you use. There are two common ones, when restricting ourselves to the natural numbers.

First definition. The greatest common divisor of $a$ and $b$ (not both $0$) is the largest common divisor of $a$ and $b$.

With this definition, there is no problem in stating uniqueness.

Second definition. A number $g$ is a greatest common divisor of $a$ and $b$ if

  1. $g\mid a$ and $g\mid b$
  2. for all $c$, if $c\mid a$ and $c\mid b$, then $c\mid g$

With this definition, uniqueness must be proved. Thus, since you're asking, I'll assume this is your definition.

Now, suppose $g$ and $g'$ both satisfy the requirements above.

Since $g\mid a$ and $g\mid b$ by 1 applied to $g$, we get, from 2 applied to $g'$ with $c=g$, that $g\mid g'$.

Since $g'\mid a$ and $g'\mid b$ by 1 applied to $g'$, we get, from 2 applied to $g$ with $c=g'$, that $g'\mid g$.

From here the proof of $g=g'$ follows easily.

$\endgroup$
  • $\begingroup$ This is what I was looking for. Thank you. $\endgroup$ – luis_garibay Oct 9 '16 at 22:43
1
$\begingroup$

As $g'$ is a greatest common divisor of $a,b$ we have that $g' \mid a$ and $g' \mid b$, by definition. Now by the definition of a greatest common divisor $g$ is divided by any number that divides both $a$ and $b$, hence $g' \mid g$. Similarly we prove that $g \mid g'$, which implies that $g = g'$.

$\endgroup$
  • $\begingroup$ The definition of a greatest common divisor is only that d=gcd(a,b) if: 1) d|a and d|b; and 2) if c is any integer such that c|a and c|b, then c≤d. So, how does one reach the point that the gcd d is divisible by any integer that divides a and b? $\endgroup$ – luis_garibay Oct 9 '16 at 22:15
  • $\begingroup$ @luis_garibay The definition of a greatest common divisor is only that d=gcd(a,b) if: 1) d|a and d|b; and 2) if c is any integer such that c|a and c|b, then $c$ divides $d$ $\endgroup$ – Stefan4024 Oct 9 '16 at 22:19
0
$\begingroup$

The proof shows that a gcd exists, then goes on to show that there can only be one gcd. He says to suppose that both $g$ and $g'$ are gcd's of $a$ abd $b$.

As egreg stated, the normal definition of gcd(a,b) is

  1. $g\mid a$ and $g\mid b$
  2. for all $c$, if $c\mid a$ and $c\mid b$, then $c\mid g$

If that's the case, it follows that $g \mid g'$ and $g' \mid g$. He argues that, clearly then, $g = g'$. Well, to be truely picky, he's wrong. If we are using the set of all integers, then it follows that $ g = \pm g'$. In a ring $R$, $u \in R$ is a unit if $u^{-1}$ exists in $R$. The units of the set of integers are $1$ and $-1$. If $x,y \in R$ can be expressed as $s = uy$, where $u$ is a unit in $R$, then $x$ and $y$ are called associates. So it would be more correct to say that any two gcd's of $a$ and $b$ are associates of each other.

To be honest, I have never seen your definition before:

  1. $g\mid a$ and $g\mid b$
  2. for all $c$, if $c\mid a$ and $c\mid b$, then $c \le g$

but it does work for the set of integers. And we could argue that,if $g$ and $g'$ are gcd's of $a$ and $b$, then $g \le g'$ and $g' \le g$. It would follow that $g=g'$.

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