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

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

הלמה נקראת על שמו של המתמטיקאי היווני בן המאה ה-3 לפנה"ס אוקלידס, שהלמה מופיעה כמשפט ה-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+mp$. נכפיל שוויון זה ב-b:‏ $b=nab+mpb$. p מחלק הן את ab והן את עצמו ולכן $p|n(ab)+p(mb)=b$ כפי שרצינו להוכיח.

המשפט ההפוך

משפט. אם $1<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 בהכרח ראשוני.

הכללות

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

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

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