חזור לתיקייה: 01040134 - אלגברה מודרנית ח'

1 - מבוא לתורת המספרים

חיפוש בתיקיה
Ctrl K
לחץ כאן או הקש Ctrl K כדי לחפש בכל התיקיה
  • חלוקות
  • המחלק המשותף
  • בואו נמצא ממ"גב
  • חשבון מודולו n

1 - מבוא לתורת המספרים

01040134

אלגברה מודרנית ח'

רשימות הרצאה לקריאה בשבת

מבוא לתורת המספרים

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

uni-folder.vercel.app

הדבר הראשון שנתעניין בו הוא איך לעבוד עם מספרים שלמים? נרצה להשוות ביניהם ועל מנת לעשות זאת נשווה ביניהם ע"י חלוקה.

חלוקות

הגדרה 1 (מחלק את)

עבור 0≠a∈Z,b∈Z0\neq a \in \mathbb{Z},b \in \mathbb{Z}0=a∈Z,b∈Z נאמר כי aaa מחלק את bbb ובסימון a∣ba \mid ba∣b אם קיים c∈Zc \in \mathbb{Z}c∈Z כך ש-b=a⋅cb=a\cdot cb=a⋅c.

דוגמה

2∣66∤2−3∣02\mid 6 \qquad \qquad \qquad 6 \nmid2 \qquad \qquad -3 \mid 02∣66∤2−3∣0
הערה

החלוקה 0∣−30 \mid-30∣−3 לא מוגדרת כלל, לכן לא ניתן לכתוב את זה ולא את 0∤−30 \nmid-30∤−3.
אף אחד מהסימנים הללו לא נכון למקרה זה.

בתרגול נראה כל מיני תכונות וביניהן:

משפט

יהיו 0≠a,b∈Z0\neq a,b \in \mathbb{Z}0=a,b∈Z
אם a∣ba \mid ba∣b וגם b∣ab \mid ab∣a אזי a=±ba=\pm ba=±b.

משפט

יהיו 0≠a∈Z,b,c∈Z0\neq a\in \mathbb{Z}, b,c\in \mathbb{Z}0=a∈Z,b,c∈Z.
אם a∣ba \mid ba∣b וגם a∣ca \mid ca∣c אזי לכל α,β∈Z\alpha,\beta \in \mathbb{Z}α,β∈Z מתקיים a∣αb+βca \mid \alpha b+\beta ca∣αb+βc.

את שאר התכונות והוכחות לאלו נראה בתרגול.
כעת נשאל את עצמנו מה עושים כשלא ניתן לחלק "בלי שארית"?

משפט (חלוקה עם שארית (Z\mathbb{Z}Z אוקלידי))

יהיו a,b∈Za,b \in \mathbb{Z}a,b∈Z כאשר b≠0b\neq 0b=0. אז קיימים ויחידים שלמים המנה - qqq והשארית - rrr כך שמתקיים a=b⋅q+ra=b\cdot q+ra=b⋅q+r ובנוסף r=0r=0r=0 או 0<r<∣b∣0<r<|b|0<r<∣b∣.

הרבה פעמים כאשר נרצה להראות שיש חלוקה בלי שארית נניח כי יש שארית ונראה כי r=0r=0r=0 במשפט הזה.

דוגמה

  1. עבור a=29,b=7a=29,b=7a=29,b=7 נקבל כי: 29=7⋅4+129=7\cdot 4+129=7⋅4+1. כלומר, q=4,r=1q=4,r=1q=4,r=1.
  2. עבור a=−29,b=7a=-29,b=7a=−29,b=7 נקבל כי: −29=7⋅(−5)+6-29=7\cdot (-5)+6−29=7⋅(−5)+6. כלומר, q=−5,r=6q=-5,r=6q=−5,r=6.
  3. עבור a=29,b=7a=29,b=7a=29,b=7 נקבל כי: 29=(−7)⋅(−4)+129=(-7)\cdot(-4)+129=(−7)⋅(−4)+1. כלומר, q=−4,r=1q=-4,r=1q=−4,r=1.
  4. עבור a=−29,b=−7a=-29,b=-7a=−29,b=−7 נקבל כי −29=(−7)⋅5+6-29=(-7)\cdot 5+6−29=(−7)⋅5+6. כלומר, q=5,r=6q=5,r=6q=5,r=6.
  5. עבור a=7,b=29a=7,b=29a=7,b=29 נקבל כי 7=29⋅0+77=29\cdot 0+77=29⋅0+7. כלומר, q=0,r=7q=0,r=7q=0,r=7. (נשים לב כי r=7<29r=7<29r=7<29 כנדרש)

