שינויים
/* דיפי-הלמן */
[[קטגוריה:מערכי לימוד]]
=ספר הקורס=
ההרצאות מבוססות באופן כללי על הספר [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 הקדמה; הסבר על קידוד והצפנה, מבוא למבנים אלגבריים ==
==הרצאה 2 חבורות ותת חבורות; פרקים 3,4 מ[http://abstract.ups.edu/aata/ הספר] ==
===חבורות===
*חבורה היא קבוצה G עם פעולה המקיימת:
**סגירות
**אסוציאטיביות
**איבר נייטרלי
**לכל איבר יש איבר הופכי
*תזכורת לגבי חבורותחבורה המקיימת את חוק החילוף נקראת חבורה אבלית, קומוטטיבית או חילופית *תכונת הצמצום: תהי חבורה 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> בהתאם לסימון פעולת החבורה.
*תהי G חבורה, לכל <math>a\in G,n\in \mathbb{N}</math> נגדיר:
**<math>a^0=e_G</math>.
**<math>a^{-n}=(a^{-1})^n</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/ הספר] ==
<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>
==הרצאה 5 חבורת אוילר, משפטי אוילר ופרמה; פרק 6 מ[http://abstract.ups.edu/aata/ הספר]==
===חלוקה עם שארית===
*זוג מספרים שלמים <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%A6%D7%95%D7%A4%D7%9F_%D7%A1%D7%99%D7%9E%D7%98%D7%A8%D7%99 הצפנה סימטרית] - הצפנה בה לשני הצדדים יש סוד משותף שהעבירו מראש בערוץ שאינו פומבי (משאית ברינקס למשל, לנסוע לחנות לאסוף כרטיס sim).
*[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 פרקטית] הצדדים מעבירים מפתח סודי באמצעות הצפנה פומבית, ואז עוברים להצפנה סימטרית.
===RSA===
מומלץ לקרוא ישירות את המאמר פורץ הדרך בו הוצגה השיטה:
[https://people.cs.umass.edu/~emery/classes/cmpsci691st/readings/Sec/Rsapaper.pdf Rivest, Ronald L., Adi Shamir, and Leonard Adleman. "A method for obtaining digital signatures and public-key cryptosystems."]
*אליס בוחרת שני ראשוניים גדולים <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>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> יכולים להיות עדים חזקים.
*לכן הסיכוי שמצאנו עד חזק למרות שהמספר שאנו בודקים אינו ראשוני הוא רבע.
===דיפי-הלמן===
מומלץ לקרוא ישירות את המאמר פורץ הדרך בו הוצגה השיטה:
[http://ee.stanford.edu/%7Ehellman/publications/24.pdf Diffie, Whitfield, and Martin E. Hellman. "New directions in cryptography."]
*למדנו שבעזרת 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>.
**האיבר שבחרנו הוא יוצר.
*סיפרנו על אליס שייצרה מפתח פומבי <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> ומוודאת ומוודא כי המידע שהיא קיבלה שהוא קיבל הוא המידע שבוב התכוון שאליס התכוונה לשלוח עד כדי המקרה הבלתי סביר של התנגשות.*אף אחד אחר לא יכל ליצור את הוכחת אמינות המידע הזו פרט לבובלאליס.
**<math>x^{41}=\left(\left(\left(\left(x^2\right)^2\right)^2\right)^2\right)^2\cdot \left(\left(x^2\right)^2\right)^2 \cdot x</math>
**סה"כ חישבנו את החזקה עם 8 העלאות בריבוע, ושלוש הכפלות, במקום 40 הכפלות.
==הרצאה 8 תת חבורות נורמליות, חבורות מנה, גרעין; פרקים 10,11 מ[http://abstract.ups.edu/aata/ הספר]==
*יהי הומומורפיזם בין חבורות <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> ולכן הגרעין הינו תת חבורה נורמלית.
==הרצאה 9 משפט האיזומורפיזם, מבוא לקידוד; פרק 11 מ[http://abstract.ups.edu/aata/ הספר]==
*'''משפט האיזומורפיזם הראשון'''. יהי <math>\varphi:G\to H</math> איזומורפיזם הומומורפיזם בין חבורות. אזי <math>G/\ker(\varphi)\cong im(\varphi) </math>
*הוכחה:
**לצורך הנוחות נסמן <math>K=\ker(\varphi)</math> ו<math>M=im(\varphi)</math>.
**<math>a_ix_i+a_jx_j-a_ix_j-a_jx_i=(a_i-a_j)(x_i-x_j)\neq 0</math>.
*שימו לב שקוד זה מוגבל במספר הספרות, ואכן כשהוסיפו ספרות שינו אותו באופן דומה במידה מסוימת לתעודת הזהות שנלמד בהמשך.
==הרצאה 10 קידוד; פרק 8 מ[http://abstract.ups.edu/aata/ הספר]==
**אם <math>\deg(f)<\deg(g)</math> אזי <math>f=0\cdot g + f</math>.
**אם <math>\deg(f)\geq\deg(g)</math> נוכיח באינדוקציה על הדרגה של <math>f</math>.
**נסמן <math>f(x)=a_nx^n+...+a_0</math>, <math>g(x)=b_mx_mb_mx^m+...+b_0</math> כאשר נתון <math>n\geq m</math>.
**הפולינום <math>f(x)-\frac{a_n}{b_m}x^{n-m}g(x)</math> הוא מדרגה קטנה ממש מ<math>n</math> ולכן מקיים את הטענה לפי הנחת האינדוקציה.
**לכן <math>f(x)-\frac{a_n}{b_m}x^{n-m}g(x)=q(x)g(x)+r(x)</math>.
**נציב <math>a</math> ונקבל <math>f(a)=r</math>.
**לכן <math>f(x)=q(x)(x-a)</math> אם ורק אם <math>f(a)=0</math>.
*נקבע פולינום <math>g(x)\in\mathbb{Z}_2[x]</math> כלשהו מדרגה nm.*עבור מידע <math>f(x)</math> נבצע חלוקה עם שארית של <math>x^m\cdot f(x)</math> ב<math>g(x)</math>*<math>x^m\cdot f(x^n ) =q(x)g(x)+r(x)</math>.*המילה שנשלח היא <math>f(x)^m\cdot f(x^n ) + r(x)</math> (שימו לב כי <math>r(x)=-r(x)</math>).
*המילה תקינה אם ורק אם היא מתחלקת ב<math>g(x)</math>.
*זהו קוד לינארי:
**אם <math>f(x),h(x)</math> מתאימים לוקטורי מידע, <math>f(x)=q_1(x)g(x)+r_1(x)</math> ו<math>h(x)=q_2(x)g(x)+r_2(x)</math> אז השארית של <math>f(x)+h(x)</math> היא <math>r_1(x)+r_2(x)</math>.
*קוד זה מוסיף n m ביטים של יתירות למידע.
**נקודד מידע:
***נניח כי המידע שלנו הוא <math>1010</math> כלומר הפולינום <math>f(x)=x^3+x</math>.
***לכן עלינו לחלק את הפולינום <math>f(x)^3\cdot f(x^3) =x^6+x^4</math> בפולינום <math>g(x)=x^3+x+1</math>.
***לאחר אלגוריתם חלוקה עם שארית נקבל <math>x^6+x^4=(x^3+1)(x^3+x+1)+x+1</math>.
***לכן סה"כ המידע שנשלח הוא <math>f(x)^3\cdot f(x^3 ) + r(x)=x^6+x^4+x+1</math> שזה בעצם <math>1010011</math>.
**נבדוק תקינות מידע:
***האם המידע <math>1101101</math> תקין?
***זה בעצם הפולינום <math>x^6+x^5+x^3+x^2+1</math>, זה קוד תקין אם"ם הוא מתחלק ב<math>g(x)</math>.
***נבצע חלוקה עם שארית ונקבל שארית <math>x^2+x+1</math>, לכן הקוד אינו תקין.
==הרצאה 13 קודים ציקליים; פרק 22 מ[http://abstract.ups.edu/aata/ הספר]==
===קידוד פולינומי ציקלי===*עבור הקידוד הציקלי נקבע את הפרמטרים הבאים:*נביט ב<math>R</math> חוג הפולינומים *יהי k אורך המידע, כלומר נקודד פולינומים עד דרגה <math>nk-1</math>בלבד.**יהי g פולינום מדרגה m, עם מקדמים מלפי נקודד קידוד פולינומי.**נסמן את אורך המילה המקודדת ב<math>\mathbb{Z}_2n=k+m</math>, יחד עם פעולת החיבור הרגילה, ופעולת הכפל מודולו הפולינום .**מילה היא חוקית אם ורק אם היא מהצורה <math>h(x)g(x^n-1)</math>.*נשים לב כי מתקיים כאשר <math>x\cdotdeg(h(a_{n-1}x^{n-1}+...+a_1x+a_0)=a_{n-2}x^{n-1}+...+a_1x^2+a_0x+a_{n-1})<k</math>.
*קוד נקרא ציקלי אם לכל מילה חוקית <math>(a_{n-1}\ a_{n-2}\ \cdots\ a_1\ a_0)</math> גם המילה ההזזה הציקלית <math>(a_{n-2}\ a_{n-3}\ \cdots\ a_0\ a_{n-1})</math> היא מילה חוקית.
*נקבע פולינום נתאר את ההזה הציקלית באמצעות פעולה אלגברית.**יהי <math>gf(x)=a_{n-1}x^{n-1}+...+a_0</math> בעל דרגה **אזי <math>x\deg(gcdot f(x))=\equiv a_{n-2}x^{n-1}+...+a_0x+a_{n-1} \mod x^n-k>1</math>.*נקודד את כל פולינומי המידע מדרגה שקטנה או שווה *כלומר ההזזה הציקלית של <math>kf(x)</math> היא השארית של <math>x\cdot f(x)</math> בחלוקה ב<math>x^n-1</math> בקידוד פולינומי.*שימו לב*הוכחה: כיוון ש***אכן <math>x\deg (cdot f(x)\cdot = a_{n-1}x^n+...+a_0x=a_{n-k1}(x^n-1)\leq + a_{n-1} + a_{n-2}x^{n-1}+...+a_0x</math> החלוקה בשארית כוללת אך ורק פולינומים מ<math>R</math>.
*טענהבמילים פשוטות: הפולינום <math>g(x)</math> מחלק את <math>x^n-1</math> אם ורק אם הקוד לעיל הינו ציקלי.*הוכחה:*בכיוון ראשון, נניח כי הקוד הינו ציקלי:**ראשית, נוכיח כי קבוצת המילים החוקיות <math>I</math> היא אידיאל של <math>R</math>.***תהי יהי <math>f(x)\in I</math> מילה חוקית. כיוון שהקוד ציקלי גם <math>x\cdot f(x)\in I</math>.***באופן דומה, לכל <math>k</math> מתקיים כי <math>x^k\cdot f(x)\in I</math>.***כיוון שהקוד לינארי, גם סכום של מילים חוקיות הוא מילה חוקית.***ביחד, <math>=a_{n-1}x^{n-1}f(x)+...+a_1xf(x)+a_0f(x)a_0</math> הינה מילה חוקית.***לכן לכל פולינום אם <math>h(x)\in Ra_n=0</math> מתקיים אזי ההזזה הציקלית היא <math>h(x)\cdot f(x)\in I</math>, כלומר אוסף המילים החוקיות הינו אידיאל.**נוכיח כי אם <math>Ia_n=\{h(x)g(x)|h(x)\in R\}</math> (שימו לב שמדובר בכפל מודולו <math>x^n-1</math>).***ידוע שכל מילה חוקית אזי ההזה הציקלית היא מהצורה <math>x\cdot f(x)x^{n-k}+r(x)=q(x)g(x)</math>.***מצד שני, כיוון ש<math>I</math> אידיאל לכל <math>h(x)\in R</math> מתקיים כי <math>h(x)g(x)\in I</math>.**כעת נבצע חילוק בשארית (בחוג הפולינומים הרגיל) <math>x^n-1=q(x)g(x)+r(x)</math>.**<math>\deg(g(x))>1</math> ולכן <math>\deg(q(x))<n</math> ולכן <math>q(x)\in R</math>.**לכן ב<math>R</math> מתקיים כי <math>q(x)g(x)=r(x)</math> ולכן <math>r(x)\in I</math>.**כלומר קיבלנו מילה חוקית <math>\deg(r(xמכבים את הביט האחרון, ומוסיפים ביט ראשון))<\deg(g(x))</math> ולכן <math>r(x)=0</math>.
*משפט: הפולינום <math>g(x)</math> מחלק את <math>x^n+1</math> אם ורק אם הקוד הפולינומי הינו ציקלי.*שימו לב: n הוא אורך המילה המקודדת, שכולל הן את המידע והן את היתירות.**הוכחה:**בכיוון השניראשון, נניח כי הקוד הוא ציקלי:***<math>x^n{k-1=t(x)}g(x)</math> ונוכיח כי מדובר בקוד ציקלי.היא מילה חוקית**נביט במילה חוקית *כיוון שהקוד ציקלי, גם ההזזה הציקלית <math>f(x)\cdot x^{n-k-1}g(x)+rx^n+1</math> חוקית***כלומר <math>x^k g(x)+x^n+1=qh(x)g(x)</math>, עלינו להוכיח כי ***לכן <math>xqx^n+1=(h(x)+x^k)g(x)\in I</math>, כפי שרצינו.**בכיוון שני, נניח כי <math>\deg (qx^n+1=t(x)g(x))<n</math> ולכן ***נשים לב כי <math>\deg(xqt(x))\leq =k</math>.**נבצע חלוקה עם שארית *תהי מילה חוקית <math>xqh(x)g(x)=u</math>***אם <math>deg(xh\cdot g)(x^<n-1)+v</math> אז ההזזה הציקלית היא <math>xh(x)=ug(x)t</math> והיא מילה חוקית כי <math>deg(x)gxh(x)+v(x)<k</math>.***אחרת, נניח כי <math>\deg(u(xh\cdot g)t=n</math> ולכן ההזזה הציקלית היא <math>xh(x))\leq \deg (xqg(x))\leq k+x^n+1</math>.**כעת *כלומר ההזזה הציקלית היא <math>vxh(x)=xqg(x)+t(x)g(x)-u=(xh(x)+t(x))\cdot g(x)=</math>***כיוון ש <math>deg(xqxh(x)-u(x)=deg(t(x))g(x)=k</math> בנובע כי <math>Rdeg(xh(x)+t(x))<k</math>.**כיוון ש *לכן <math>\deg(xq(x)-uxh(x)+t(x))\leq kcdot g(x)</math> מדובר במילה מילה חוקית, כפי שרצינו.
*טענהמשפט: קוד פולינומי ציקלי עם פולינום <math>g(x)</math> מדרגה <math>m</math> מסוגל לזהות כל כמות של שגיאות, בתנאי שכולן נמצאות בתוך טווח של <math>m</math> ביטים.
*הוכחה:
**נניח שקרו טעויות בתוך טווח של <math>m</math> ביטים.
**אם המילה החדשה חוקית, גם כל הזזה ציקלית שלה היא חוקית.
**נזיז את <math>m</math> הביטים כך שיהיה שיהיו בקצה הימני במקום של היתירות.
**כיוון שהיתירות היא יחידה, בוודאות המילה אינה חוקית, סתירה.
*פרוטוקול Ethernet משתמש בתיקון שגיאות ציקלי הנקרא CRC32, ובפרט בפולינום:
*<math>g(x)=x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1</math>.*הפולינום <math>g(x)</math> מחלק את <math>x^{2^{32}-1}-1</math>, כלומר הוא מתאים לקידוד של עד למעלה מ4 מיליארד ביטים של מידע.
