Proof

(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 ( * )\]

Motivations: 1


Thank you to the contributors under CC BY-SA 4.0!

Github:
bookofproofs


References

Bibliography

  1. Scheid Harald: "Zahlentheorie", Spektrum Akademischer Verlag, 2003, 3rd Edition
  2. Landau, Edmund: "Vorlesungen ├╝ber Zahlentheorie, Aus der Elementaren Zahlentheorie", S. Hirzel, Leipzig, 1927