שינויים
/* דיפי-הלמן */
ההרצאות מבוססות באופן כללי על הספר [http://abstract.ups.edu/aata/ Abstarct Algebra - Theory and Applications by Thomas W. Judson]
* [[מדיה:19CSASnotes.pdf|סיכום ההרצאות מ2019 ע"י ספיר ביתן]]* [[מדיה:21CSASnotes.pdf|סיכום ההרצאות מ2021 ע"י רועי אוסקר]] =מבחנים לדוגמא= *[[מדיה:17ASExmTest1.pdf|מבחן לדוגמא 1 תשע"ח]]**[[מדיה:17ASExmTest1Sol.pdf|פתרון מבחן לדוגמא 1 תשע"ח]]*[[מדיה:17ASExmTest2.pdf|מבחן לדוגמא 2 תשע"ח]]**[[מדיה:17ASExmTest2Sol.pdf|פתרון מבחן לדוגמא 2 תשע"ח]]*[[מדיה:17ASExmTest3.pdf|מבחן לדוגמא 3 תשע"ח]]**[[מדיה:17ASExmTest3Sol.pdf|פתרון מבחן לדוגמא 3 תשע"ח]]*[[מדיה:17ASTestA.pdf|מבחן מועד א' תשע"ח]]*[[מדיה:17ASTestB.pdf|מבחן מועד ב' תשע"ח]]*[[מדיה:17ASTestC.pdf|מבחן מועד ג' תשע"ח]]*[[מדיה:18ASTestA.pdf|מבחן מועד א' תשע"ט]]**[[מדיה:18ASTestASol.pdf|פתרון מועד א' תשע"ט]]*[[מדיה:19ASTestB.pdf|מבחן מועד ב' תשע"ט]]**[[מדיה:18ASTestBSol.pdf|פתרון מועד ב' תשע"ט]]*[[מדיה:20ASTestA.pdf|מבחן מועד א' תש"ף]]*[[מדיה:20ASTestB.pdf|מבחן מועד ב' תש"ף]]*[[מדיה:21ASTestA.pdf|מבחן מועד א' תשפ"א]]**[[מדיה:21ASTestASol.pdf|פתרון מבחן מועד א' תשפ"א]]*[[מדיה:21ASTestB.pdf|מבחן מועד ב' תשפ"א]]*[[מדיה:21ASTestC.pdf|מבחן מועד ג' תשפ"א]]*[[מדיה:22ASTestA.pdf|מבחן מועד א' תשפ"ב]]*[[מדיה:22ASTestB.pdf|מבחן מועד ב' תשפ"ב]] * [[89-214 מבחנים|מבחנים משנים קודמות]] =נושאי ההרצאות= [https://www.youtube.com/playlist?list=PLzSjdxrZD_hka_9hBlLKybpwG_5_T7FaY פלייליסט של הרצאות קבוצה 01 תשפ"א] [https://www.youtube.com/playlist?list=PLzSjdxrZD_hlVTrX-RcrpYiTMyQBmIihV פלייליסט של הרצאות קבוצה 02 תשפ"א] ==הרצאה 1 הקדמה; הסבר על קידוד והצפנה, מבוא למבנים אלגבריים ===
*קידוד הוא שיטה להעברת מידע ובין היתר מטרתו היא להבטיח את נכונות המידע ולזהות (ולתקן) שגיאות.
*תזכורת לגבי חבורותחבורה המקיימת את חוק החילוף נקראת חבורה אבלית, קומוטטיבית או חילופית *תכונת הצמצום: תהי חבורה G, אזי לכל <math>a,b,c\in G</math> אם <math>ab=ac</math> אזי <math>b=c</math>.**הוכחה: נכפול באיבר ההופכי <math>a^{-1}(ab)=a^{-1}(ac)</math> ונשתמש באסוציאטיביות ובאיבר הנייטרלי. *יחידות האיבר ההופכי: נובע מתכונת הצמצום שלכל איבר בחבורה קיים איבר הופכי יחיד.**הוכחה: אם <math>ab=ac=e_G</math> אזי <math>b=c</math>. *דוגמאות לחבורות:**<math>S_n</math> חבורת הפונקציות ההפיכות מקבוצה בגודל n לעצמה עם פעולת ההרכבה.**<math>GL_n(\mathbb{ZF},)</math> חבורת המטריצות ההפיכות עם כפל מטריצות.**<math>\mathbb{Z}_n,</math> חבורת השלמים עם חיבור.**<math>\mathbb{GLZ}_n</math> חבורת השאריות עם חיבור מודולו n. ===מכפלה קרטזית של חבורות=== *תהיינה חבורות <math>G,H</math> המכפלה הקרטזית של החבורות <math>G\times H</math> (אוסף הזוגות הסדורים) היא חבורה עם הפעולה הבאה: <math>(g_1,h_1)\cdot_{SLG\times H}_n(g_2,S_nh_2)=(g_1\cdot_G g_2,h_1\cdot_H h_2)</math>.*===תת חבורות; קווטרניונים, מעגל היחידה ושורשי יחידה, המרוכבים ללא אפס כתת ===*הגדרה: תהי חבורה G. תת קבוצה <math>H\subseteq G</math> נקראת תת חבורה של מטריצות ממשיות בגודל 2 על 2G אם היא חבורה ביחס לפעולה של G.
**לכל שני איברים <math>a,b\in H</math> מתקיים כי <math>ab^{-1}\in H</math>.
*הוכחת הקריטריון המקוצר:
*בכיוון ראשון נניח כי H תת חבורה:
**נוכיח כי <math>e_G\in H</math>.
***נניח H תת חבורה, לכן קיים בה איבר נייטרלי <math>e_H</math>.
***כיוון שמדובר באיבר נייטרלי בH מתקיים כי <math>e_H\cdot e_H=e_H</math>.
***מצד שני ברור ש<math>e_H\cdot e_G=e_H</math>.
***לכן <math>e_H\cdot e_H=e_H\cdot e_G</math> ולפי תכונת הצמצום נובע ש <math>e_H=e_G</math>.
**נוכיח כי לכל שני איברים <math>a,b\in H</math> מתקיים כי <math>ab^{-1}\in H</math>.
***יהיו <math>a,b\in H</math>.
***קיים בH הופכי לb, נקרא לו c.
***לכן <math>bc=bb^{-1}=e_G</math> (הרי הוכחנו כבר ש<math>e_H=e_G</math>).
***שוב לפי תכונת הצמצום נובע כי <math>b^{-1}=c\in H</math>.
***לפי הסגירות של H נובע כי <math>ab^{-1}\in H</math>.
*בכיוון השני, נוכיח כי H תת חבורה:
**סגירות:
***יהיו <math>a,b\in H</math>.
***ידוע כי <math>e_G\in H</math>, לכן <math>e_G\cdot b^{-1}\in H</math>, כלומר <math>b^{-1}\in H</math>.
***לכן <math>a\cdot \left(b^{-1}\right)^{-1}\in H</math> כלומר <math>a\cdot b \in H</math>.
**אסוציאטיביות:
***נתון כי הפעולה אסוציאטיבית, הרי זו הפעולה של G וG חבורה.
**איבר נייטרלי:
***נתון כי <math>e_G\in H</math>.
**איברים הופכיים:
***יהי <math>a\in H</math>.
***לכן <math>a^{-1}=e_G\cdot a^{-1}\in H</math> בדומה להוכחת הסגירות.
*תת חבורות;
**<math>SL_n(\mathbb{F})</math> חבורת המטריצות בעלות דטרמיננטה שווה 1, עם כפל מטריצות.
**קווטרניונים <math>\left\{
\pm\begin{pmatrix}1&0\\0&1\end{pmatrix},
\pm\begin{pmatrix}0&1\\-1&0\end{pmatrix},
\pm\begin{pmatrix}0&i\\i&0\end{pmatrix},
\pm\begin{pmatrix}i&0\\0&-i\end{pmatrix}
\right\}\subseteq GL_2\left(\mathbb{C}\right)</math>
**<math>\mathbb{C}\setminus \{0\}=\left\{\begin{pmatrix}a&b\\-b&a\end{pmatrix}:(a,b)\neq (0,0)\right\}\subseteq GL_2\left(\mathbb{R}\right)</math>.
**<math>\{z\in\mathbb{C}:|z|=1\}\subseteq \mathbb{C}\setminus \{0\}</math> מעגל היחידה.
===תת חבורות ציקליות===
*כתיב אקספוננט <math>g^n=g\cdots g</math> או כפל <math>ng=g+\cdots+g</math> בהתאם לסימון פעולת החבורה.
*הערה: קל להוכיח כי <math>(a^{-1})^n=(a^n)^{-1}</math>
*הומומורפיזמיםתהי חבורה G, איזומורפיזמיםלכל <math>a\in G</math> נגדיר את הסדר של האיבר <math>o(a)</math> בתור החזקה החיובית הקטנה ביותר k עבורה <math>a^k=e_G</math>. אם אין חזקה כזו, ניתן לומר שהסדר הוא אינסוף.*תמונה של הומומורפיזם היא תת חבורהדוגמאות:**<math>o(e_G)=1</math>.*משפט קיילי- כל חבורה איזומורפית לתת חבורה *ב<math>\mathbb{Z}_5</math> מתקיים כי <math>o(2)=5</math>.**ב<math>\mathbb{Z}</math> הסדר של חבורת תמורותכל איבר שונה מאפס הוא אינסוף.
*תהי חבורה G, ויהי <math>a\in G</math>. תת החבורה הציקלית הנוצרת על ידי a הינה <math><a>=\{a^n|n\in\mathbb{Z}\}</math>*הוכחה שאכן מדובר בתת חבורה מחלקת :**<math>e_G=a^0\in<a></math>.**יהיו <math>a^n,a^k\in<a></math> אזי <math>a^n\cdot (a^k)^{-1}=a^n\cdot (a^{-1})^k=a^{n-k}\in<a></math>. *תהי חבורה למחלקות שקילות G, אזי סדר כל איבר הוא גודל החבורה הציקלית שהוא יוצר, כלומר <math>|<a>|=o(קוסטיםa) שוות בגודלן לגודל תת </math>.*הוכחה:**ראשית נוכיח עבור המקרה בו סדר האיבר סופי <math>o(a)=n</math>.***רוצים להוכיח כי <math><a>=\{e_G,a,a^2,...,a^{n-1}\}</math> וכי כל האיברים בקבוצה זו שונים זה מזה (אחרת כמות האיברים קטנה יותר מn).***ברור שהחזקות של a שייכות לתת החבורההציקלית.*אינדקס **יהי k כלשהו, נסמן בr את השארית <math>r=k \mod n</math> כלומר <math>k=pn+r</math> עבור <math>p\in\mathbb{Z}, 0\leq r\leq n-1</math>.***<math>a^k=(a^n)^pa^r=e_G^pa^r=a^r</math>.***כעת נניח כי קיימות שתי חזקות שונות <math>0\leq r_1<r_2\leq n-1</math> כך ש <math>a^{r_1}=a^{r_2}</math>.***לכן <math>a^{r_2-r_1}=e_G</math>.***אבל <math>r_2-r_1\leq n-1 < n</math> בסתירה לכך ש<math>o(a)=n</math>.**כעת נניח כי סדר האיבר הוא אינסוף, ונוכיח כי גודל תת החבורה הציקלית שהוא יוצר הוא מספר מחלקות השקילות שהיא מייצרת בחבורהאינסוף.***נניח בשלילה ש <math><a></math> סופית, וזה בדיוק גודל החבורה חלקי לכן לפחות שתי חזקות שונות של a נותנות אותו איבר.***נסמן <math>n<k</math> כך ש <math>a^n=a^k</math>.***לכן <math>a^{k-n}=e_G</math> בסתירה לכך שסדר האיבר הוא אינסוף. *מסקנה: תהי חבורה '''סופית''' G, אזי לכל איבר בחבורה יש סדר סופי.**הוכחה: גודל תת החבורה הציקלית חייב להיות סופי. *תת חבורות ציקליות:**<math>2\mathbb{Z}</math>.**<math>\{z\in\mathbb{C}:z^n=1\}\subseteq \mathbb{C}\setminus \{0\}</math> שורשי היחידה מסדר n. ==הרצאה 3 חבורת תמורות, סימן התמורה; פרק 5 מ[http://abstract.ups.edu/aata/ הספר] == ===סימן של תמורה===*נביט בחבורת התמורות <math>S_n</math>.*עבור <math>f\in S_n</math> נגדיר את הסימן <math>\mathrm{sign}(f):=\Pi_{i\neq j}\frac{x_{f(i)}-x_{f(j)}}{x_i-x_j}</math>.*הסימן של תמורה הוא תמיד פלוס או מינוס 1.*אם סימן התמורה הוא מינוס אחד אומרים שהיא '''אי-זוגית''' או '''שלילית''', ואם הסימן הוא אחד אומרים שהיא '''זוגית''' או '''חיובית'''. *כפליות הסימן: תהיינה שתי תמורות <math>f,g\in S_n</math>, אזי <math>\mathrm{sign}(f\circ g)=\mathrm{sign}(f)\cdot\mathrm{sign}(g)</math>.**הוכחה:**<math>\mathrm{sign}(f\circ g)=\Pi_{i\neq j}\frac{x_{f(g(i))}-x_{f(g(j))}}{x_i-x_j}=\Pi_{i\neq j}\frac{x_{f(g(i))}-x_{f(g(j))}}{x_{g(i)}-x_{g(j)}}\cdot\frac{x_{g(i)}-x_{g(j)}}{x_i-x_j}</math>**כיוון שg חח"ע ועל,אוסף הזוגות <math>i\neq j</math> שווה לאוסף הזוגות <math>g(i),g(j)</math>, ולכן <math>\Pi_{i\neq j}\frac{x_{f(g(i))}-x_{f(g(j))}}{x_{g(i)}-x_{g(j)}}=\mathrm{sign}(f)</math>.**סה"כ קיבלנו <math>\mathrm{sign}(f\circ g)=\mathrm{sign}(f)\cdot\mathrm{sign}(g)</math>. <videoflash>Lmk0izbQR08</videoflash> ===מחזורים===*מחזור <math>(a_1\ a_2\ \cdots \ a_k)</math> מייצג את התמורה f המקיימת <math>f(a_1)=a_2,...,f(a_{k-1})=a_k,f(a_k)=a_1</math> ולכל איבר אחר <math>f(a)=a</math>.*לדוגמא: <math>\begin{pmatrix}1&2&3&4&5\\4&2&5&3&1\end{pmatrix}=(1\ 4\ 3\ 5)\in S_5</math> *כל תמורה ניתן להציג כהרכבה של מחזורים זרים, ואת תמורה הזהות ניתן להציג כ<math>(1)</math>. *חילוף הוא מחזור באורך 2.*חילוף הוא תמורה אי זוגית.**נוכיח עבור <math>f=(1\ 2)\in S_n</math>. (זה מספיק כיוון שהשם של האיברים לא משנה.)**<math>\mathrm{sign}(f)=\left(\frac{x_2-x_1}{x_1-x_2}\cdot\frac{x_2-x_3}{x_1-x_3}\cdots \frac{x_2-x_n}{x_1-x_n}\right)\cdot\left(\frac{x_1-x_3}{x_2-x_3}\cdots\frac{x_1-x_n}{x_2-x_n}\right)\left(\cdot\frac{x_3-x_4}{x_3-x_4}\cdots\frac{x_{n-1}-x_n}{x_{n-1}-x_n}\right)=-1</math> *כל מחזור ניתן להציג כהרכבה של חילופים:**<math>(a_1\ a_2\ \cdots \ a_k)=(a_1\ a_2)(a_2\ a_3)\cdot (a_{k-1}\ a_k)</math>**כל איבר שלא מוזכר במחזור נשלח לעצמו, ונציב בשני הצדדים את <math>a_1,...,a_{k-1}</math> ונראה כי הפונקציות שוות.**כיוון שמדובר בפונקציה הפיכה, אין צורך לבדוק את האיבר האחרון <math>a_k</math>. *מסקנה: כיוון שסימן כל חילוף הוא שלילי ולפי כפליות הסימן, הסימן של מחזור באורך k הוא <math>(-1)^{k-1}</math>.*דוגמא:**<math>f=\begin{pmatrix}1&2&3&4&5&6&7\\4&2&5&3&1&7&6\end{pmatrix}=(1\ 4\ 3\ 5)(6\ 7)</math>.**לכן <math>\mathrm{sign}(f)=(-1)\cdot(-1)=1</math>, כלומר מדובר בתמורה זוגית. <videoflash>oXntZnnoHfM</videoflash> ==הרצאה 4 הומומורפיזמים, איזומורפיזמים, משפט קיילי, משפט לגראנג'; פרקים 9 ו6 מ[http://abstract.ups.edu/aata/ הספר] == ===הומומורפיזם, איזומורפיזם===*הגדרה: תהיינה שתי חבורות G,H ותהי פונקציה <math>f:G\to H</math>. אזי f נקראת '''הומומורפיזם''' אם לכל <math>a,b\in G</math> מתקיים <math>f(a\cdot_G b)=f(a)\cdot_H f(b)</math>.*בחבורה סופיתשימו לב ש <math>\cdot_G</math> היא הפעולה של G, ו<math>\cdot_H</math> היא הפעולה של H.*הומומורפיזם שהוא פונקציה חח"ע ועל נקרא איזומורפיזם.*הומומורפיזם שומר במובן מסויים על המבנה של החבורה, ואיזומורפיזם מראה שהחבורות הן 'אותה גברת בשינוי אדרת'. *תכונות:**אם <math>f:G\to H</math> הומומורפיזם אזי <math>f(e_G)=e_H</math>.***הוכחה:***<math>f(e_G)=f(e_G\cdot e_G)=f(e_G)\cdot f(e_G)</math>.***לפי תכונת הצמצום <math>f(e_G)=e_H</math>.**אם f הומומופיזם אזי <math>o(f(a))\leq o(a)</math>.***אם <math>o(a)=n</math> אזי <math>a^n=e_G</math>.***לכן <math>f(a^n)=\left(f(a)\right)^n=e_H</math>.***לכן <math>o(f(a))\leq n=o(a)</math>.**אם f איזומורפיזם אזי <math>o(f(a))= o(a)</math>.***נניח כי <math>o(a)=n</math>, הוכחנו ש<math>o(f(a))\leq n</math>.***נסמן <math>o(f(a))=k</math>.***לכן <math>\left(f(a)\right)^k=e_H</math>, ולכן <math>f(a^k)=e_H</math>.***כיוון שאיזומורפיזם הינו פונקציה חח"ע, נובע כי <math>a^k=e_G</math>, כלומר <math>o(a)\leq k</math>.***ביחד <math>k=n</math>.***לבסוף, נובע <math>o(f(a))</math> סופי אם"ם <math>o(a)</math> סופי, ולכן הם שווים גם אם אחד מהם הוא אינסוף.**אם f הומומורפיזם אזי <math>f(a^{-1})=\left(f(a)\right)^{-1}</math> (שימו לב שf לא צריכה להיות הפיכה, והסימון <math>f^{-1}(a)</math> לא בהכרח מוגדר ואינו קשור).***אכן <math>f(a)\cdot f(a^{-1})=f(e_G)=e_H</math>. *הגדרה: גרעין של הומומורפיזם הוא אוסף האיברים שנשלחים לאיבר היחידה.*טענה: התמונה והגרעין של הומומורפיזם הינם תתי חבורות של הטוווח והתחום בהתאמה.**הוכחה לגבי התמונה:**יהי הומומורפיזם <math>f:G\to H</math>.**ראשית, <math>f(e_G)=e_H</math> ולכן <math>e_H\in Im(f)</math>.**שנית, יהיו <math>h_1,h_2\in Im(f)</math> לכן קיימים <math>g_1,g_2\in G</math> כך ש <math>f(g_i)=h_i</math>.**<math>h_1\cdot h_2^{-1}=f(g_1)\cdot \left(f(g_2)\right)^{-1}=f(g_1\cdot g_2^{-1})\in Im(f)</math>.**סה"כ הוכחנו כי <math>Im(f)</math> הינה תת חבורה של <math>H</math>. ===משפט קיילי===*שיכון קיילי:**תהי חבורה <math>G</math> ונגדיר את S להיות חבורת הפונקציות ההפיכות מ<math>G</math> לעצמה עם פעולת ההרכבה (חבורת תמורות).**לכל איבר יש סדר סופי <math>a\in G</math> נגדיר את התמורה המתאימה לו <math>f_a\in S</math> המוגדרת ע"י <math>f_a(x)=a\cdot x</math>.***הוכחה ש<math>f_a\in S</math>:***חח"ע: אם <math>f_a(x_1)=f_a(x_2)</math> אזי <math>a\cdot x_1=a\cdot x_2</math> ולפי תכונת הצמצום <math>x_1=x_2</math>.***על: עבור <math>y\in G</math> מתקיים כי <math>f_a(a^{-1}\cdot y)=a\cdot(a^{-1}\cdot y) =(a\cdot a^{-1})\cdot y=y </math>**הפונקציה <math>\varphi:G\to S</math> השולחת כל איבר לתמורה המתאימה לו <math>\varphi(a)=f_a</math> נקראת '''שיכון קיילי'''. *תכונות:*שיכון קיילי הינו הומומורפיזם.**<math>\varphi(a)\circ\varphi(b)=f_a\circ f_b</math>.**<math>f_a\circ f_b (x)=f_a(f_b(x))=a\cdot (b\cdot x)=(a\cdot b)\cdot (x) = f_{a\cdot b}(x)</math>.**לכן <math>\varphi(a)\circ\varphi(b)=\varphi(a\cdot b)</math>.*שיכון קיילי הינו חח"ע (לכן הוא נקרא שיכון).**אם <math>a\neq b</math>, אזי <math>f_a(e)=a\neq b=f_b(e)</math>.**כלומר <math>f_a\neq f_b</math> ולכן <math>\varphi(a)\neq\varphi(b)</math>. *מסקנה: '''משפט קיילי''' כל חבורה איזומורפית לתת חבורה של חבורת תמורות.**הוכחה: החבורה איזומורפית לתמונה שלה בשיכון קיילי. ===משפט לגראנג'===*תהי חבורה G ותת חבורה צקלית בגודל סדר האיברH. לכן יהי <math>a\in G</math>, נגדיר את '''המחלקה''' <math>a\cdot H:=\{a\cdot h:h\in H\}</math>.*אלה הן למעשה מחלקות השקילות של היחס <math>aRb\iff a^{-1}b\in H</math>**הוכחה שמדובר ביחס שקילות:***רפלקסיביות: <math>a^{-1}a=e\in H</math>***סימטריות: אם <math>a^{-1}b\in H</math> אזי גם ההופכי שלו <math>(a^{-1}b)^{-1}=b^{-1}a\in H</math>***טרנזיטיביות: נניח <math>a^{-1}b,b^{-1}c\in H</math> אזי לפי סגירות גם <math>a^{-1}bb^{-1}c=a^{-1}c\in H</math>**אכן <math>[a]_R=\{b|aRb\}=\{b|a^{-1}b=h\in H\}=\{b|b=ah,h\in H\}=a\cdot H</math>*טענה: לכל איבר <math>a\in G</math> מתקיים כי <math>|a\cdot H|=|H|</math>.**הוכחה: **נביט בפונקציה <math>f:H\to a\cdot H</math> המוגדרת ע"י <math>f(h)=a\cdot h</math> ונוכיח שהיא חח"ע ועל.**חח"ע: אם <math>f(h_1)=f(h_2)</math> אזי <math>a\cdot h_1=a\cdot h_2</math> ולפי תכונת הצמצום <math>h_1=h_2</math>.**על: יהי <math>a\cdot h\in a\cdot H</math>, ברור ש<math>f(h)=a\cdot h</math>. *הגדרה: האינדקס <math>[G:H]</math> מוגדר להיות מספר המחלקות השונות ש<math>H</math> מגדירה.*כיוון שראינו שהמחלקות הן בעצם מחלקות שקילות שוות בגודלן המחלקות את G, נובע '''משפט לגראנג' ''':עבור חבורות סופיות, <math>|G|=|H|\cdot [G:H]</math>.*נובע כי הגודל (סדר ) של כל תת חבורה, מחלק את הגודל (סדר) של החבורה כולה.*יהי <math>a\in G</math> איבר מסדר <math>n</math>. ראינו כי <math>|<a>|=n</math>, ולכן ביחד סדר האיבר מחלק את גודל החבורה.*תהי חבורה מגודל סופית עם מספר ראשוני חייבת להיות של איברים, אזי היא חבורה ציקלית. **אכן, וכל ניקח איבר פרט לאיבר היחידה יוצר אותהשונה מהנייטרלי, הסדר שלו חייב להיות המספר הראשוני (כי לראשוני אין מחלקים), ולכן החבורה הציקלית שלו שווה לכל החבורה.
<videoflash>jKprPSfRysE</videoflash>
*זוג מספרים שלמים <math>a,b</math> נקראים שקולים מודולו n אם קיים שלם <math>q</math> כך ש <math>a=b+q\cdot n</math>
*חלוקה עם שארית: לכל מספר טבעי a ולכל מספר שלם b קיים זוג שלמים '''יחיד''' <math>q,r</math> כך ש <math>b=q\cdot a+r</math> וגם <math>0\leq r < a</math>.
**קיום:
***יהי <math>a\in\mathbb{N}</math>
***אם <math>b=0</math> אזי <math>b=0\cdot a + 0</math>.
***יהי <math>b\geq 0</math> עבורו הטענה נכונה, נוכיח עבור <math>b+1</math>.
***<math>b+1=qa+r+1</math>.
***אם <math>r+1<a</math> סיימנו, אחרת <math>r+1=a</math> ולכן <math>b=(q+1)a+0</math>.
***אם <math>b<0</math> אזי <math>-b=qa+r</math>.
***אם <math>r=0</math> אזי <math>b=(-q)a+0</math> וסיימנו.
***אם <math>0<r<a</math> אזי <math>b=-qa-r=-qa-a+a-r=(-q-1)a+(a-r)</math> כאשר <math>0<a-r<a</math>.
**יחידות:
***נניח <math>b=q_1a+r_1=q_2a+r_2</math>.
***לכן <math>(q_1-q_2)a=r_2-r_1</math>.
***אבל <math>-(a-1)\leq r_2-r_2\leq a-1</math>, ולכן <math>r_2-r_1\neq ka</math>.
***לכן <math>q_1-q_2=0</math> כלומר <math>q_1=q_2</math> ולכן גם <math>r_1=r_2</math>.
*המספר q נקרא '''מנת''' החלוקה והמספר r נקרא '''שארית''' החלוקה.
*יהיו שני טבעיים שלמים <math>a,b</math> ויהיו <math>r_a,r_b</math> השאריות שלהם בחלוקה בn. אזי <math>ab\equiv r_ar_b \mod n</math>**<math>ab=(q_an+r_a)(q_bn+r_b)=(q_aq_bn+r_aq_b+q_ar_b)n+r_ar_b</math>*מסקנה: באותם תנאים, לכל k טבעי מתקיים כי <math>a^k\equiv r_a^k \mod n</math>.
===המחלק המשותף הגדול ביותר===
*לכל שני מספרים טבעיים <math>k<n</math> מתקיים כי <math>gcd(n,k)=gcd(n-k,k)</math>
**נוכיח שכל מספר שמחלק את <math>n,k</math> מחלק גם את <math>n-k,k</math> וההפך, ולכן הגדול ביותר הוא אותו האחד.
**אם <math>a</math> מחלק את <math>n,k</math> אזי <math>n=qa,k=ta</math>, לכן <math>n-k=(q-t)a</math>.
**אם <math>a</math> מחלק את <math>n-k,k</math> אזי <math>n-k=qa,k=ta</math> ולכן <math>n=(q+t)a</math>.
*לכל שני מספריים טבעיים <math>n,k</math> קיימים מספרים שלמים <math>a,b</math> כך ש <math>an+bk=gcd(n,k)</math>
**עבור <math>n=k=1</math> מתקיים כי <math>1\cdot 1 + 0\cdot 1 = 1 = gcd(הוכחה באינדוקציה על הגודל של 1,1)</math>.**נניח שהטענה נכונה לכל <math>n+k<m</math> נוכיח שהיא נכונה עבור <math>n+k=m</math>. **אם <math>n=k סיימנו</math> אזי <math>1\cdot n + 0\cdot k = n =gcd(n, n)=gcd(n,k)</math>.**אחרת , אם <math>n>k<n</math> אזי מתקיים כי <math>gcd(n,k)=gcd(n-k,k)=a(n-k)+bk=an+(b-a)k</math>).**שימו לב שהנחת האינדוקציה התקיימה עבור הזוג <math>n-k,k</math>.
*שני מספרים טבעיים n,k נקראים '''זרים''' אם <math>gcd(n,k)=1</math>
*ב<math>\mathbb{Z}_n</math> עם פעולת הכפל מודולו n האיברים ההפיכים הם בדיוק המספרים הזרים ל n.
**נניח <math>k\in\mathbb{Z}_n</math> אינו זר לn, כלומר <math>gcd(n,k)=a>1</math>.
***לכן <math>n=qa,k=ta</math> לכן <math>qk=tn</math> ולכן <math>qk=0\in\mathbb{Z}_n</math> כלומר k מחלק אפס ואינו הפיך.
**נניח <math>k\in\mathbb{Z}_n</math> זר לn כלומר <math>gcd(n,k)=1</math>.
***לכן קיימים שלמים כך ש <math>an+bk=1</math> לכן <math>b\cdot k \equiv 1 \mod n</math>.
*עבור מספר טבעי <math>1<n</math> קבוצת המספרים הטבעיים הזרים לn וקטנים ממנו מהווה חבורה ביחס לכפל מודולו n, היא נקראית '''חבורת אוילר''' ומסומנת <math>U_n</math>.
**הוכחה ש<math>U_n</math> חבורה:
**סגירות: מכפלת הפיכים היא הפיכה.
**אסוציאטיביות: נובע מהאסוציאטיביות של הכפל.
**איבר נייטרלי: 1.
**הפיכים: ברור מההגדרה.
*<math>\mathbb{Z}_n</math> עם פעולות חיבור וכפל מודולו n הוא שדה אם ורק אם n הינו מספר ראשוני.
**אכן, כל המספרים החיוביים הקטנים מn הפיכים אם"ם כולם זרים לו אם"ם הוא ראשוני.
===פונקצית אוילר, משפט אוילר והמשפט הקטן של פרמה===
*פונקצית אוילר <math>\phi(n)</math> היא מספר המספרים הטבעיים שקטנים או שווים לn וזרים לו.
*'''משפט אוילר''' - יהיו שני מספרים טבעיים '''זרים''' <math>a<n</math>. אזי <math>a^{\phi(n)}\equiv 1</math> מודולו n.
**עבור <math>n>1</math>, מתקיים כי <math>a\in U_n</math> וגם <math>|U_n|=\phi(n)</math>.
**הסדר של איבר בחבורה סופית חייב לחלק את סדר החבורה, נסמן <math>o(a)=k</math> ולכן <math>\phi(n)=t\cdot k</math>.
**לכן <math>a^{\phi(n)} = (a^k)^t=1</math> כאשר הכפל נעשה ב<math>U_n</math>.
*'''המשפט הקטן של פרמה''' - יהי p ראשוני ומספר טבעי <math>a<p</math> אזי <math>a^{p-1}\equiv 1</math> מודולו p.
**זו מסקנה ישירה ממשפט אוילר (אמנם למעשה אוילר הוא הכללה של פרמה), כיוון ש <math>\phi(p)=p-1</math>.
*בפרט, בתנאי המשפט, <math>a^p\equiv a</math> מודולו p.
**למעשה התוצאה תקיפה לכל מספר טבעי <math>a^p\equiv a</math>, מודולו p נכון לכל ראשוני p ולכל טבעי a. **כיוון ש שאם a זר לp מתקיים כי גם השארית <math>r_a</math> זרה ל <math>p</math> ולכן <math>a^{\phi(n)p-1}\equiv rr_a^{\phi(n)p-1} \mod nequiv 1</math>מודולו p.**אם a אינו זר לp אזי הוא חייב להתחלק בראשוני p, וגם השארית ולכן <math>r</math> זרה ל <math>na^p\equiv a \equiv 0</math>מודולו p.
==הרצאה 6 הצפנה סימטרית (מפתח פרטי), הצפנה אסימטרית (מפתח ציבורי), RSA; פרק 7 מ[http://abstract.ups.edu/aata/ הספר]==
*[https://he.wikipedia.org/wiki/%D7%9E%D7%A4%D7%AA%D7%97_%D7%A6%D7%99%D7%91%D7%95%D7%A8%D7%99 הצפנה פומבית] - הצפנה ללא סוד מתואם מראש, באמצעות מפתחות פומביים (שכולם רואים).
*[https://en.wikipedia.org/wiki/Transport_Layer_Security פרקטית] הצדדים מעבירים מפתח סודי באמצעות הצפנה פומבית, ואז עוברים להצפנה סימטרית.
**אורך המידע (בהנחה שהוא אינו מרופד באפסים).
*אליס בוחרת שני ראשוניים גדולים <math>\{p,q\}</math> זה הסוד שלה.
*אליס מחשבת את המכפלה <math>n=p\cdot q</math>
*שימו לב: אמנם <math>4\equiv 3 1 \mod 13</math> אך <math>2^4 \not\equiv 2 \mod 3</math> כלומר לחשב את ההופכי של e מוד n זה אמנם קל, אך לא יעיל לשום דבר...
==הרצאה 7 המשך הצפנה - בדיקת ראשוניות, דיפי הלמן, חתימה, חישוב חזקות;==
*חלק מהותי בשיטות שאנו לומדים הוא מציאת ראשוניים גדולים. כיצד הדבר נעשה? האם יש רשימה גדולה של כל הראשוניים בעולם?
*ידוע שכמות הראשוניים עד המספר <math>n</math> היא בערך <math>\frac{n}{\ln(n)}</math>.
*טענה: אם <math>p</math> ראשוני, ו<math>x\in U_p</math> איבר כך ש <math>x^2=1</math> אזי <math>x=\pm 1</math>
*הוכחה:
**נזכור ש<math>U_p\mathbb{Z}_p</math> הוא '''שדה''' כיוון שמדובר במספר ראשוני, ולכן אין בו ב<math>U_p=\mathbb{Z}/\{0\}</math> מחלקי אפס.
**<math>x^2=1</math> אם"ם <math>(x-1)(x+1)=0</math> אם"ם <math>x=\pm 1</math>
*הגדרה:
**בהנתן מספר n, ונסמן <math>n-1=2^s\cdot r</math> עבור r אי זוגי. אומרים שהמספר <math>1\leq a <n</math> הוא '''עד חזק''' לראשוניות של n אם אחד מהתנאים הבאים מתקיים:
***<math>a^r\equiv 1 \mod n</math>
***<math>a^{2^kr}\equiv n-1 \mod n</math> עבור <math>1\leq k \leq s-1</math>.
*בהנתן מספר שימו לב: <math>p</math> נתאר מבחן '''הסתברותי''' הבודק האם הוא ראשוני**נבחר מספר <math>1<a<p</math>.**אם <math>a,p</math> אינם זרים, אז <math>p</math> אינו ראשוני '''בוודאות''' וסיימנו.**אחרת, לפי משפט פרמה הקטן <math>a^{pn-1}\equiv 1 \mod p</math>.**המספר <math>p-1</math> הוא זוגי (ביננו, אף אחד לא יבדוק האם <math>p=2</math> ראשוני).**נחלק את <math>p-1</math> ב2 שוב ושוב עד שנגיע למספר אי זוגי r ולכן <math>p-1=2^s\cdot r</math>**כעת נביט במספר <math>a^r \mod p</math>, ידוע שאם נעלה אותו בריבוע s פעמים נקבל 1 (אם p ראשוני כמובן).**כלומר אם נעלה אותו בריבוע שוב ושוב נקבל את סדרת המספרים <math>a^r,a^{2r},a^{4r},...,a^{2^s\cdot r}</math> (מוד p כמובן).**אם אחד האיברים בסדרה אינו <math>\pm 1</math> והבא אחריה הוא כן 1, סימן ש<math>p</math> אינו ראשוני '''בוודאות''' וסיימנו.**אם אף אחד מהחזקות אינה 1 סימן ש<math>p</math> אינו ראשוני '''בוודאות''' וסיימנו.**אחרת <math>a</math> הינו '''עד חזק''' לראשוניות של <math>pn</math>.
*אם <math>p</math> ראשוני אזי כל המספרים <math>1<a<p</math> הם עדים חזקים לכך.**הוכחה:***לפי אוילר <math>a^{p-1}\equiv 1 \mod p</math> .***אם נעלה את <math>a^r</math> בריבוע s פעמים נקבל <math>a^{2^s\cdot r}=a^{p-1}\equiv 1 \mod p</math>.***לכן אם <math>a^r\not \equiv 1 \mod p</math>, בשלב כלשהו נעלה מספר שאינו 1 בריבוע ונקבל 1, לכן מספר זה חייב להיות <math>-1</math>.
*אם <math>p</math> אינו ראשוני, ידוע שלכל היותר רבע מבין המספרים <math>a</math> יכולים להיות עדים חזקים.
*לכן הסיכוי שמצאנו עד חזק למרות שהמספר שאנו בודקים אינו ראשוני הוא רבע.
*אם נבחן k מספרים אקראיים שונים, הסיכוי שכולם יהיו עדים חזקים אך המספר אינו ראשוני הוא <math>\frac{1}{4^k}</math> (נמוך מאד).
*למדנו שבעזרת RSA ניתן להעביר פיסת מידע באופן בטוח בערוץ פומבי, ולרוב נרצה להעביר מפתח סודי לצורך הצפנה סימטרית.
*אלגוריתם דיפי-הלמן הוא שיטה לתיאום מפתח סודי בלבד ולא להעברת מידע.
*אליס ובוב מתאמים מספר ראשוני גדול <math>p</math> שאינו סודי כמובן.
*כמו כן הם מתאמים יוצר <math>g</math> של <math>U_p</math> (כלומר <math>U_p=<g></math>), או לפחות איבר מסדר מאד גדול(בהמשך יש הסבר כיצד אפשר לעשות זאת).
*כעת אליס בוחרת מספר אקראי סודי <math>a\leq p-1</math> ושולחת לבוב את <math>g^a \mod p</math>.
*בוב בוחר מספר אקראי סודי <math>b\leq p-1</math> ושולח לאליס את <math>g^b \mod p</math>.
**נבחר את p להיות מספר ראשוני "בטוח", כלומר <math>p=2q+1</math> כאשר <math>q</math> ראשוני.
**כעת ב<math>|U_p|=2q</math> ולכן הסדר של כל איבר ב<math>U_p</math> הוא אחד מבין <math>1,2,q,2q</math>.
**נגריל איבר <math>g\neq \pm 1</math> כך ש(לכן <math>g^2\not\equiv 1 \mod p</math> ) וגם <math>g^q\not\equiv 1 \mod p</math>.
**האיבר שבחרנו הוא יוצר.
*פונקציות גיבוב (hash) - מעבירות קלט בגודל אקראי לקלט באורך קבוע.
*סיפרנו על אליס שייצרה מפתח פומבי <math>(n,e)</math>, ושמרה לעצמה את הערכים הסודיים <math>m,d</math>
*כעת בוב שרוצה לשלוח לה מידע ולהבטיח אליס רוצה להבטיח את זהותו זהותה ואת אמינות המידע, מייצר באופן דומה מפתח פומבי <math>(n',e')</math> ושומר ערכים סודיים <math>m',d'</math>*בוב מעביר היא מעבירה את המידע שלו שלה דרך פונקצית גיבוב ומקבל ומקבלת את הערך המגובב <math>a</math>.*בוב מחשב אליס מחשבת את <math>y=a^{d'} \mod n'</math> ושולח לאליס ושולחת אותו בנוסף למידע.*אפילו בהנתן <math>a</math> לא ניתן לחשב את <math>d'</math> (זו בעיית הלוגריתם הדיסקרטי).*אף אחד אחר לא יכול לחשב את y כיוון ש <math>d'</math> סודי.
*כעת אליס מחשבת בוב שרוצה לוודא את אמינות המידע מחשב את <math>a=y^{e'} \mod n'</math> ומוודאת ומוודא כי המידע שהיא קיבלה שהוא קיבל הוא המידע שבוב התכוון שאליס התכוונה לשלוח עד כדי המקרה הבלתי סביר של התנגשות.*אף אחד אחר לא יכל ליצור את הוכחת אמינות המידע הזו פרט לבובלאליס.
*שימו לב שעל מנת למנוע תקיפת 'אדם באמצע' באמצעות חתימה המפתחות הפומביים צריכים להיות מאומתים על פני ערוץ מאובטח (מקודדים בתוך הדפדפן למשל).
*[http://abstract.ups.edu/aata/section-method-of-repeated-squares.html שיטת הריבועים החוזרים] לחישוב חזקה.
*לדוגמא, אנו מעוניינים לחשב את <math>x^{41} \mod n</math> במעט פעולות
**סה"כ חישבנו את החזקה עם 8 העלאות בריבוע, ושלוש הכפלות, במקום 40 הכפלות.
*תהי חבורה G ותהי תת חבורה N. תת החבורה N נקראת '''נורמלית''' אם לכל <math>a\in G</math> מתקיים כי <math>aN=Na</math>.
*יהי הומומורפיזם בין חבורות <math>\varphif:G\to H</math>. נגדיר את '''הגרעין''' <math>\ker(\varphif)=\{a\in G|\varphif(a)=e_H\}</math>.*הגרעין הוא תת-חבורה נורמלית של <math>G</math>.*הוכחה - נסמן <math>K=\ker(\varphif)</math>*טענה:**ראשית עלינו להוכיח שמדובר בתת-חבורה: אכן <math>e_G\in K</math> ואם לכל <math>a,b\in KG</math> אז מתקיים כי <math>aK=\left\varphi(ab^{-1})=b\varphiin G|f(a)\left(\varphi=f(b)\right)^{-1\}=e_H</math>.*הוכחה:*כעת *בכיוון ראשון, יהי <math>aak\in GaK</math> עלינו להוכיח כי אזי <math>aKf(ak)=Kaf(a)f(k)=f(a)e_H=f(a)</math>. נעשה הכלה בכיוון אחד, הכיוון השני דומה.**בכיוון שני, יהי <math>akb\in aK</math> רוצים למצוא <math>m\in KG</math> כך ש <math>akf(a)=maf(b)</math>. **לכן עלינו לבחור אזי <math>m=akaf(a^{-1}b)=e_H</math>, נותר להוכיח שאכן ולכן <math>ma^{-1}b=k\in K</math>.**אכן ולכן <math>\varphi(m)b=ak\varphi(aka^{-1})=\varphi(a)e_H\left(\varphi(a)\right)^{-1}=e_Hin aK</math>.
*כיוון שהוכחה דומה עובדת מהצד השני, נובע כי <math>aK=Ka</math> ולכן הגרעין הינו תת חבורה נורמלית.
*הוכחה:
**לצורך הנוחות נסמן <math>K=\ker(\varphi)</math> ו<math>M=im(\varphi)</math>.
*כיוון ש <math>\varphi(21)=\varphi(3)</math>, נובע לפי הוכחת משפט האיזומורפיזם הראשון כי <math>21+9\mathbb{Z}=3+9\mathbb{Z}</math>, כלומר אכן מותר לעשות את המודולו בסוף.
*קוד ISBN בעל 10 ספרות, כאשר הספרה האחרונה היא ספרת ביקורת.
*הספרות שייכות לחבורה <math>\mathbb{Z}_{11}</math>, כאשר 9 הספרות הראשונות הן 0-9 והאחרונה יכולה להיות גם X.
*שימו לב שקוד זה מוגבל במספר הספרות, ואכן כשהוסיפו ספרות שינו אותו באופן דומה במידה מסוימת לתעודת הזהות שנלמד בהמשך.
*תעודת זהות בישראל.
*עבור ספרת הביקורת של תעודת הזהות אנו לא מרשים שימוש בספרה X ולכן עובדים ב<math>\mathbb{Z}_{10}</math>.
*ראשית נביט בכפל ב2
**הספרות <math>\{0,1,2,3,4\}</math> נשלחות לספרות <math>\{0,2,4,6,8\}</math> בהתאמה.
**הספרות <math>\{05,16,27,38,49\}</math> נשלחות לספרות <math>\{1,3,5,7,9\}</math> בהתאמה.
**הספרות <math>\{5,6,7,8,9\}</math> כפול 2 שוות ל <math>10+x</math> ונשלחות ל<math>1+x</math>.
**נשים לב כי פעמיים הספרה שקול ל <math>x</math> מודולו 10.
**<math>1\cdot a+3\cdot (a+5)=a+3a+15=1\cdot(a+5)+3\cdot a</math>.
*נניח שספרות תעודת הזהות הן <math>x_9,...,x_1</math>כאשר <math>x_1</math> היא ספרת הביקורת והימנית ביותר.
*לפי החישוב לעיל ספרת הביקורת נבחרה כך ש <math>x_9+f(x_8)+x_7+...+f(x_2)+x_1=0</math>.
*נעביר אגף ונקבל נוסחא לספרת הביקורת.
checksum בפרוטוקולי IP, TCP, UDP.
*דוגמא:*<math>x^7-1=(1+x)(1+x+x^3)(1+x^2+x^3)</math>*לכן הקוד הנוצר על ידי הפולינום <math>g(x)==הרצאה 12 קודים ציקליים; פרק 22 מ[http:1+x+x^3<//abstractmath> עבור וקטורי מידע באורך 4 הוא ציקלי.ups.edu/aata/ הספר]===