Welcome guest
You're not logged in.
435 users online, thereof 0 logged in

Proposition: Greatest Common Divisor

Let \(a,b\) be integers and let \(D_{a,b}\) be the set of all common divisors of \(a\) and \(b\):

\[D_{a,b}:=\left\{d\in\mathbb N : d\mid a\wedge d\mid b\right\}.\]

\(D_{a,b}\) has a unique maximum $\max(D_{a,b})$, called the greates common divisor of \(a\) and \(b\), denoted by

\[\gcd(a,b):=\max(D_{a,b}).\]

We have $\gcd(a,b)\mid a$ and $\gcd(a,b)\mid b.$ Moreover, any divisor $d$ dividing both, $d\mid a$ and $d\mid b$ also divides their greatest common divisor $d\mid \gcd(a,b).$ For this reason, since $d\mid 0$ for all integers $d\neq 0$, we set \(\gcd(0,0):=0\).

| | | | | created: 2015-05-30 09:12:47 | modified: 2019-03-21 13:38:59 | by: bookofproofs | references: [701], [1272]

1.Proof: (related to "Greatest Common Divisor")


This work was contributed under CC BY-SA 3.0 by:

This work is a derivative of:

(none)

Bibliography (further reading)

[1272] Landau, Edmund: “Vorlesungen ├╝ber Zahlentheorie, Aus der Elementaren Zahlentheorie”, S. Hirzel, Leipzig, 1927

[701] Scheid Harald: “Zahlentheorie”, Spektrum Akademischer Verlag, 2003, 3. Auflage

FeedsAcknowledgmentsTerms of UsePrivacy PolicyImprint
© 2018 Powered by BooOfProofs, All rights reserved.