המחלק המשותף

חילוק עם שארית יעזור לנו לחשב ממג"ב (מחלק משותף גדול ביותר) ותכף נראה זאת.

הגדרה 2 (מחלק משותף גדול ביותר (ממג"ב))

יהיו a,b∈Za,b \in \mathbb{Z}a,b∈Z.
נאמר כי d∈Zd \in \mathbb{Z}d∈Z הוא מחלק משותף גדול ביותר של a,ba,ba,b (ממג"ב של a,ba,ba,b) אם:

  1. מתקיים d>0d>0d>0.
  2. מחלק משותף: d∣ad \mid ad∣a וגם d∣bd \mid bd∣b.
  3. גדול ביותר במובן חלוקה: אם c∈Zc \in \mathbb{Z}c∈Z מקיים ש-c∣ac \mid ac∣a וגם c∣bc \mid bc∣b אזי c∣dc \mid dc∣d.

סימון: אם קיים ddd כנ"ל נסמן d=gcd⁡(a,b)d=\gcd(a,b)d=gcd(a,b) או אפילו d=(a,b)d=(a,b)d=(a,b).

דוגמה

  • על מנת למצוא את (12,18)(12,18)(12,18) נפרק אותם לגורמים: 12=3⋅2212=3\cdot 2^212=3⋅22 ו-18=2⋅3218=2\cdot 3^218=2⋅32. אנחנו רואים שלשניהם יש 222 פעם אחת ו-333 פעם אחת ולכן:
(12,18)=2⋅3=6(12,18)=2\cdot 3 = 6(12,18)=2⋅3=6
  • עבור (0,12)(0,12)(0,12) נגלה כי (0,12)=12(0,12)=12(0,12)=12. אין משהו גדול מ-121212 שמחלק את 121212 ולכן זה מתקיים.
  • הממג"ב של (0,0)(0,0)(0,0) לא מוגדר כלל שכן הוא ∞\infty∞-י.

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

משפט (זהות בזו)

יהיו a,b∈Za,b \in \mathbb{Z}a,b∈Z כאשר a≠0a \neq 0a=0 או b≠0b \neq 0b=0, אזי קיים ממג"ב יחיד d=(a,b)d=(a,b)d=(a,b) ובנוסף קיימים x,y∈Zx,y \in \mathbb{Z}x,y∈Z כך ש-d=xa+ybd=xa+ybd=xa+yb.

דוגמה

עבור (12,18)(12,18)(12,18) נראה כי x=−1,y=1x=-1,y=1x=−1,y=1 ואז 6=−12+18=18−12=8−2=66=-12+18=18-12=8-2=66=−12+18=18−12=8−2=6.

הוכחה:
נתחיל מהוכחת קיום:

הערה (משפט מתורת הקבוצות: עקרון הסדר הטוב)

אם C≠∅C \neq \emptysetC=∅ של שלמים חיוביים אז יש בה איבר מינימלי.

נגדיר קבוצה C={xa+yb∣x,y∈Z∧xa+yb>0}C=\left\{ xa+yb \mid x,y \in \mathbb{Z} \land xa+yb>0 \right\}C={xa+yb∣x,y∈Z∧xa+yb>0}.
נשים לב כי C≠∅C\neq \emptysetC=∅ מכיוון ש

  • אם a≠0a\neq 0a=0 אז עבור x=a,y=0x=a,y=0x=a,y=0 נקבל כי a2+0⋅b>0a^2+0\cdot b>0a2+0⋅b>0 ולכן a2∈Ca^2 \in Ca2∈C.
  • ואם b≠0b \neq 0b=0 אז עבור x=0,y=bx=0,y=bx=0,y=b נקבל כי 0⋅a+b2>00\cdot a+b^2>00⋅a+b2>0 ולכן b2∈Cb^2 \in Cb2∈C.

לכן, לפי עקרון הסדר הטוב קיימים x,y∈Zx,y \in \mathbb{Z}x,y∈Z כך ש-d=xa+ybd=xa+ybd=xa+yb מינימלי ב-CCC.
לפי הגדרת CCC מתקיים כי d>0d>0d>0.
נראה כי d∣ad \mid ad∣a ואז באופן דומה d∣bd \mid bd∣b:
לפי משפט קיימים בהכרח q,r∈Zq,r \in \mathbb{Z}q,r∈Z כך ש-a=d⋅q+ra=d\cdot q+ra=d⋅q+r ו-0<r<d0<r<d0<r<d. נניח בשלילה כי r≠0r\neq 0r=0 ואז:

0<r=a−qd=a−qxa−qyb=a(1−qx)+b(−qy)<d0< r=a-qd=a-qxa-qyb=a(1-qx)+b(-qy)<d0<r=a−qd=a−qxa−qyb=a(1−qx)+b(−qy)<d

זוהי סתירה למינימליות ddd ב-CCC שכן r∈Cr \in Cr∈C לפי הנ"ל.
לכן, בהכרח r=0r=0r=0 ולכן d∣ad \mid ad∣a.

לבסוף, אם c∣ac \mid ac∣a וגם c∣bc \mid bc∣b אזי c∣xa+yb=dc \mid xa+yb=dc∣xa+yb=d מאחד המשפטים ממקודם.
לכן, תמיד קיים ממג"ב עבור a,b∈Za,b\in \mathbb{Z}a,b∈Z כאשר לא שניהם 000 שכן d=(a,b)d=(a,b)d=(a,b).

כעת נעבור להוכחת היחידות:
נניח בשלילה כי קיימים d,d~∈Zd,\tilde{d}\in \mathbb{Z}d,d~∈Z אשר שניהם ממג"בים של a,ba,ba,b.
מכיוון ש-d,d~d,\tilde{d}d,d~ ממג"בים, לפי הגדרה: d∣d~d \mid \tilde{d}d∣d~ וגם d~∣d\tilde{d} \mid dd~∣d. לפי משפט, d=±d~d=\pm \tilde{d}d=±d~ אך מכיוון שלפי הגדרה d,d~>0d,\tilde{d}>0d,d~>0 אזי d=d~d=\tilde{d}d=d~.
לכן, קיים ממג"ב יחיד.
∎

הערה (הזהרה)

הממג"ב עצמו יחיד אך ה-x,yx,yx,y בצירוף d=xa+ybd=xa+ybd=xa+yb אינם יחידים.
דוגמה: 1=2⋅3+(−1)⋅5=(−3)⋅3+2⋅51=2\cdot 3+(-1)\cdot 5=(-3)\cdot 3+2 \cdot 51=2⋅3+(−1)⋅5=(−3)⋅3+2⋅5.

הערה (עוד הזהרה)

ראינו במשפט שאם d=(a,b)d=(a,b)d=(a,b) אז קיימים x,y∈Zx,y \in \mathbb{Z}x,y∈Z כך ש-d=xa+ybd=xa+ybd=xa+yb.
האם הכיוון ההפוך נכון? ממש ממש לא.
למשל: x=2,y=1x=2,y=1x=2,y=1 אז 2≠8=2⋅2+1⋅42\neq 8=2\cdot 2+1\cdot 42=8=2⋅2+1⋅4 ואנו יודעים כי 2=(2,4)2=(2,4)2=(2,4).

הערה (להערה)

מתי הכיוון ההפוך כן נכון? כאשר מובטח לנו שהצירוף x0a+y0b=dx_{0}a+y_{0}b=dx0​a+y0​b=d הוא המינימלי מבין כל הצירופים x,y∈Zx,y \in \mathbb{Z}x,y∈Z.

מסקנה (מההערה)

xa+yb=1 כך ש-x,y∈Zקיימים   ⟺  (a,b)=1xa+yb=1\R{\text{ כך ש-}}x,y\in \mathbb{Z}\R{\text{קיימים }}\iff (a,b)=1xa+yb=1 כך ש-x,y∈Zקיימים ⟺(a,b)=1

בואו נמצא ממ"גב

Algorithm 6 Euclidean Algorithm (אלגוריתם אוקלידס)

1:function GCD(a,ba, ba,b)

2:if b=0b = 0b=0 then

3:

4:return aaa

5:else

6:

7:return GCD(b,a mod bb, a \bmod bb,amodb)

8:end if

9:end function

דוגמה

נמצא את הממג"ב של (112,42)(112,42)(112,42) באופן רקורסיבי:

(1)    112=42⋅2+28(2)    42=28⋅1+14(3)    28=14⋅2+0\begin{align*} (1)\;\; & 112=42\cdot 2 +28 \\ (2)\;\; & 42=28\cdot 1 + 14 \\ (3)\;\; & 28 = 14\cdot 2+ 0 \end{align*}(1)(2)(3)​112=42⋅2+2842=28⋅1+1428=14⋅2+0​

השארית האחרונה שלא התאפסה היא הממג"ב ולכן 14=(112,42)14=(112,42)14=(112,42).

ע"י חזרה על האיטרציות מהסוף להתחלה נוכל למצוא x,yx,yx,y:

14=↓(2)42−28⋅1=↓(1)42−(112−42⋅2)⋅1=3⋅42+(−1)⋅11214\underset{\begin{matrix} \downarrow \\ (2) \end{matrix}}{=}42-28\cdot 1 \underset{\begin{matrix} \downarrow \\ (1) \end{matrix}}{=}42-(112-42\cdot 2)\cdot 1=3\cdot 42 +(-1)\cdot 11214↓(2)​=​42−28⋅1↓(1)​=​42−(112−42⋅2)⋅1=3⋅42+(−1)⋅112

הוכחת נכונות האלגוריתם מתבססת על כך שאם a=bq+ra=bq+ra=bq+r כאשר 0≤r<∣b∣,b≠00\leq r<|b|,b\neq 00≤r<∣b∣,b=0 אז (a,b)=(b,r)(a,b)=(b,r)(a,b)=(b,r). לכן, נדרש להוכיח את הטענה הזו:
הוכחה:
נראה ש-c=(b,r)c=(b,r)c=(b,r) הוא הממג"ב של a,ba,ba,b:

  1. מתקיים כי c>0c>0c>0 שכן ccc ממג"ב.
  2. מחלק משותף: ccc מחלק את bbb מהגדרתו. בנוסף, c∣rc \mid rc∣r מהגדרתו ולכן לפי משפט c∣ac \mid ac∣a שכן a=bq+ra=bq+ra=bq+r.
  3. נניח ש-e∣ae \mid ae∣a וגם e∣be \mid be∣b אז לפי אותו המשפט, מכיוון ש-r=a−bqr=a-bqr=a−bq, מתקיים כי e∣re \mid re∣r.

לכן, (b,r)=(a,b)(b,r)=(a,b)(b,r)=(a,b).
∎

חשבון מודולו nnn

הגדרה 3 (שקול מוד nnn)

יהיו a,b∈Za,b \in \mathbb{Z}a,b∈Z.
נאמר ש-aaa שקול ל-bbb מוד nnn (או aaa קונגורטי ל-bbb או aaa שווה ל-bbb מוד nnn) ונסמן a=b ⁣ ⁣ ⁣(mod  n)a=b\pmod{n}a=b(modn) או a≡nba\equiv_{n}ba≡n​b אם ל-aaa ול-bbb אותה שארית בחלוקה ב-nnn.
כלומר, aaa ו-bbb נבדלים בכפולה שלמה של nnn או במילים אחרות, n∣a−bn \mid a-bn∣a−b.

דוגמה

5∣12−7  ⟹  12≡57  ⟸  12=7+5⋅15 \mid 12-7\implies 12 \equiv_{5}7 \impliedby 12=7+5\cdot 1 5∣12−7⟹12≡5​7⟸12=7+5⋅1

יהיה לנו סימון אם אנחנו מדברים על שאריות בחלוקה ב-nnn ובעצם פה אנחנו עוברים לעולם חדש. עד כה היינו ב-Z\mathbb{Z}Z וכעת נעבור לעולם בשם Zn\mathbb{Z}_{n}Zn​.

הגדרה 4 (סימון)

nשאריות מוד −Zn={0,1,2,…,n−1}n\R{\text{שאריות מוד }}-\mathbb{Z}_{n}=\left\{ 0,1,2,\dots,n-1 \right\}nשאריות מוד −Zn​={0,1,2,…,n−1}

נצייד את Zn\mathbb{Z}_{n}Zn​ בפעולות חיבור וכפל מוד nnn כדי שנוכל להשתמש בו:

4+2=6≡514⋅2=8≡534+2 =6\equiv_{5}1 \qquad \qquad \qquad 4\cdot 2 = 8 \equiv_{5}34+2=6≡5​14⋅2=8≡5​3 7+12=19≡54≡52+2≡57+127+12=19\equiv _{5}4\equiv_{5}2+2\equiv_{5}7+127+12=19≡5​4≡5​2+2≡5​7+12
משפט

a+b≡n(a ⁣ ⁣ ⁣(mod  n))+(b ⁣ ⁣ ⁣(mod  n))a+b\equiv_{n}(a\pmod{n})+(b\pmod{n})a+b≡n​(a(modn))+(b(modn)) a⋅b≡n(a ⁣ ⁣ ⁣(mod  n))⋅(b ⁣ ⁣ ⁣(mod  n))a\cdot b\equiv_{n}(a\pmod{n})\cdot(b\pmod{n})a⋅b≡n​(a(modn))⋅(b(modn))

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

דוגמה

עבור Z2={0,1}\mathbb{Z}_{2}=\left\{ 0,1 \right\}Z2​={0,1} נקבל כי:

\begin{array}{} 2\mod+ & \begin{array}{} 0 & 1 \end{array} \\ \begin{array}{} \quad \quad \quad 0 \\ \quad \quad \quad 1 \end{array} & \begin{array}{|c|c|} \hline 0 & 1 \\ \hline 1 & 0 \\ \hline \end{array} \end{array}
הערה

נשים לב כי זהו שער XORXORXOR וכפל מודולו 2 הוא השער ANDANDAND.

מסקנה

aℓ≡n(a ⁣ ⁣ ⁣(mod  n))ℓa^\ell\equiv_{n} (a\pmod{n})^{\ell}aℓ≡n​(a(modn))ℓ
הערה

אסור לבצע מודולו על החזקה. במבחן אם נעשה את זה באמריקאיות נגיע למסיח.

דוגמה

30311 ⁣ ⁣ ⁣(mod  10)=↓מסקנה(303 ⁣ ⁣ ⁣(mod  10))11=311=34⋅2+3=(34)2⋅33≡1012⋅7≡107303^{11}\pmod{10} \underset{\begin{matrix} \downarrow \\ \R{\text{מסקנה}} \end{matrix}}{=} (303\pmod{10})^{11}=3^{11}=3^{4\cdot 2 +3}=(3^4)^2\cdot 3^3\equiv_{10}1^2\cdot 7\equiv_{10}730311(mod10)↓מסקנה​=​(303(mod10))11=311=34⋅2+3=(34)2⋅33≡10​12⋅7≡10​7
טענה

יהי 0≠a∈Zn0\neq a\in \mathbb{Z}_{n}0=a∈Zn​.
למערכת ax≡n1ax\equiv_{n}1ax≡n​1 קיים פתרון 1=(a,n)  ⟺  1=(a,n)\iff1=(a,n)⟺. (כלומר, a,na,na,n זרים)

הערה

במידה וקיים, הפתרון הוא יחיד מוד nnn. (מוזמנים להוכיח כתרגיל)

הוכחה:
כיוון :  ⟸  :\impliedby:⟸ נתון שקיים x∈Znx \in \mathbb{Z}_{n}x∈Zn​ כך ש-ax≡n1ax\equiv_{n}1ax≡n​1. כלומר, קיים y∈Zy \in \mathbb{Z}y∈Z כך ש-ax−1=nyax-1=nyax−1=ny.
לכן: ax+(−y)n=1ax+(-y)n=1ax+(−y)n=1. לפי משפט, (a,n)=1(a,n)=1(a,n)=1.
כיוון :  ⟹  :\implies:⟹ נתון (a,n)=1(a,n)=1(a,n)=1. לפי אותו המשפט, קיימים x,y∈Zx,y \in \mathbb{Z}x,y∈Z כך ש-ax+yn=1ax+yn=1ax+yn=1.

ax ⁣ ⁣ ⁣(mod  n)+0=(ax ⁣ ⁣ ⁣(mod  n))+(yn ⁣ ⁣ ⁣(mod  n))=(ax+yn) ⁣ ⁣ ⁣(mod  n)=1 ⁣ ⁣ ⁣(mod  n)=1ax\pmod{n}+0=(ax \pmod{ n})+(yn \pmod{ n})=(ax+yn)\pmod{n}= 1\pmod{n}=1ax(modn)+0=(ax(modn))+(yn(modn))=(ax+yn)(modn)=1(modn)=1

ולכן, ax≡n1ax\equiv_{n}1ax≡n​1.
∎

תרגיל (מבחינה)

האם קיים 0≤x≤3600\leq x\leq 3600≤x≤360 כך ש-7x≡36047x\equiv_{360}47x≡360​4?

נרצה לקשר את זה למה שכרגע עשינו. נשים לב כי יש לנו 444 ולא 111 בצד המתאים של המשוואה. עדיין נפתור ל-111 ואז פשוט נכפיל ב-444.
ראשית נחפש פתרון למשוואה 7x~≡36017\tilde{x}\equiv_{360}17x~≡360​1:
נבצע אוקלידס מוכלל: 360=7⋅51+3360=7\cdot 51+3360=7⋅51+3 (כאשר q=51,r=3q=51,r=3q=51,r=3) ואז 7=3⋅2+17=3\cdot 2+17=3⋅2+1 ולכן (360,7)=1(360,7)=1(360,7)=1. לכן, לפי משפט, קיים פתרון למשוואה.

1=7−3⋅2=7−(360−7⋅51)⋅2=103⋅7+(−2)⋅3601=7-3\cdot 2=7 -(360-7\cdot 51)\cdot 2=103\cdot 7 +(-2)\cdot 3601=7−3⋅2=7−(360−7⋅51)⋅2=103⋅7+(−2)⋅360

נבצע  ⁣ ⁣ ⁣(mod  360)\pmod{360}(mod360) על המשוואה:

1≡360103⋅7  ⟹  x~=103  ⟹  4≡360103⋅7⋅4≡36052⋅71\equiv_{360}103 \cdot 7 \implies \tilde{x}=103\implies 4\equiv_{360}103\cdot 7 \cdot 4\equiv_{360} 52\cdot 71≡360​103⋅7⟹x~=103⟹4≡360​103⋅7⋅4≡360​52⋅7

ואז, x=52x=52x=52.