תרגול 2 - אלגוריתם אוקלידס וחשבון שארית (מודולו) — אלגברה מודרנית ח'

תרגיל

יהיו $a,b,c\in \mathbb{Z}$ . ויהי $p \in \mathbb{Z}$ ראשוני. הוכיחו:
א. אם $a \mid bc$ ו- $(a,b)=1$ אזי $a \mid c$ .
ב. אם $p \mid ab$ אז $p \mid a$ או $p \mid b$ .
ג. מתקיים: $(ac,bc)=|c|(a,b)$ .
ד. אם $a \mid c$ ו- $b \mid c$ וגם $(a,b)=1$ אזי $ab \mid c$ .

הוכחה א':

\begin{align*} (a,b)=1 & \implies \exists x,y \in \mathbb{Z}:\; 1=xa+yb & \R{\text{זהות בזו}} \\ & \implies c=xac+ybc & c\R{\text{כפל ב-}} \\ a \mid bc &\implies \exists k_{1} \in \mathbb{Z}:\;bc=ak_{1} & \R{\text{הגדרת חלוקה}} \\ & \implies c=xac+yak_{1}=a(xc+yk_{1}) & \R{\text{הצבה}} \\ k=(xc+yk_{1})\in \mathbb{Z}& \implies \exists k \in \mathbb{Z}:\; c=ak & \R{\text{סימון}} \\ & \implies a \mid c & \R{\text{הגדרת חלוקה}} \end{align*}

∎

הוכחה ב':
נתון כי $p \mid ab$ . נחלק למקרים:

אם $p \mid a,b$ אז סיימנו.
אם בה"כ $p \nmid a$ אזי, $(p,a)=1$ ולכן מסעיף א', $p \mid b$ וסיימנו.

∎

הערה

עבור $p$ ראשוני המחלק את $p \mid a_{1}a_{2}\cdots a_{n}$ אזי קיים $1\leq i\leq n$ כך ש- $p \mid a_{i}$ .
ההוכחה באינדוקציה :) (ומזווית של מדמח תהליך זה יקח לנו $\log n$ פעולות)

הוכחה ד':
דרך 1:
נתון כי $(a,b)=1$ ולכן קיימים $x_{0},y_{0} \in \mathbb{Z}$ כך ש: $1=ax_{0}+by_{0}$ . נכפיל ב- $c$ לקבלת: $c=ax_{0}c+by_{0}c$ .
קיימים $q_{1},q_{2} \in \mathbb{Z}$ כך ש- $bq_{1}=c,aq_{2}=c$ אזי: $c=abq_{1}x_{0}+abq_{2}y_{0}$ ולכן: $ab(q_{1}x_{0}+q_{2}y_{0})=c$ .
נגדיר $k=q_{1}x_{0}+q_{2}y_{0}\in \mathbb{Z}$ ולכן, $abk=c$ ולכן, לפי הגדרה, $ab \mid c$ .

דרך 2:

ab=\frac{ab}{(a,b)}=[a,b] \mid c

∎

תרגיל

חשבו את $(101,56)$ ומצאו $x,y \in \mathbb{Z}$ כך שמתקיים $(101,56)=101x+56y$ .

נפעיל את אלגוריתם אוקלידס:

101=56\cdot 1+45 \implies 56=45\cdot 1+11\implies 45=11\cdot 4+1 \implies 11=1\cdot 11+0

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

1=\underline{45}-\underline{11}\cdot 4=\underline{45}-4(\underline{56}-\underline{45})=\underline{101}-\underline{56}-4(\underline{56}-(\underline{101}-\underline{56}))=\underline{101}-\underline{56}-4(2\cdot \underline{56}-\underline{101})

1=5\cdot \underline{101}+(-9)\cdot \underline{56}

לכן, $(101,56)=1$ ו- $x=5,y=-9$ .

הערה (חישוב

[101,56]

)

[101,56]=\frac{101\cdot 56}{(101,56)}=101\cdot 56

תרגיל

חשבו את ספרת האחדות של $(333)^{333}$ .

הערה

אם היינו מנסים למצוא את המספר הזה היינו מגלים כי הוא בעל $999$ ספרות (כמעט אלף-ספרתי)
נשים לב כי בנוסף מתקיים כי $2^{333}<333^{333}$ . בנוסף, אם היינו מוצאים את מספר החלקיקים בקיום היינו מגלים כי הוא קטן מ- $2^{333}$ . אנו יודעים בוודאות כי מספר החלקיקים במחשב קטן ממספר החלקיקים ביקום ולכן בוודאות לא היינו מצליחים לשמור את כל המספר במחשב. (זוהי הוכחת אי-חישוב)

הערה (להערה)

ניתן לחשב את המספר בתוך $string$ שכן אז זה יתפוס רק $1000$ בתים :) זה פשוט יקח מלאאאאא זמן

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

ננסה להשיג את ספרת היחידות באמצעות $\pmod{10}$ .

(333)^{333}\pmod{10} \underset{\begin{matrix} \downarrow \\ \mod{}\R{\text{תכונות}} \end{matrix}}{=}(333 \pmod{10})^{333}= 3^{333}\pmod{10}

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

3 \qquad 3^2=9 \qquad 3^3=27\equiv_{10}7 \qquad 3^4=81\equiv_{10} 1

כל רביעיה שכזו נותנת $1$ במודולו $10$ .

3^{333}\pmod{10}=(3\cdot 3 \cdot 3 \cdot 3)(3\cdot 3 \cdot 3 \cdot 3)\cdots (3 \cdot 3 \cdot 3 \cdot 3)\cdot 3^r \pmod{10}

כאשר $0\leq r\leq 3$ .

333=4\cdot 83+1 \implies r=1

לכן מתקיים:

333^{333}\equiv_{10}3^{333}\pmod{10}\equiv_{10}3^{4\cdot 83+1}\pmod{10}\equiv_{10}1^{83}\cdot 3^{1}\pmod{ 10}\equiv_{10}3

תרגיל

חשבו את ספרת היחידות של $12^{84}$

12^{84}\equiv_{10}2^{84}\pmod{10}

נמצא את המחזור של 2:

2,2^2=4,2^3=8,2^4=16\equiv_{10}6,2^5=12\equiv_{10}=2

נשים לב כי כל $5$ כאלו הם $2$ .

2^{84}\equiv_{10}2^{16\cdot 5+4}\equiv_{10}2^{16+4}\equiv_{10}2^{20}\equiv_{10}2^{4}\equiv_{10} 6

תרגיל

הוכחה א':

\begin{align*} (a,b)=1 & \implies \exists x,y \in \mathbb{Z}:\; 1=xa+yb & \R{\text{זהות בזו}} \\ & \implies c=xac+ybc & c\R{\text{כפל ב-}} \\ a \mid bc &\implies \exists k_{1} \in \mathbb{Z}:\;bc=ak_{1} & \R{\text{הגדרת חלוקה}} \\ & \implies c=xac+yak_{1}=a(xc+yk_{1}) & \R{\text{הצבה}} \\ k=(xc+yk_{1})\in \mathbb{Z}& \implies \exists k \in \mathbb{Z}:\; c=ak & \R{\text{סימון}} \\ & \implies a \mid c & \R{\text{הגדרת חלוקה}} \end{align*}

∎

הוכחה ב':
נתון כי $p \mid ab$ . נחלק למקרים:

אם $p \mid a,b$ אז סיימנו.
אם בה"כ $p \nmid a$ אזי, $(p,a)=1$ ולכן מסעיף א', $p \mid b$ וסיימנו.

∎

הערה

דרך 2:

ab=\frac{ab}{(a,b)}=[a,b] \mid c

∎

תרגיל

חשבו את $(101,56)$ ומצאו $x,y \in \mathbb{Z}$ כך שמתקיים $(101,56)=101x+56y$ .

נפעיל את אלגוריתם אוקלידס:

101=56\cdot 1+45 \implies 56=45\cdot 1+11\implies 45=11\cdot 4+1 \implies 11=1\cdot 11+0

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

1=\underline{45}-\underline{11}\cdot 4=\underline{45}-4(\underline{56}-\underline{45})=\underline{101}-\underline{56}-4(\underline{56}-(\underline{101}-\underline{56}))=\underline{101}-\underline{56}-4(2\cdot \underline{56}-\underline{101})

1=5\cdot \underline{101}+(-9)\cdot \underline{56}

לכן, $(101,56)=1$ ו- $x=5,y=-9$ .

הערה (חישוב

[101,56]

)

[101,56]=\frac{101\cdot 56}{(101,56)}=101\cdot 56

תרגיל

חשבו את ספרת האחדות של $(333)^{333}$ .

הערה

הערה (להערה)

ניתן לחשב את המספר בתוך $string$ שכן אז זה יתפוס רק $1000$ בתים :) זה פשוט יקח מלאאאאא זמן

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

ננסה להשיג את ספרת היחידות באמצעות $\pmod{10}$ .

(333)^{333}\pmod{10} \underset{\begin{matrix} \downarrow \\ \mod{}\R{\text{תכונות}} \end{matrix}}{=}(333 \pmod{10})^{333}= 3^{333}\pmod{10}

3 \qquad 3^2=9 \qquad 3^3=27\equiv_{10}7 \qquad 3^4=81\equiv_{10} 1

כל רביעיה שכזו נותנת $1$ במודולו $10$ .

3^{333}\pmod{10}=(3\cdot 3 \cdot 3 \cdot 3)(3\cdot 3 \cdot 3 \cdot 3)\cdots (3 \cdot 3 \cdot 3 \cdot 3)\cdot 3^r \pmod{10}

כאשר $0\leq r\leq 3$ .

333=4\cdot 83+1 \implies r=1

לכן מתקיים:

333^{333}\equiv_{10}3^{333}\pmod{10}\equiv_{10}3^{4\cdot 83+1}\pmod{10}\equiv_{10}1^{83}\cdot 3^{1}\pmod{ 10}\equiv_{10}3

תרגיל

חשבו את ספרת היחידות של $12^{84}$

12^{84}\equiv_{10}2^{84}\pmod{10}

נמצא את המחזור של 2:

2,2^2=4,2^3=8,2^4=16\equiv_{10}6,2^5=12\equiv_{10}=2

נשים לב כי כל $5$ כאלו הם $2$ .

2^{84}\equiv_{10}2^{16\cdot 5+4}\equiv_{10}2^{16+4}\equiv_{10}2^{20}\equiv_{10}2^{4}\equiv_{10} 6