הבדלים בין גרסאות בדף "תקציר תורת המספרים, סמסטר א תשע״ג"
מתוך Math-Wiki
(יצירת דף עם התוכן "בקורס זה <math>\mathbb N=\{0,1,2,\dots\}</math> ו־<math>\mathbb N^+=\{1,2,\dots\}</math>. כמו כן, אלא אם צוין אחרת, <math>A^+:=A\cap\math...") |
|||
שורה 24: | שורה 24: | ||
* <math>U_m:=\{\bar a\in\mathbb Z_m:\ (a,m)=1\}\subset\mathbb Z_m</math>. | * <math>U_m:=\{\bar a\in\mathbb Z_m:\ (a,m)=1\}\subset\mathbb Z_m</math>. | ||
* '''פונקציית אוילר''' היא <math>\varphi:\mathbb N^+\to\mathbb N^+</math> עבורה <math>\varphi(1):=1,\ \varphi(m):=|U_m|</math>. | * '''פונקציית אוילר''' היא <math>\varphi:\mathbb N^+\to\mathbb N^+</math> עבורה <math>\varphi(1):=1,\ \varphi(m):=|U_m|</math>. | ||
− | * | + | * אם <math>(m,n)=1</math> אז <math>\varphi(mn)=\varphi(m)\varphi(n)</math>. |
− | * '''מערכת מלאה מודולו m''' היא קבוצה <math>\{a_i\}_{i=1}^m\subseteq\mathbb Z</math> עבורה <math>\forall a:\ \exists i:\ a\equiv a_i\pmod m</math>. קיים <math>i</math> כנ״ל יחיד לכל <math>a</math>. באופן שקול, המערכת מלאה מודולו <math>m</math> אם <math>\mathbb Z_m=\{\bar a_i\}_{i=1}^m</math>. | + | * '''מערכת מלאה מודולו ''m''''' היא קבוצה <math>\{a_i\}_{i=1}^m\subseteq\mathbb Z</math> עבורה <math>\forall a:\ \exists i:\ a\equiv a_i\pmod m</math>. קיים <math>i</math> כנ״ל יחיד לכל <math>a</math>. באופן שקול, המערכת מלאה מודולו <math>m</math> אם <math>\mathbb Z_m=\{\bar a_i\}_{i=1}^m</math>. |
* אם <math>\{a_i\}_{i=1}^m</math> מלאה מודולו <math>m</math>, <math>(\alpha,m)=1</math> ו־<math>k</math> שלם אזי <math>\{\alpha a_i+k\}_{i=1}^m</math> מלאה מודולו <math>m</math>. | * אם <math>\{a_i\}_{i=1}^m</math> מלאה מודולו <math>m</math>, <math>(\alpha,m)=1</math> ו־<math>k</math> שלם אזי <math>\{\alpha a_i+k\}_{i=1}^m</math> מלאה מודולו <math>m</math>. | ||
− | * '''מערכת מצומצמת מודולו m''' היא קבוצה <math>\{a_i\}_{i=1}^{\varphi(m)}</math> כך ש־<math>\forall\bar a\in U_m:\ \exists i:\ a\equiv a_i\pmod m</math>. | + | * '''מערכת מצומצמת מודולו ''m''''' היא קבוצה <math>\{a_i\}_{i=1}^{\varphi(m)}</math> כך ש־<math>\forall\bar a\in U_m:\ \exists i:\ a\equiv a_i\pmod m</math>. |
* אם <math>\{a_i\}_{i=1}^{\varphi(m)}</math> מצומצמת מודולו <math>m</math> ו־<math>(\alpha,m)=1</math> אז <math>\{\alpha a_i\}_{i=1}^{\varphi(m)}</math> מצומצמת מודולו <math>m</math>. | * אם <math>\{a_i\}_{i=1}^{\varphi(m)}</math> מצומצמת מודולו <math>m</math> ו־<math>(\alpha,m)=1</math> אז <math>\{\alpha a_i\}_{i=1}^{\varphi(m)}</math> מצומצמת מודולו <math>m</math>. | ||
+ | * אם <math>\forall i:\ p_i\in\mathcal P\ \and\ p_i^{l_i}\mid\!\mid m</math> אזי <math>\varphi(m)=m\prod_i\left(1-\frac1{p_i}\right)</math>. בפרט, <math>\varphi\!\left(p^l\right)=p^l-p^{l-1}</math>. | ||
+ | * '''משפט גאוס:''' <math>\sum_{d\mid m}\varphi\!\left(\frac md\right)=m</math>. | ||
+ | * '''משפט אוילר:''' אם <math>(a,m)=1</math> אז <math>a^{\varphi(m)}\equiv1\pmod m</math>. ''משפט פרמה'' הוא מקרה פרטי כאשר <math>m</math> ראשוני. | ||
+ | * '''פתרון משוואות פולינומיאליות מעל {{ltr|ℤ<sub>''m''</sub>}}:''' יהי <math>m>1</math> ונרצה לפתור או לבדוק כמה פתרונות יש ל־<math>f(x)\equiv0\pmod m</math> כאשר <math>f(x)\in\mathbb Z[x]</math>. | ||
+ | :* '''משוואה לינארית:''' <math>ax\equiv b</math>. קיים פתרון אם״ם <math>d:=(a,m)\mid b</math>. אם <math>x_0</math> פתרון פרטי של <math>ax\equiv b\pmod{m/d}</math> אז כל הפתרונות הם <math>x\equiv x_0+k\frac md\pmod m</math> כאשר <math>0\le k\le d-1</math>, ויש <math>d</math> פתרונות. |
גרסה מ־20:46, 22 בדצמבר 2012
בקורס זה ו־. כמו כן, אלא אם צוין אחרת, וכל המשתנים והנעלמים שלמים.
- משפט פיאנו: קיימת קבוצה בודדה שעבורה יש פונקציה המקיימת את אקסיומות פיאנו: חח״ע, , ואם מקיימת אזי .
- מחולק לשלוש קבוצות: יחידות – , ראשוניים – ופריקים – .
- לכל ו־ קיים זוג יחיד של שארית ומנה כך ש־.
- המשפט הבסיסי של האתריתמטיקה: כל מספר ב־ ניתן לפירוק יחיד (עד כדי סדר ההכפלה) של גורמים ראשוניים.
- למת אוקלידס: יהי . אם אז .
- יהיו . נסמן אם .
- נניח ש־ ו/או שונים מ־0. אזי קיים יחיד (הנקרא מחלק משותף מקסימלי של ומסומן ) עבורו ואם כך ש־ אזי .
- אם אזי .
- .
- .
- אם זרים ו־ אזי .
- אם אזי .
- אלגוריתם אוקלידס: נניח ונרצה לחשב כאשר . אם שארית החלוקה של ב־ אזי . נמשיך כך עד שנקבל . ניתן להעזר באלגוריתם גם כדי לפתור את : נסמן ולכן בתהליך החישוב של עם האלגוריתם נקבל כאשר . לפיכך:
- משוואה דיאופנטית ב־2 משתנים: נרצה לפתור כאשר משתנים והשאר קבועים. נחלק למקרים:
- : אין פתרון.
- : ניתן לפתור ע״י אלגוריתם אוקלידס (כמפורט בהמשך הסעיף). הפתרון הכללי הוא לכל .
- : נחלק את אגפי המשוואה ב־ ונקבל משוואה חדשה מהמקרה הקודם.
- אם בפרט אז ניתן לפתור גם באמצעות אלגוריתם אוקלידס.
- נאמר ש־ חופפים מודולו (ונסמן ) אם . מגדיר יחס שקילות כאשר מחלקת השקילות של ו־ קבוצת מחלקות השקילות.
- אם ו־ אז .
- יהי . אם״ם הפיך. ניתן למצוא את ההופכי ל־ ע״י פתירת , ואז .
- .
- פונקציית אוילר היא עבורה .
- אם אז .
- מערכת מלאה מודולו m היא קבוצה עבורה . קיים כנ״ל יחיד לכל . באופן שקול, המערכת מלאה מודולו אם .
- אם מלאה מודולו , ו־ שלם אזי מלאה מודולו .
- מערכת מצומצמת מודולו m היא קבוצה כך ש־.
- אם מצומצמת מודולו ו־ אז מצומצמת מודולו .
- אם אזי . בפרט, .
- משפט גאוס: .
- משפט אוילר: אם אז . משפט פרמה הוא מקרה פרטי כאשר ראשוני.
- פתרון משוואות פולינומיאליות מעל ℤm: יהי ונרצה לפתור או לבדוק כמה פתרונות יש ל־ כאשר .
- משוואה לינארית: . קיים פתרון אם״ם . אם פתרון פרטי של אז כל הפתרונות הם כאשר , ויש פתרונות.