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

בהוכחת היחידות מופיע "ולכן" (שמקבל בתוכו את כל ההוכחה). אני סקרן לדעת עד כמה ההסבר של הצעד הקריטי הזה מוכר (לאחר המתנה קצרה להעלאת המתח, אסביר את העניין בתוך הערך). עוזי ו. 21:57, 5 באוקטובר 2006 (IST)

אולי אני מתבלבל, אבל נראה לי שלמי שלמד אלגברה מופשטת זה אמור להיות ברור. עד כמה שאני מבין, בגלל ש-p ראשוני ומחלק מכפלה, הוא בהכרח מחלק את אחד מאברי המכפלה, נניח q (זה דבר שיש להוכיח בפני עצמו, אבל איני בטוח שהוא צריך להיות חלק מההוכחה הזו). מכיוון ש-q ראשוני ולכן מחלק אותו רק q ו-1 ומכיוון ש-p אינו 1, בהכרח p=q. כל זה נראה לי די מיידי, אבל באמת כדאי לפרט אותו. גדי אלכסנדרוביץ' 22:06, 5 באוקטובר 2006 (IST)

קצת מבלבל לגייס את האלגברה המופשטת לכאן. בתחום שלמות כללי, מקובל להגדיר איבר אי-פריק כאיבר שאין לו פירוק לא טריוויאלי, ואיבר ראשוני כאיבר שאינו יכול לחלק מכפלה בלי לחלק את אחד הגורמים. ראשוני הוא תמיד אי-פריק, אבל יש אי-פריקים שאינם ראשוניים. (במספרים הטבעיים מקובל לקרוא דווקא למספרים מהסוג השני "ראשוניים"; אבל העובדה שההגדרות שקולות, ובמספרים השלמים כל מספר אי-פריק הוא ראשוני, היא לב ההוכחה של המשפט היסודי של האריתמטיקה). אם תקרא את ההוכחה בעיון, תראה שהחלק הראשון מראה שתמיד קיים פירוק לגורמים אי-פריקים, והחלק השני מוכיח שפירוק לגורמים ראשוניים (אם הוא קיים) הוא יחיד. לסיכום הסיכום, לפי ההוכחה הזו יתכן שכל מספר מתפרק לגורמים אי-פריקים, אבל פירוק זה אינו יחיד; פרט לכמה מספרים בני-מזל שיש להם פירוק לראשוניים, ואז הוא יחיד (מבין כל הפירוקים לגורמים אי-פריקים). עוזי ו. 15:02, 9 באוקטובר 2006 (IST)

אני התייחסתי כאן לראשוני בהגדרתו ה"קלאסית" (אי פריק), ולכן אמרתי שיש להוכיח שאי הפריקות אכן גוררת ראשוניות ב-Z. אם כיוונת לכך שהדבר שחסר הוא שאי פריק הוא ראשוני ב-Z, לא הבנתי אותך קודם. גדי אלכסנדרוביץ' 15:14, 9 באוקטובר 2006 (IST)

אולי כדאי להחליף את ההוכחה שבערך בהוכחה זו, שאינה מסתמכת על הנחות לא-מוכחות: http://img2.tapuz.co.il/forums/1_87049092.pdf כמו כן נראה לי שניסוח של הוכחת הקיום כהוכחה באינדוקציה הינו ברור יותר מהניסוח שבגוף הערך. כך: מההנחה שלמספרים 1 עד n יש פירוק לגורמים ראשוניים נובע שלמספר n+1 יש פירוק כזה, כי אם n+1 ראשוני - הוא עצמו הפירוק, ואם הוא פריק - הוא מכפלת שני מספרים קטנים מ - n+1, שלפי הנחת האינדוקציה יש להם פירוק לגורמים ראשוניים. זו בעצם ההוכחה שבערך, רק בכיוון הפוך, אבל לדעתי כך ברור יותר.

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

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

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

תזכורת

העניין טרם תוקן, ולדעתי הוכחת היחידות הנוכחית מאוד צורמת. לירן (שיחה,תרומות) 00:35, 2 בנובמבר 2007 (IST)

ויכוח

מספר לא בהכרח יכול להיכתב בתור מכפלה ייחודית: למשל, $\ 6=3\cdot 2=2\cdot 3$, ולכן 6 לא יכול להיכתב בתור מכפלה ייחודית (כי הוא שווה לשתי מכפלות של ראשוניים). לעומת זאת קיימת צורה ייחודית להצגת 6 בתור מכפלה - כאשר הראשוניים מסודרים לפי סדר עולה, נניח. מאותה סיבה לא ניתן להוכיח שהפירוק הוא אף פעם יחיד - אלא רק עד כדי סדר הופעת הגורמים בפירוק. גדי אלכסנדרוביץ' 18:20, 2 בפברואר 2007 (IST)

אתה קצת קטנוני (הרי כל ויקיפד כבר יודע שהכפל קומוטטיביות), וחוץ מזה כתוב בפסקה השנייה "פרט לשינוי הסדר של הגורמים". הזזתי לפסקה הראשונה. דוד שי 18:29, 2 בפברואר 2007 (IST)

