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

גרסה מ־21:45, 21 בדצמבר 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$ .