<p>Can someone explain to me why Euclid’s algorithm ‘magically’ gives you the GCD. I understand how to use the algorithm, but why does it work? Thanks.</p>
<p>[Euclidean</a> algorithm - Wikipedia, the free encyclopedia](<a href=“Euclidean algorithm - Wikipedia”>Euclidean algorithm - Wikipedia)</p>
<p>Pretty nice proof.</p>