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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

הלמה נקראת על שמו של המתמטיקאי היווני בן המאה השלישית לפנה"ס אוקלידס, שהלמה מופיעה כמשפט ה-30 בכרך השביעי של ספרו יסודות.

דוגמה[עריכת קוד מקור | עריכה]

המכפלה  15 \times 2 = 30 מתחלקת בראשוני 3, ולכן לפי הלמה 3 מחלק את 2 או את 15. במקרה הזה 3 מחלק את 15.

המשפט אינו בהכרח נכון כאשר המחלק הוא מספר פריק. 4 מחלק את המכפלה 6 \times 2 =12, אבל לא מחלק את 2 או את 6.

הוכחה[עריכת קוד מקור | עריכה]

הלמה של אוקלידס. אם p ראשוני ו-p|ab אז p|a או p|b.

נגדיר d=\gcd(p,a) (מחלק משותף מקסימלי). d מחלק של p ולכן מהגדרת הראשוניות d=1 או d=p. אם d=p אז מכיוון ש-d|a נקבל p|a כפי שרצינו להוכיח. על כן נניח ש-d=1, כלומר a ו-p מספרים זרים. לפי אלגוריתם אוקלידס המורחב קיימים n ו-m שלמים כך ש-1=na+pm. נכפיל שוויון זה ב-b:‏ b=nab+pmb. p מחלק הן את ab והן את עצמו ולכן p|n(ab)+p(mb) = b כפי שרצינו להוכיח.

המשפט ההפוך[עריכת קוד מקור | עריכה]

משפט. אם p מספר שלם כך שלכל a ו-b כך ש-p|ab, מתקיים p|a או p|b, אזי p ראשוני.

נניח שלכל a ו-b שלמים, אם p|ab אז p|a או p|b. יהי p=cd פירוק של p. בפרט p|cd ולכן נניח ללא הגבלת הכלליות ש-p|c. מכאן שקיים e שלם כך ש-c=pe=cde. נצמצם ב-c:‏ 1=ed.‏ d מחלק של 1 ולכן d= \pm 1. כלומר p=cd הוא פירוק טריוויאלי ו-p בהכרח ראשוני.

הכללות[עריכת קוד מקור | עריכה]

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

בתחום שלמות כללי איבר ראשוני מוגדר כאיבר שמקיים את הלמה של אוקלידס. הוכחת הכיוון ההפוך מדגימה שאיבר ראשוני הוא בהכרח אי-פריק (לא ניתן להצגה כמכפלה של גורמים לא הפיכים). לעומת זאת בתחום שלמות כללי איבר אי-פריק אינו בהכרח ראשוני. למשל ב-\Z[\sqrt{-5}] 2 אי-פריק, אבל אינו ראשוני כי אינו מחלק אף אחד מן הגורמים במכפלה: (1+\sqrt {-5})(1-\sqrt {-5})=6.

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