אני מאוד קטנוני, ללא ספק, אבל המשפט שקיים כרגע בערך - "כל מספר טבעי יכול להיכתב כמכפלה ייחודית של מספרים ראשוניים, פרט לשינוי הסדר של הגורמים" - נשמע לי חסר משמעות. אולי זה רק אני. גדי אלכסנדרוביץ' 20:48, 2 בפברואר 2007 (IST)

מי הוכיח

ומתי? נוי - שיחה 18:13, 2 באוקטובר 2008 (IDT)

הוכחתו של אוקלידס לשלב א' (קיום) במשפט

ההוכחה מתבססת על עקרון הסדר הטוב, השקול לאינדוקציה:

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

תהא $S=\left\{{n\in \mathbb {N} :n>1,\neg \exists p\in \mathbb {P} :p|n}\right\}$

כלומר: $\}$קבוצת כל המספרים הטבעיים שאינם מתחלקים בגורם ראשוני$S=\{$

עכשיו, יהי $n\in S$ הקטן שבאיברי הקבוצה. כיון שהקבוצה חסומה מלרע ע"י $1$, חייב להתקיים איבר כזה.

לכן: $\neg \exists x\in S:x<n$

לאמר: לא קיים איבר $x$ בקבוצה הקטן מ-$n$.

עכשיו, $n$ עצמו אינו יכול להיות ראשוני:

$\left({\left({n\in \mathbb {P} }\right)\land \left({n|n}\right)\implies n\notin S}\right)\implies n\notin \mathbb {P}$

שאז שוב לא ישתייך ל-$S$.

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

$\exists a,b\in \mathbb {N} :1<a<n,1<b<n:n=ab$

לאמר: קיימים שני גורמים טבעיים $a,b$ הגדולים מ-$1$ וקטנים מ-$n$, כך ש- $n=ab$.

כרגע, ישנם שני מצבים אפשריים:

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

אם כך, מתקיים: $\exists p\in \mathbb {P} :\left({p|a}\right)\lor \left({p|b}\right)\implies p|n$

כלומר, קיים ראשוני $p$ שלפי למת אוקלידס מחלק לפחות אחד מהגורמים $a,b$ במכפלה, דבר הגורר את היותו מחלק של $n$ גם הוא.

אך נתון ש- $n$ אינו מתחלק באף ראשוני. סתירה!

$.2$ לאף מן הגורמים אין מחלק ראשוני.

מכאן נובע: $a,b\in S$

כלומר, הם משתייכים לקבוצה $S$, עקב הגדרתה כ"קבוצת כל המספרים חסרי מחלקים ראשוניים".

כיון שנתון לנו $(a,b)<n$, מסתבר ש-$n$ שוב אינו האיבר הקטן ביותר בקבוצה. שוב סתירה!

עקב כך, מתברר שלא קיים $n$ כזה, ו-$S=\varnothing$, קבוצה ריקה ללא איברים כלל. מש"ל. ■

איש הסילונים - שיחה 00:52, 13 באוקטובר 2015 (IDT)

היסטוריה

לפי התאור המפורט בערך האנגלי , קשה שלא לייחס את ההוכחה המלאה לאוקלידס, גם אם הוא לא ניסח את המשפט באופן שאנחנו מנסחים אותו היום. הלוא כן? עוזי ו. - שיחה 13:08, 12 בדצמבר 2023 (IST)

אני לא מכירה מקורות היסטוריים שמשייכים את ההוכחה לאוקליד. כמובן שיש קשר הדוק בין מה שאוקליד עשה למשפט. שתי הטענות שרבים מאיתנו משתמשים בהן להוכחה כיום אכן מופיעות אצלו ב'אלמנטים', אבל הוא מעולם לא ניסח את המשפט עצמו ולא הוכיח אותו. Rosielev - שיחה 11:14, 13 בדצמבר 2023 (IST)

המאמר הזה מציג מידע נוסף. לאור הדברים שאוקלידס כן הוכיח, אני לא רואה איך אפשר לשייך את המשפט למישהו אחר. נכון שלא מדובר בגילוי יבשת, שאפשר לקבוע באופן חד-משמעי אם היה ומתי, אלא בניסוח של טענה מתמטית. האם אוקלידס ניסח את המשפט היסודי, או "רק" את חלקיו של המשפט הזה? לא ברור שיש טעם בדיון הזה. עוזי ו. - שיחה 14:59, 13 בדצמבר 2023 (IST)

גם במאמר ששלחת לא כתוב שאוקליד הוכיח את המשפט. כיוון שהדיון לגבי מי הוכיח את המשפט הוא מורכב, הייתי מציעה לתת את ההוכחה המתמטית, ובפסקה נפרדת לדון בהיסטוריה של המשפט, למי שמתעניין בנושא Rosielev - שיחה 15:13, 13 בדצמבר 2023 (IST)