Proof that gcd(n1, .... , nk) = gcd(n1, gcd(n2,...,nk))

Question

I should proof $\gcd(n_1, .... , n_k) = \gcd(n_1, \gcd(n_2,...,n_k))$

I did that:

$d = \gcd(n_1, .... , n_k) \rightarrow d | n_1, ..., d| n_2$

$e = \gcd(n_1, \gcd(n_2,...,n_k)) \rightarrow e|n_1, e|n_2,... ,e|n_k$

and if $e$ divides $n_1,n_2,...,n_k$, then $d|e$ and $d = e$.

Is that right?

Answer 1

This is almost right. To get it right, you have to use that $d$ is the greatest common divisor of $n_1, \dots, n_k$. In particular, if $x$ is a common divisor of $n_1, \dots, n_k$ then $x \operatorname{|} d$.

Here's how I would redact this proof :

Let $d = gcd(n_1, \dots, n_k)$ and $e = gcd(n_1, gcd(n_2,\dots, n_k))$

claim : $d$ divides $e$

Since $d$ is a common divisor of $n_2,\dots,n_k$, we have $d \operatorname{|} gcd(n_2,\dots,n_k)$. Hence $d$ is a common divisor of $n_1$ and $gcd(n_2,\dots,n_k)$, whence $d \operatorname{|} e$.

claim: $e$ divides $d$

Since $e$ divides $gcd(n_2,\dots,n_k)$, $e$ is a common divisor of $n_2,\dots,n_k$. But $e$ is also a divisor of $n_1$. Hence, $e \operatorname{|} d$.

Since $d \operatorname{|} e$ and $e \operatorname{|} d$, we have $\boxed{d = e}$.

Answer 2

OK, set $d=\gcd(n_1, n_2, \ldots, n_k)$ and $d'=\gcd(n_1, \gcd(n_2, \ldots, n_k))$.

The $\gcd$ $d$ of a set $A$ of numbers has two defining properties:

1. $\forall a \in A: d | a$ (or abreviated $d|A$).
2. If $d'$ is such that $d'|A$ then $d'|d$ (maximality)

$d | n_1$ as part of the definition.

Also, $d | n_2,\ldots n_k$ likewise and so $d| gcd(n_2, \ldots, n_k)$ as the gcd of a set of numbers is the "maximal" (in divisor sense) common divisor. As $d | n_1$ and $d| gcd(n_2, \ldots, n_k)$ we have $d|d'$ again by this "maximality".

On the other hand $d'|n_1$ by definition, $d'| gcd(n_2, \ldots, n_k)$ so $d'|n_2, n_3, \ldots, n_k$ as $|$ is transitive and $gcd(n_2, \ldots, n_k) | n_2$ etc. Again by "maximality", we have $d'|d$ and when we have $d|d'$ and $d'|d$ and by definition both are positive integers we have $d=d'$.

The proof is completely analogous in any lattice (here we have that the lattice $(\Bbb N, |)$ with $n \land m = \gcd(n,m)$, $n \lor m = \operatorname{lcm}(n,m)$ etc.) and allows us to go from binary sups to sups of tuples/sets.