Proposition: Greatest Common Divisor of More Than Two Numbers

Let $n_1,n_1,\ldots,n_k\in\mathbb Z$ be integers. The simultanous greatest common divisor of all these numbers can be calculated by the recursive formula

$$\gcd(n_1,\ldots,n_k):=\gcd(\gcd(n_1,\ldots,n_{k-1}),n_k).$$

This calculation is independent of the order, in which the recursive formula is used, following the associativity and commutativity of the $\gcd$. In particular, for any integers $a,b,c\in\mathbb Z$ we have $$\gcd(\gcd(a,b),c))=\gcd(a,\gcd(b,c))$$ and $$\gcd(a,b)=\gcd(b,a).$$

Proofs: 1

Proofs: 1
Propositions: 2 3


Thank you to the contributors under CC BY-SA 4.0!

Github:
bookofproofs


References

Bibliography

  1. Scheid Harald: "Zahlentheorie", Spektrum Akademischer Verlag, 2003, 3rd Edition
  2. Landau, Edmund: "Vorlesungen über Zahlentheorie, Aus der Elementaren Zahlentheorie", S. Hirzel, Leipzig, 1927