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

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

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

הוכחה

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

 

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

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

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

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

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

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

 

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

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

הוכחה

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

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

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

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

נוכיח כי   :

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

 

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

לכן   .


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

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

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

 

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

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

 

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

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

הוכחה

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

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

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


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

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

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

 

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

לכן   לכל   .

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


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

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

 

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

 

שורשיםעריכה

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

הוכחה

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

 

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

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

 

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