המשפט היסודי של האריתמטיקה

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

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

למשל, את המספר $\!\, 1176$ ניתן לכתוב כמכפלה הבאה של מספרים ראשוניים: $\!\, 1176=2^3\cdot 3\cdot 7^2$ . אין שום דרך אחרת לכתוב את המספר הזה בתור מכפלה של ראשוניים.

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

תוכן עניינים

1 הוכחת המשפט
- 1.1 שלב א' - קיום
- 1.2 שלב ב' - יחידות
2 הכללות

[עריכה] הוכחת המשפט

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

[עריכה] שלב א' - קיום

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

[עריכה] שלב ב' - יחידות

היחידות מבוססת על תכונה מיוחדת של המספרים הראשוניים: אם מספר ראשוני p מחלק מכפלה, אז הוא מוכרח לחלק אחד מן הגורמים. נוכיח תכונה זו באינדוקציה: נניח שהיא נכונה לכל המספרים הראשוניים הקטנים מ- p. נניח (בשלילה) ש- p אינו מקיים תכונה זו, ולכן קיימת מכפלה ab, ש-p אינו מחלק את שני הגורמים שלה. מבין כל המכפלות בעלות תכונה זו, ניקח את הקטנה ביותר. אם a>p, אפשר להחליף את a ב- a-p, ולקבל דוגמה קטנה יותר; וכך גם עבור b. לכן אפשר להניח ש- a,b<p. מכיוון שכך, $\ ab<p^2$ , ואם נכתוב $\ ab=kp$ , נגלה ש- $\ k<p$ . יהי q גורם ראשוני של k (גורם כזה קיים לפי השלב הראשון). אז q מחלק את kp=ab, ומכיוון ש- $\ q\leq k<p$ , הנחת האינדוקציה מבטיחה ש- q מחלק אחד מן הגורמים a או b. אבל אז אפשר לחלק את הגורם המתאים (ואת k) ב- q, ולקבל דוגמה קטנה יותר, בסתירה להנחה שלפיה בחרנו את הדוגמה הקטנה ביותר.

נסיים את הוכחת היחידות באינדוקציה על n. נניח כי ל- $\ n$ קיימים שני פירוקים למכפלת גורמים ראשוניים $\ n = p_1p_2 \cdots p_r = q_1q_2 \cdots q_s$ . מכיוון ש- $\ p_1$ ראשוני, הוא מקיים את התכונה האמורה לעיל, ומחלק אחד מן הגורמים $\ q_j$ . אבל $\ q_j$ עצמו ראשוני, ומכאן ש- $\ p_1=q_j$ . כעת אפשר לצמצם את שני הגורמים הללו, ולקבל מספר קטן יותר שיש לו שני פירוקים. לפי הנחת האינדוקציה, פירוק זה הוא יחיד, כפי שרצינו להוכיח.

[עריכה] הכללות

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

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

יחידות הפירוק, כאמור, היא עניין סבוך יותר. תחום שבו מתקיים המשפט היסודי של האריתמטיקה - כל איבר (לא הפיך) מתפרק באופן יחיד לגורמים אי-פריקים - נקרא תחום פריקות יחידה. בדיוק כמו בחוג השלמים, בחוג כזה מתלכדים המושגים "איבר ראשוני" ו"איבר אי-פריק". הדוגמאות הבולטות לחוג כזה: כל תחום ראשי (ובפרט - כל תחום אוקלידי), וגם כל חוג פולינומים מעל שדה, בכל מספר של משתנים. החוג $\ F[\lambda_1,\lambda_2,\dots]$ (עם אינסוף משתנים) הוא דוגמה לתחום פריקות יחידה שאינו נותרי.

המשפט היסודי של האריתמטיקה

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

תוכן עניינים

[עריכה] הוכחת המשפט

[עריכה] שלב א' - קיום

[עריכה] שלב ב' - יחידות

[עריכה] הכללות

צפיות

כלים אישיים

חיפוש

ניווט

קהילה

תיבת כלים

שפות אחרות