הלמה של בזו

במתמטיקה, ובפרט בתורת המספרים, הלמה של בזו (במקורות מסוימים נקראת גם זהות בזו^[1]) קובעת שבהינתן זוג מספרים שלמים, המחלק המשותף המקסימלי שלהם ניתן לייצוג כצירוף ליניארי שלהם במקדמים שלמים.

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

גרסה של הלמה לפולינומים הוכחה על-ידי המתמטיקאי הצרפתי אטיין בזו בשנת 1779.

ניסוח פורמלי

בהינתן זוג מספרים שלמים $a, b \in ℤ$ קיימים זוג מקדמים שלמים $x, y \in ℤ$ כך ש- $a x + b y = \gcd (a, b)$ , כאשר $\gcd (a, b)$ הוא המחלק המשותף המקסימלי של $a$ ו- $b$ . הזוג $(x, y)$ נקרא מקדמי בזו.

דוגמה

נבחן את המספרים a = 12 ו- b = 8. המחלק המשותף המקסימלי הוא $g c d (12, 8) = 4$ . נמצא זוג מקדמים שלמים $(x, y)$ כך ש $4 = 12 x + 8 y$ . אחד הפתרונות יהיה $y = 2$ , $x = - 1$ , כי $12 \cdot (- 1) + 8 \cdot 2 = 4$

הוכחה

מקרים טריוויאליים

במקרה שבו $a = 0$ ניתן להגדיר $x = 0, y = 1$ ולקבל ש- $a x + b y = 0 \cdot 0 + b \cdot 1 = b = \gcd (0, b) = \gcd (a, b)$ .

במקרה שבו $a < 0$ , אם הלמה של בזו מתקיימת עבור $| a |$ ו- $b$ , ניתן להראות כי:

$a (- x) + b y = - a x + b y = | a | x + b y = \gcd (| a |, b) = \gcd (a, b)$

משמע היא מתקיימת גם עבור $a$ ו- $b$ . לכן, די להוכיח את הלמה במקרה שבו $a$ ו- $b$ שניהם חיוביים כדי להוכיח את הלמה בשלמותה.

הוכחה למספרים חיוביים

מגדירים את הקבוצה $S : = {a x + b y ∣ x, y \in ℤ, a x + b y > 0}$ . הקבוצה $S$ היא בהכרח קבוצה לא ריקה מכיוון ש- $1 \cdot a + 0 \cdot b = a > 0$ ולכן $a \in S$ . $S$ היא תת-קבוצה של קבוצת המספרים הטבעיים. מכיוון שקבוצת המספרים הטבעיים סדורה בסדר טוב, לכל תת-קבוצה לא ריקה שלה יש איבר קטן ביותר.^[2] לכן, ל- $S$ קיים איבר קטן ביותר, נסמנו ב- $d$ . כמו כן, מגדירים $x_{1}, y_{1} \in ℤ$ כך ש- $d = a x_{1} + b y_{1}$ (אלו בהכרח קיימים לפי הגדרת $S$ ).

די להוכיח כי $d = \gcd (a, b)$ כדי להוכיח את הלמה.

ראשית יש להוכיח כי $d | a$ . בגלל תכונות החילוק של המספרים הטבעיים, בהכרח קיימים $k, r$ שלמים ואי-שליליים כך ש- $a = k d + r$ ו- $0 \leq r < d$ . מניחים בשלילה כי $r \neq 0$ . מתקבל כי $r = a - k d = a - k (a x_{1} + b y_{1}) = a (1 - k x_{1}) - b k y_{1}$ . משמע $r \in S$ . עם זאת, $r < d$ ו- $d$ מינימלי ב- $S$ , וזו סתירה. על כן $r = 0$ , משמע $a = k d$ ו- $d | a$ .

ההוכחה כי $d | b$ זהה. עולה מכך ש- $d$ הוא מחלק משותף של $a$ ו- $b$ .

