הוכחת אלגוריתם אוקליד

הצהרת האלגוריתם

כעת נציין את המקרה הכללי של אלגוריתם אוקליד ונוכיח אותו:

אלגוריתם אוקליד: נתונים שני מספרים שלמים \(m > n > 0\).
אם מתקיים:
$$ m = qn + r, 0 \le r \le b, r = m \% n $$
אז:
$$ gcd(m, n) = gcd(b, r) $$

ראינו בדוגמא הקודמת - עלינו להחליף בכל שלב את הגדול מבין שני המחלקים בשארית החלוקה שלו בשני, עד להגעה לתשובה הסופית.

הוכחה

נשתמש באינדוקציה על מנת להראות את הטענה. נניח שמתקיים \(m = qn+r\) ונניח כי קיים מחלק \(d\) של \(m, n\):

$$ m | d, n | d $$

לכן גם מתקיים:

$$ r = m - qn \Longrightarrow r | d $$

כלומר, \(d\) הוא ה-GCD של \(r, n\).

נמשיך באינדוקציה עד שאחד מהמספרים הוא 0.

מימוש בקוד של האלגוריתם

{{# src/euclid.c}}