0
$\begingroup$

Prove The GCD of more than two numbers, defined as that positive common divisor which is divisible by every common divisor, exists and can be found in the following way. Let there n numbers $a_1,a_2,...,a_n$ and define

$D_1=(a_1,a_2),D_2=(D_1,a_3),....,D_{n-1}=(D_{n-2},a_n)$

Then $(a_1,....,a_n)=D_{n-1}$

(a,b) refers to the gcd of a and b

Approach

Proof

Theorem 2-1 states, given any two integers a and b not both zero, there is a unique integer such that

i) $d>0$
ii) $d|a$ and $d|b$
iii) if $d_1$ is any integer such that $d_1|a$ and $d_1|b$, then $d_1|d$

Because we computed $D_{N-2}$, $D_{n-2}$ is divisible by every other divisor of $a_1,a_2,....,a_{n-1}$ by theorem 2-1, so the problem is reduced to considering all the divisors of $D_{n-2}$ and pick the greatest one that also divides $a_n$. This is equivalent to finding $D_{n-1}$, so $D_{n-1}$ by definition is divides $a_1,a_2,a_3....,a_n$

$\endgroup$
  • $\begingroup$ Presumably none of the $a_i$ is allowed to be $0$, else we have to modify the theorem a little. $\endgroup$ – André Nicolas Jun 22 '16 at 0:13
  • $\begingroup$ what is the problem of having $a_1$ as 0? $\endgroup$ – TheMathNoob Jun 22 '16 at 0:15
  • $\begingroup$ At least you would need one of $a_1,a_2$ to be non-zero for $D_1$ to exist. $\endgroup$ – Arthur Jun 22 '16 at 0:19
  • $\begingroup$ Not much. Of course some of the $a_i$ must be non-zero. And if we are unlucky and $a_1=a_2=0$ our algorithm is in trouble. So the statement of the theorem has to be modified a little. $\endgroup$ – André Nicolas Jun 22 '16 at 0:20
  • $\begingroup$ Theorem 2-1 states, given any two integers a and b not both zero. If $a_1=a_2....=a_n$, I would just put $D_{n-1}$ is undefined right? $\endgroup$ – TheMathNoob Jun 22 '16 at 0:21
1
$\begingroup$

Hint $\ $ The general definition is equivalent to

$$d\mid (a_1,a_2,\ldots,a_n)\iff d\mid a_1,a_2,\ldots,a_n$$

The Theorem proves the case $\,n=2.\,$ We can repeatedly apply this binary case to erase all the brackets in the left-associated $D_i$ as follows:

$$\begin{eqnarray} && d\mid (((a,b),c),d)\\ &\iff& d\mid ((a,b),c),d\\ &\iff& d\mid (a,b),c ,d\\ &\iff& d\mid a,b,c ,d\\ &\iff& d\mid (a,b,c ,d)\\ \end{eqnarray}$$

In the same way can erase the brackets from any such association, thus showing the general associativity of the gcd.

$\endgroup$
  • $\begingroup$ so $d| (a,b,c,d)$ based on your definition but how would this show (a,b,c,d)=(((a,b),c),d) $\endgroup$ – TheMathNoob Jun 22 '16 at 2:01
  • $\begingroup$ @TheMathNoob $\ $ If $\,m,n>0\,$ have the same set of divisors $\,d\,$ then $\,m = n\,$ since then $\,m\mid m\,\Rightarrow\,m\mid n,\ $ and $\ n\mid n\,\Rightarrow\,n\mid m.\ $ $\endgroup$ – Bill Dubuque Jun 22 '16 at 2:34
  • $\begingroup$ how do we know here that set of divisors is the same?. You started with a set of divisors d and at then at thend we showed that $d|(a,b,c,d)$ which implies that $(a,b,c,d)$ have those divisor , but do we know that we don't miss any? $\endgroup$ – TheMathNoob Jun 22 '16 at 4:05
  • $\begingroup$ @TheMathNoob The equivalences in the answer show d divides the first iff d divides the second. $\endgroup$ – Bill Dubuque Jun 22 '16 at 4:10
  • $\begingroup$ ok so it goes in both directions. In conclusion the set of divisors is the same. $\endgroup$ – TheMathNoob Jun 22 '16 at 4:16

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.