(related to Algorithm: Greatest Common Divisor (Python))
We want to show that if \(a\), \(b\) are integers, with \(a\neq 0\) or \(b\neq \). The algorithm calculates correctly the greatest common divisor of \(a\) and \(b\).
\[\begin{array}{rclclcl} a & = & q_0\cdot b & + & r_1 & \text{with} & 0 < r_1 < b\\ b & = & q_1\cdot r_1 & + & r_2 & \text{with} & 0 < r_2 < r_1\\ r_1 & = & q_2\cdot r_2 & + & r_3 & \text{with} & 0 < r_3 < r_2\\ &\vdots&\\ r_{n-3} & = & q_{n-2}\cdot r_{n-2} & + & r_{n-1} & \text{with} & 0 < r_{n-1} < r_{n-2}\\ r_{n-2} & = & q_{n-1}\cdot r_{n-1} & + & r_{n} & \text{with} & 0 < r_{n} < r_{n-1}\\ r_{n-1} & = & q_{n}\cdot r_{n} \end{array}\]
\[\begin{array}{rclclcl} a & = & q_0\cdot b & + & a\mod b & \text{with} & 0 < r_1 < b\\ b & = & q_1\cdot r_1 & + & b\mod r_1 & \text{with} & 0 < r_2 < r_1\\ r_1 & = & q_2\cdot r_2 & + & r_1\mod r_2 & \text{with} & 0 < r_3 < r_2\\ &\vdots&\\ r_{n-3} & = & q_{n-2}\cdot r_{n-2} & + & r_{n-3}\mod r_{n-2} & \text{with} & 0 < r_{n-1} < r_{n-2}\\ r_{n-2} & = & q_{n-1}\cdot r_{n-1} & + & r_{n-2}\mod r_{n-1} & \text{with} & 0 < r_{n} < r_{n-1}\\ r_{n-1} & = & q_{n}\cdot r_{n} \end{array}\quad\quad ( * )\]
Since the program begins with the assignment \(r:=b\), exactly the above calculation steps are represented by the commands inside the \(\mathtt{WHILE}\) loop \[\begin{array}{l} r:= a\mod b;\\ a:= b;\\ b:=r \end{array}\]
If \(r_1=0\), then the algorithm stops and returns \(\gcd(a,b)=b\), which is correct, since in this case \(b\mid a\). * Otherwise the loop is repeated.
From the divisibility laws it follows for any common divisor \(t\) of \(a\) and \(b\) that \[t\mid a\wedge t\mid b\Longrightarrow t\mid r_{i}\wedge t\mid r_{i+1}\text{ for }i=0,\ldots,n\]
Therefore, \(t\mid r_n\), and this is true for any arbitrary common divisor \(t\) of \(a\) and \(b\). Moreover, from the last equation of \( ( * ) \) we have that \(r_n\mid r_{n-1}\), from the secont to last equotion that \(r_{n-1}\mid r_{n-2}\), etc.
Motivations: 1
