משתמש:יהודה שמחה ולדמן/רשימת משפטים בתורת המספרים

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי

קיום מחלקים ראשוניים[עריכה]

לכל קיים מחלק ראשוני.

הוכחה

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

כיון שהקבוצה חסומה מלרע על־ידי 1, על־פי עקרון הסדר הטוב קיים מינימום .

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

לכן קיימים עבורם .

ישנם שני מצבים אפשריים:

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

לכן ריקה וכו'.

אלגוריתם אוקלידס[עריכה]

לכל קיימים מספרים יחידים המקיימים כאשר "שארית".

הוכחה

(קיום) נגדיר קבוצת טבעיים . זוהי קבוצה לא־ריקה

אם , הצבת מראה .
אם , הצבת מראה כיון שכבר הגדרנו .

כיון שהקבוצה חסומה מלרע על־ידי 0, על־פי עקרון הסדר הטוב קיים מינימום .

לכן קיים עבורו .

נוכיח כי  :

נניח בשלילה כי ואז .

נובע , אך אף שהנחנו כי מינימום. סתירה.

לכן .


(יחידות) נניח בשלילה כי קיימים מספרים נוספים המקיימים כאשר "שארית".

כלומר . מכאן נקבל .

נניח ללא הגבלת הכלליות כי ואז . מהנתון ודאי . לכן

וחיסורם נותן מספר שלם הקטן מ־1 וגדול או שווה 0, וישנו רק מספר אחד כזה.

כלומר ומכאן . הצבה במשוואה הנ"ל תתן כמובן .

אלגוריתם אוקלידס המורחב – זהות Bézout[עריכה]

לכל בעלי מחלק משותף מקסימלי , קיימים מספרים המקיימים .

הוכחה

נגדיר קבוצת טבעיים .

זוהי קבוצה לא־ריקה, כי הצבה פשוטה מראה .

על־פי עקרון הסדר הטוב קיים מינימום .


נוכיח כי מחלק משותף:

נניח בשלילה כי עבור כלשהו.

על־פי אלגוריתם אוקלידס קיימים המקיימים כאשר "שארית".

מהתבנית הירוקה נובע , אך אף שהנחנו כי מינימום. סתירה.

לכן לכל .

הצבות פשוטות נוספות מראות , ומכאן וגם .


עתה נוכיח כי הוא מקסימלי.

נניח כי מחלק נוסף של , אזי קיימים מספרים המקיימים .

ומתקבל כי , לכן הוא מחלק משותף מקסימלי.

שורשים[עריכה]

הוא מספר שלם או אי־רציונלי לכל .

הוכחה

נניח בשלילה כי עבור מספרים זרים (שמחלקם המשותף המקסימלי הוא 1).

לפי המשפט היסודי קיים מספר ראשוני עבורו .

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

קיבלנו וגם אף כי הנחנו תחילה שהם זרים. סתירה.