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

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

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

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

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

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

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

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

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

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

נניח כי ל- $\ n$ קיימים שני פירוקים למכפלת גורמים ראשוניים:

$n = p_1p_2 \cdots p_r = q_1q_2 \cdots q_s$

כאשר $\ r$ ו- $\ s$ מספרים טבעיים כלשהם. נניח כי $r \le s$ וכי בכל מכפלה הגורמים מסודרים בסדר עולה, כלומר $p_1 \le p_2 \le \cdots \le p_r$ ו- $q_1 \le q_2 \le \cdots \le q_s$ . מכיוון ש- $\ p_1$ מחלק את $\ n$ , הרי שהוא מחלק גם את המכפלה $q_1q_2 \cdots q_s$ . אבל כל הגורמים במכפלה זו הם ראשוניים, ולכן $\ p_1 = q_i$ עבור $\ i$ כלשהו, ולכן $p_1 \ge q_1$ . טיעון דומה יתן לנו $q_1 \ge p_1$ , ומכאן ש- $\ p_1 = q_1$ . נצמצם גורם זה משני צדדי השוויון ונקבל: