הבדלים בין גרסאות בדף "תקציר תורת המספרים, סמסטר א תשע״ג"
מתוך 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: יהי
ונרצה לפתור או לבדוק כמה פתרונות יש ל־
כאשר
.
- משוואה לינארית:
. קיים פתרון אם״ם
. אם
פתרון פרטי של
אז כל הפתרונות הם
כאשר
, ויש
פתרונות.
- משוואה לינארית: