הבדלים בין גרסאות בדף "תקציר תורת המספרים, סמסטר א תשע״ג"

גרסה מ־20:46, 22 בדצמבר 2012

בקורס זה $\mathbb N=\{0,1,2,\dots\}$ ו־ $\mathbb N^+=\{1,2,\dots\}$ . כמו כן, אלא אם צוין אחרת, $A^+:=A\cap\mathbb N^+$ וכל המשתנים והנעלמים שלמים.

משפט פיאנו: קיימת קבוצה בודדה $\mathbb N$ שעבורה יש פונקציה $S:\mathbb N\to\mathbb N$ המקיימת את אקסיומות פיאנו: $S$ חח״ע, $0\not\in\mbox{Im}(S)$ , $0\in\mathbb N$ ואם $K\subseteq\mathbb N$ מקיימת $0\in K\ \and\ (x\in K\iff S(x)\in K)$ אזי $K=\mathbb N$ .
$\mathbb Z\setminus\{0\}$ מחולק לשלוש קבוצות: יחידות – $U:=\{\pm1\}$ , ראשוניים – $\mathcal P:=\{p\in\mathbb Z\setminus U:\ \forall ab=p:\ a\in U\ \or\ b\in U\}$ ופריקים – $\mathbb Z\setminus\{0\}\setminus U\setminus\mathcal P$ .
לכל $a\in\mathbb N^+$ ו־ $b$ קיים זוג יחיד של שארית $r$ ומנה $q$ כך ש־ $b=qa+r,\ 0\le r<a$ .
המשפט הבסיסי של האתריתמטיקה: כל מספר ב־ $\mathbb Z\setminus\{0,\pm1\}$ ניתן לפירוק יחיד (עד כדי סדר ההכפלה) של גורמים ראשוניים.
למת אוקלידס: יהי $p\in\mathcal P$ . אם $p\mid ab$ אז $p\mid a\ \or\ p\mid b$ .
יהיו $p\in\mathcal P^+,\ a,m\in\mathbb N^+$ . נסמן $p^m\mid\!\mid a$ אם $p^m\mid a\ \and\ p^{m+1}\nmid a$ .
נניח ש־ $a$ ו/או $b$ שונים מ־0. אזי קיים $d\in\mathbb N^+$ יחיד (הנקרא מחלק משותף מקסימלי של $a,b$ ומסומן $\gcd(a,b)=(a,b)$ ) עבורו $d\mid a,b$ ואם $d'\in\mathbb Z$ כך ש־ $d'\mid a,b$ אזי $d'\mid d$ .
אם $a\mid b,c$ אזי $\forall x,y\in\mathbb Z:\ a\mid xb+yc$ .
$(a,b)=\min\{xa+yb:\ x,y\in\mathbb Z\}^+$ .
$a\mathbb Z+b\mathbb Z=(a,b)\mathbb Z$ .
אם $a,b$ זרים ו־ $a\mid bc$ אזי $a\mid c$ .
אם $\forall i:\ p_i\in\mathcal P\ \and\ k_i,m_i\in\mathbb N$ אזי $\left(\prod_i p_i^{k_i},\prod_i p_i^{m_i}\right)=\prod_i p_i^{\min\{k_i,m_i\}}$ .
אלגוריתם אוקלידס: נניח $b\ne0$ ונרצה לחשב $(a,b)$ כאשר $a>b$ . אם $r$ שארית החלוקה של $a$ ב־ $b$ אזי $(a,b)=(b,r)$ . נמשיך כך עד שנקבל $(x,0)=x$ . ניתן להעזר באלגוריתם גם כדי לפתור את $ax+by=(a,b)$ : נסמן $r_{-1}=a, r_0=b$ ולכן בתהליך החישוב של $(a,b)$ עם האלגוריתם נקבל $\forall0\le i\le k:\ r_{i-1}=r_iq_{i+1}+r_{i+1}$ כאשר $r_{k+1}=(a,b)$ . לפיכך:
$\begin{align}r_{k+1}&=r_{k-1}-r_kq_{k+1}\\&=r_{k-1}-(r_{k-2}-r_{k-1}q_k)q_{k+1}\\&=r_{k-1}(1+q_kq_{k+1})-r_{k-2}q_{k+1}\\&=\dots\\&=r_0y-r_{-1}(-x)\\&=ax+by\end{align}$
משוואה דיאופנטית ב־2 משתנים: נרצה לפתור $ax+by=c$ כאשר $x,y$ משתנים והשאר קבועים. נחלק למקרים:

