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

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

לכל $n\in \mathbb {N} _{>1}$ קיים מחלק ראשוני.

הוכחה

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

$S={\Big \{}n\in \mathbb {N} _{>1}:\not \exists p\in \mathbb {P} :p|n{\Big \}}$

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

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

לכן קיימים $a,b$ עבורם $n=ab$ .

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

1. לאף מן הגורמים אין מחלק ראשוני $p$ , שכן זה גורר $p|n$ . מכאן $a,b\in S$ , אך $a,b<n$ אף שהנחנו כי $n$ מינימום. סתירה.
2. כיון שהאפשרות הקודמת נפסלה, מוכרח כי לפחות אחד הגורמים $a,b$ בעל מחלק ראשוני $p$ , אך זה גורר $p|n$ . סתירה.

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

$\blacksquare$

אלגוריתם אוקלידס

לכל $a,b\in \mathbb {Z} ,b>0$ קיימים מספרים יחידים $q,r\in \mathbb {Z}$ המקיימים $a=qb+r$ כאשר $0\leq r<b$ "שארית".

הוכחה

(קיום) נגדיר קבוצת טבעיים $S={\Big \{}a-nb\geq 0:n\in \mathbb {Z} {\Big \}}$ . זוהי קבוצה לא־ריקה

אם $a\geq 0$ , הצבת $n=0$ מראה $a\in S$ .

אם $a<0$ , הצבת $n=a$ מראה $a(1-b)\in S$ כיון שכבר הגדרנו $b>0$ .

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

לכן קיים $q\in \mathbb {Z}$ עבורו $r=a-qb$ .

נוכיח כי $r<b$ :

נניח בשלילה כי $r\geq b$ ואז $r-b\geq 0$ .

${\color {blue}0\leq r-b}=(a-qb)-b={\color {blue}a-b(q+1)<r}$

נובע $r-b\in S$ , אך $r-b<r$ אף שהנחנו כי $r$ מינימום. סתירה.

לכן $r<b$ .

(יחידות) נניח בשלילה כי קיימים מספרים נוספים ${\bar {q}},{\bar {r}}\in \mathbb {Z}$ המקיימים $a={\bar {q}}b+{\bar {r}}$ כאשר $0\leq {\bar {r}}<b$ "שארית".

כלומר $a=qb+r={\bar {q}}b+{\bar {r}}$ . מכאן נקבל $b(q-{\bar {q}})={\bar {r}}-r$ .

נניח ללא הגבלת הכלליות כי ${\bar {r}}\geq r$ ואז ${\bar {r}}-r\geq 0$ . מהנתון ${\bar {r}}<b$ ודאי ${\bar {r}}-r<b$ . לכן

${\begin{matrix}0\leq {\bar {r}}-r<b\\0\leq b(q-{\bar {q}})<b\\0\leq q-{\bar {q}}<1\end{matrix}}$

$q,{\bar {q}}\in \mathbb {Z}$ וחיסורם נותן מספר שלם הקטן מ־1 וגדול או שווה 0, וישנו רק מספר אחד כזה.

כלומר $q-{\bar {q}}=0$ ומכאן ${\bar {q}}=q$ . הצבה במשוואה הנ"ל תתן כמובן ${\bar {r}}=r$ .

$\blacksquare$

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

לכל $a,b\in \mathbb {Z}$ בעלי מחלק משותף מקסימלי $d$ , קיימים מספרים $x,y\in \mathbb {Z}$ המקיימים $d=ax+by$ .

הוכחה

נגדיר קבוצת טבעיים $S={\Big \{}ax+by:x,y\in \mathbb {Z} {\Big \}}$ .

זוהי קבוצה לא־ריקה, כי הצבה פשוטה מראה $0\in S$ .

על־פי עקרון הסדר הטוב קיים מינימום $0<d=am+bn\in S$ .

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

נניח בשלילה כי $d\nmid k$ עבור $k=ax+by\in S$ כלשהו.

על־פי אלגוריתם אוקלידס קיימים $q,r\in \mathbb {Z}$ המקיימים $k=qd+r$ כאשר $0<r<d$ "שארית".

${\color {blue}0<r}=k-qd=ax+by-q(ma+nb)={\color {green}a(x-qm)+b(y-qn)}\,{\color {blue}<d}$

מהתבנית הירוקה נובע $r\in S$ , אך $r<d$ אף שהנחנו כי $d$ מינימום. סתירה.

לכן $d|k$ לכל $k\in S$ .

הצבות פשוטות נוספות מראות $a,b\in S$ , ומכאן $d|a$ וגם $d|b$ .

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

נניח כי $c$ מחלק נוסף של $a,b$ , אזי קיימים מספרים $g,h\in \mathbb {Z}$ המקיימים $a=gc\ ,\ b=hc$ .

${\color {blue}d}=am+bn=(gc)m+(hc)n={\color {blue}c(mg+nh)}$

$c|d$ ומתקבל כי $c\leq d$ , לכן $d$ הוא מחלק משותף מקסימלי.

$\blacksquare$

שורשים

${\sqrt[{n}]{a}}$ הוא מספר שלם או אי־רציונלי לכל $a,n\in \mathbb {N} _{>1}$ .

הוכחה

נניח בשלילה כי ${\sqrt[{n}]{a}}={\frac {b}{c}}$ עבור מספרים זרים $b,c\in \mathbb {N} _{>1}$ (שמחלקם המשותף המקסימלי הוא 1).

${\begin{aligned}a=\left({\frac {b}{c}}\right)^{n}={\frac {b^{n}}{c^{n}}}\\ac^{n}=b^{n}\end{aligned}}$

לפי המשפט היסודי קיים מספר ראשוני $p$ עבורו $p|c^{n}$ .

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

$p|c^{n}\implies p|c\implies p|ac^{n}\implies p|b^{n}\implies p|b$

קיבלנו $p|b$ וגם $p|c$ אף כי הנחנו תחילה שהם זרים. סתירה.

$\blacksquare$