this boring and i dont like to do this on my course
== Proof of correctness ==
Suppose ''a'' and ''b'' are the natural numbers whose gcd has to be determined. And suppose the remainder of the division of ''a'' by ''b'' is ''r''. Therefore ''a'' = ''qb'' + ''r'' where ''q'' is the quotient of the division.
Any common divisor of ''a'' and ''b'' is also a divisor of ''r''. To see why this is true, consider that ''r'' can be written as ''r'' = ''a'' − ''qb''. Now, if there is a common divisor ''d'' of ''a'' and ''b'' such that ''a'' = ''sd'' and ''b'' = ''td'', then ''r'' = (''s''−''qt'')''d''. Since all these numbers, including ''s''−''qt'', are whole numbers, it can be seen that ''r'' is divisible by ''d''.
This is boring i hate this stuff lol
The above analysis is true for any divisor ''d''; thus, the greatest common divisor of ''a'' and ''b'' is also the greatest common divisor of ''b'' and ''r''. Therefore it is enough if we continue searching for the greatest common divisor with the numbers ''b'' and ''r''.
Since ''r'' is smaller in [[absolute value]] than ''b'', we will reach ''r'' = 0 after finitely many steps.
