Sei \(n:=ggT(a,b),\ m:=ggT(a,a+b)\).

Wir nutzen folgende Aussage: Sind \(x,y,z\in\mathbb N\) mit \(x|y\) ("x teilt y") und \(x|z\), dann gilt auch \(x|y+z\) und \(x|y-z.\) (Dies kann leicht bewiesen werden, falls es nicht sofort einleuchtet.)

Es gilt sicher \(n|a,n|b\). Deshalb gilt \(n|a+b\) und somit, weil \(n\) also ein Teiler von \(a\) und \(a+b\) ist, gilt \(n\leq m\).

Analog gilt \(m|a,m|a+b\Longrightarrow m|a+b-a=b\). Also teilt \(m\) sowohl \(a\) und \(b\) und damit \(m\leq n\).

Zusammen ergibt sich \(m=n\), was zu zeigen war.