$0\ne(a,b)\nmid c$ : אין פתרון.
$(a,b)=1$ : ניתן לפתור $ax_0+by_0=1$ ע״י אלגוריתם אוקלידס (כמפורט בהמשך הסעיף). הפתרון הכללי הוא $x=cx_0+bk, y=cy_0-ak$ לכל $k$ .
$1\ne(a,b)\mid c$ : נחלק את אגפי המשוואה ב־ $(a,b)$ ונקבל משוואה חדשה מהמקרה הקודם.

אם בפרט $(a,b)=c$ אז ניתן לפתור גם באמצעות אלגוריתם אוקלידס.

נאמר ש־ $a,b$ חופפים מודולו $m>1$ (ונסמן $a\equiv b\pmod m$ ) אם $m\mid a-b$ . $\equiv$ מגדיר יחס שקילות כאשר $\bar a=[a]=a+m\mathbb Z$ מחלקת השקילות של $a$ ו־ $\mathbb Z_m$ קבוצת מחלקות השקילות.
אם $m>1,\ k\ne0$ ו־ $ka\equiv kb\pmod m$ אז $a\equiv b\pmod{m/(k,m)}$ .
יהי $\bar a\in\mathbb Z_m$ . $(a,m)=1$ אם״ם $\bar a$ הפיך. ניתן למצוא את ההופכי ל־ $\bar a$ ע״י פתירת $ax+my=1$ , ואז $\bar a^{-1}=\bar x$ .
$U_m:=\{\bar a\in\mathbb Z_m:\ (a,m)=1\}\subset\mathbb Z_m$ .
פונקציית אוילר היא $\varphi:\mathbb N^+\to\mathbb N^+$ עבורה $\varphi(1):=1,\ \varphi(m):=|U_m|$ .
אם $(m,n)=1$ אז $\varphi(mn)=\varphi(m)\varphi(n)$ .
מערכת מלאה מודולו m היא קבוצה $\{a_i\}_{i=1}^m\subseteq\mathbb Z$ עבורה $\forall a:\ \exists i:\ a\equiv a_i\pmod m$ . קיים $i$ כנ״ל יחיד לכל $a$ . באופן שקול, המערכת מלאה מודולו $m$ אם $\mathbb Z_m=\{\bar a_i\}_{i=1}^m$ .
אם $\{a_i\}_{i=1}^m$ מלאה מודולו $m$ , $(\alpha,m)=1$ ו־ $k$ שלם אזי $\{\alpha a_i+k\}_{i=1}^m$ מלאה מודולו $m$ .
מערכת מצומצמת מודולו m היא קבוצה $\{a_i\}_{i=1}^{\varphi(m)}$ כך ש־ $\forall\bar a\in U_m:\ \exists i:\ a\equiv a_i\pmod m$ .
אם $\{a_i\}_{i=1}^{\varphi(m)}$ מצומצמת מודולו $m$ ו־ $(\alpha,m)=1$ אז $\{\alpha a_i\}_{i=1}^{\varphi(m)}$ מצומצמת מודולו $m$ .
אם $\forall i:\ p_i\in\mathcal P\ \and\ p_i^{l_i}\mid\!\mid m$ אזי $\varphi(m)=m\prod_i\left(1-\frac1{p_i}\right)$ . בפרט, $\varphi\!\left(p^l\right)=p^l-p^{l-1}$ .
משפט גאוס: $\sum_{d\mid m}\varphi\!\left(\frac md\right)=m$ .
משפט אוילר: אם $(a,m)=1$ אז $a^{\varphi(m)}\equiv1\pmod m$ . משפט פרמה הוא מקרה פרטי כאשר $m$ ראשוני.
פתרון משוואות פולינומיאליות מעל ℤ_m: יהי $m>1$ ונרצה לפתור או לבדוק כמה פתרונות יש ל־ $f(x)\equiv0\pmod m$ כאשר $f(x)\in\mathbb Z[x]$ .

משוואה לינארית: $ax\equiv b$ . קיים פתרון אם״ם $d:=(a,m)\mid b$ . אם $x_0$ פתרון פרטי של $ax\equiv b\pmod{m/d}$ אז כל הפתרונות הם $x\equiv x_0+k\frac md\pmod m$ כאשר $0\le k\le d-1$ , ויש $d$ פתרונות.

@@ שורה 24: / שורה 24: @@
 * <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>(m,n)=1</math> אז <math>\varphi(mn)=\varphi(m)\varphi(n)</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>.
-* '''מערכת מצומצמת מודולו 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>\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

תפריט הניווט

כלים אישיים

גרסאות שפה

מרחבי שם

חיפוש

עוד

צפיות

ניווט

כלים