כעת, בהינתן $d^{'}$ חיובי כלשהו המקיים $d^{'} | a$ ו- $d^{'} | b$ , יש להוכיח כי $d^{'} | d$ . מכיוון ש- $d^{'} | a$ מתקיים ש- $d^{'} | a x$ . באופן דומה, מכיוון ש- $d^{'} | b$ מתקיים ש- $d^{'} | b y$ . אם מספר שלם מחלק שני מספרים שלמים אחרים, הוא בהכרח מחלק את הסכום שלהם. על כן $d^{'} | a x + b y = d$ .

מתקבל אפוא כי $d$ הוא מחלק משותף של $a$ ו- $b$ , וכי כל מחלק משותף אחר של $a$ ו- $b$ מחלק בהכרח את $d$ . מכל זאת נובע כי $d$ הוא המחלק המשותף המקסימלי של $a$ ו- $b$ , כלומר $d = \gcd (a, b)$ .

מ.ש.ל.

אלגוריתם אוקלידס

ערך מורחב – אלגוריתם אוקלידס

בעוד שהלמה של בזו מוכיחה כי המחלק המשותף המקסימלי של זוג מספרים ניתן לייצוג כצירוף ליניארי שלהם, היא אינה מספקת אלגוריתם כיצד למצוא צירוף ליניארי זה.^[3]

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

בהינתן זוג מספרים שלמים $a, b \in ℤ$ , אלגוריתם אוקלידס מבוצע כדלקמן:

אם אחד או יותר מהם הוא אי-חיובי, ניתן למצוא את המחלק המשותף המקסימלי של $| a |$ ו- $| b |$ אשר זהה למחלק המשותף המקסימלי של $a$ ו- $b$ . על כן, מניחים בלי הגבלת הכלליות כי $0 \leq a \leq b$ .

אם $a = 0$ אז $\gcd (a, b) = b$ . אחרת, ניתן להראות כי $\gcd (a, b) = \gcd (a, b - a)$ . מגדירים $a_{1} : = \min (a, b - a), b_{1} : = \max (a, b - a)$ . מתוך כך $0 \leq a_{1} \leq b_{1}$ , על כן ניתן לחזור על התהליך. התהליך מסתיים לאחר $n$ צעדים סופיים כאשר $a_{n} = 0$ . במקרה זה $b_{n} = \gcd (a, b)$ .

הכללה ליותר משני גורמים

ניתן להכליל את הלמה של בזו ליותר משני גורמים:

בהינתן מספר טבעי $n \in ℕ$ ו- $a_{1}, a_{2}, \dots, a_{n} \in ℤ$ , קיימים בהכרח $x_{1}, x_{2}, \dots, x_{n} \in ℤ$ כך ש:

$a_{1} x_{1} + a_{2} x_{2} + \dots + a_{n} x_{n} = \gcd (a_{1}, a_{2}, \dots, a_{n})$

הכללה זו נובעת בין היתר מהעובדה כי $\gcd (a_{1}, a_{2}, \dots, a_{n - 1}, a_{n}) = \gcd (\gcd (a_{1}, a_{2}, \dots, a_{n - 1}), a_{n})$ , על כן ניתן למצוא את מקדמי בזו ל- $n - 1$ הרכיבים הראשונים ולאחר מכן למצוא את מקדמי בזו לכל $n$ הרכיבים.

תחום בזו

ערכים מורחבים – חוג בזו, תחום בזו

באופן כללי, הלמה של בזו לא מתקיימת לכל חוג כללי. כך למשל, הלמה לא מתקיימת בחוג הפולינומים במקדמים שלמים $ℤ [x]$ .

חוג שבו מתקיימת הלמה של בזו נקרא תחום בזו. באופן פורמלי, חוג $R$ ייקרא תחום בזו אם ורק אם הוא מקיים את כל התנאים הבאים:

$R$ הוא תחום שלמות. כלומר, לכל $0 \neq a, b \in R$ מתקיים ש- $a b \neq 0$
$R$ הוא חוג בזו. כלומר, כל אידיאל נוצר סופית ב- $R$ הוא בהכרח אידיאל ראשי.

דוגמאות לתחומי בזו הם כל תתי-החוגים של חוג המספרים הממשיים $ℝ$ וחוג הפולינומים במשתנה אחד $F [x]$ כאשר $F$ הוא שדה.

מסקנות

מספרים זרים

ערך מורחב – מספרים זרים

שני מספרים שלמים $a, b \in ℤ$ ייקראו מספרים זרים אם ורק אם $\gcd (a, b) = 1$ . מהלמה של בזו ניתן להסיק כי זוג מספרים הם מספרים זרים אם ורק אם קיימים זוג מקדמים שלמים $x, y \in ℤ$ כך ש- $a x + b y = 1$ .

הוכחה:

אם $a$ ו- $b$ זרים, לפי הלמה של בזו ניתן להרכיב את המספר $1$ על ידי צירוף ליניארי של $a$ ו- $b$ . כעת יש להוכיח את הכיוון ההפוך.

מניחים כי קיימים $x, y \in ℤ$ כך ש- $a x + b y = 1$ . $1$ הוא מחלק משותף של $a$ ו- $b$ . לכן כל שיש להוכיח הוא שהוא מחלק מקסימלי.

מגדירים מחלק משותף $d$ של $a$ ו- $b$ . לכן הוא מחלק גם כל צירוף ליניארי שלהם, בפרט $a x + b y = 1$ . כלומר $d$ מחלק את $1$ . מכל זה, $1$ הוא מחלק מקסימלי של $a$ ו- $b$ , כלומר $\gcd (a, b) = 1$ .

מ.ש.ל.

הלמה של אוקלידס

ערך מורחב – הלמה של אוקלידס

הלמה של אוקלידס קובעת שכאשר ישנם שלושה מספרים שלמים $a, b, p \in ℤ$ כך ש- $p$ ראשוני ו- $p | a b$ , בהכרח מתקיים ש- $p | a$ או $p | b$ .

הוכחה:

מגדירים $d : = \gcd (a, p)$ . מאחר ש- $p$ ראשוני ו- $d$ מחלק את $p$ , מתקיים ש- $d = 1$ או $d = p$ .

אם $d = p$ , אז $p | a$ לפי הגדרת המחלק המשותף המקסימלי, ובכך הסתיימה ההוכחה.

אם $d = 1$ , לפי הלמה של בזו קיימים $x, y \in ℤ$ כך ש- $a x + p y = 1$ . מכפילים את שני האגפים ב- $b$ ומקבלי ש- $a b x + p b y = b$ . שני האיברים משמאל מתחלקים ב- $p$ , לכן האיבר מימין מתחלק ב- $p$ . כלומר, $p | b$ .

מש.ל.

ראו גם

קישורים חיצוניים

הלמה של בזו, באתר MathWorld (באנגלית)

הערות שוליים

↑ Gareth A. Jones, J. Mary Jones, Elementary Number Theory, Springer Undergraduate Mathematics Series, 1998 doi: 10.1007/978-1-4471-0613-5
↑ A Cooper, the Well-Ordering Principle, NC State University, ‏September 17, 2018 (באנגלית)
↑ Ryan C. Daileda, B´ezout’s Lemma, Trinity University, ‏2020-03-25 (באנגלית)

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

הלמה של בזו41928912Q513028

[1] Gareth A. Jones, J. Mary Jones, Elementary Number Theory, Springer Undergraduate Mathematics Series, 1998 doi: 10.1007/978-1-4471-0613-5

[2] A Cooper, the Well-Ordering Principle, NC State University, ‏September 17, 2018 (באנגלית)

[3] Ryan C. Daileda, B´ezout’s Lemma, Trinity University, ‏2020-03-25 (באנגלית)

[1]

[2]

[3]