שינויים
יצירת דף עם התוכן "בקורס זה <math>\mathbb N=\{0,1,2,\dots\}</math> ו־<math>\mathbb N^+=\{1,2,\dots\}</math>. כמו כן, אלא אם צוין אחרת, <math>A^+:=A\cap\math..."
בקורס זה <math>\mathbb N=\{0,1,2,\dots\}</math> ו־<math>\mathbb N^+=\{1,2,\dots\}</math>. כמו כן, אלא אם צוין אחרת, <math>A^+:=A\cap\mathbb N^+</math> וכל המשתנים והנעלמים שלמים.
* '''משפט פיאנו:''' קיימת קבוצה בודדה <math>\mathbb N</math> שעבורה יש פונקציה <math>S:\mathbb N\to\mathbb N</math> המקיימת את אקסיומות פיאנו: <math>S</math> חח״ע, <math>0\not\in\mbox{Im}(S)</math>, <math>0\in\mathbb N</math> ואם <math>K\subseteq\mathbb N</math> מקיימת <math>0\in K\ \and\ (x\in K\iff S(x)\in K)</math> אזי <math>K=\mathbb N</math>.
* <math>\mathbb Z\setminus\{0\}</math> מחולק לשלוש קבוצות: יחידות – <math>U:=\{\pm1\}</math>, ראשוניים – <math>\mathcal P:=\{p\in\mathbb Z\setminus U:\ \forall ab=p:\ a\in U\ \or\ b\in U\}</math> ופריקים – <math>\mathbb Z\setminus\{0\}\setminus U\setminus\mathcal P</math>.
* לכל <math>a\in\mathbb N^+</math> ו־<math>b</math> קיים זוג יחיד של שארית <math>r</math> ומנה <math>q</math> כך ש־<math>b=qa+r,\ 0\le r<a</math>.
* '''המשפט הבסיסי של האתריתמטיקה:''' כל מספר ב־<math>\mathbb Z\setminus\{0,\pm1\}</math> ניתן לפירוק יחיד (עד כדי סדר ההכפלה) של גורמים ראשוניים.
* '''למת אוקלידס:''' יהי <math>p\in\mathcal P</math>. אם <math>p\mid ab</math> אז <math>p\mid a\ \or\ p\mid b</math>.
* יהיו <math>p\in\mathcal P^+,\ a,m\in\mathbb N^+</math>. נסמן <math>p^m\mid\!\mid a</math> אם <math>p^m\mid a\ \and\ p^{m+1}\nmid a</math>.
* נניח ש־<math>a</math> ו/או <math>b</math> שונים מ־0. אזי קיים <math>d\in\mathbb N^+</math> יחיד (הנקרא מחלק משותף מקסימלי של <math>a,b</math> ומסומן <math>\gcd(a,b)=(a,b)</math>) עבורו <math>d\mid a,b</math> ואם <math>d'\in\mathbb Z</math> כך ש־<math>d'\mid a,b</math> אזי <math>d'\mid d</math>.
* אם <math>a\mid b,c</math> אזי <math>\forall x,y\in\mathbb Z:\ a\mid xb+yc</math>.
* <math>(a,b)=\min\{xa+yb:\ x,y\in\mathbb Z\}^+</math>.
* <math>a\mathbb Z+b\mathbb Z=(a,b)\mathbb Z</math>.
* אם <math>a,b</math> זרים ו־<math>a\mid bc</math> אזי <math>a\mid c</math>.
* אם <math>\forall i:\ p_i\in\mathcal P\ \and\ k_i,m_i\in\mathbb N</math> אזי <math>\left(\prod_i p_i^{k_i},\prod_i p_i^{m_i}\right)=\prod_i p_i^{\min\{k_i,m_i\}}</math>.
* '''אלגוריתם אוקלידס:''' נניח <math>b\ne0</math> ונרצה לחשב <math>(a,b)</math> כאשר <math>a>b</math>. אם <math>r</math> שארית החלוקה של <math>a</math> ב־<math>b</math> אזי <math>(a,b)=(b,r)</math>. נמשיך כך עד שנקבל <math>(x,0)=x</math>. ניתן להעזר באלגוריתם גם כדי לפתור את <math>ax+by=(a,b)</math>: נסמן <math>r_{-1}=a, r_0=b</math> ולכן בתהליך החישוב של <math>(a,b)</math> עם האלגוריתם נקבל <math>\forall0\le i\le k:\ r_{i-1}=r_iq_{i+1}+r_{i+1}</math> כאשר <math>r_{k+1}=(a,b)</math>. לפיכך:{{left|<math>\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}</math>}}
* '''משוואה דיאופנטית ב־2 משתנים:''' נרצה לפתור <math>ax+by=c</math> כאשר <math>x,y</math> משתנים והשאר קבועים. נחלק למקרים:
:* <math>0\ne(a,b)\nmid c</math>: אין פתרון.
:* <math>(a,b)=1</math>: ניתן לפתור <math>ax_0+by_0=1</math> ע״י אלגוריתם אוקלידס (כמפורט בהמשך הסעיף). הפתרון הכללי הוא <math>x=cx_0+bk, y=cy_0-ak</math> לכל <math>k</math>.
:* <math>1\ne(a,b)\mid c</math>: נחלק את אגפי המשוואה ב־<math>(a,b)</math> ונקבל משוואה חדשה מהמקרה הקודם.
::* אם בפרט <math>(a,b)=c</math> אז ניתן לפתור גם באמצעות אלגוריתם אוקלידס.
* נאמר ש־<math>a,b</math> חופפים מודולו <math>m>1</math> (ונסמן <math>a\equiv b\pmod m</math>) אם <math>m\mid a-b</math>. <math>\equiv</math> מגדיר יחס שקילות כאשר <math>\bar a=[a]=a+m\mathbb Z</math> מחלקת השקילות של <math>a</math> ו־<math>\mathbb Z_m</math> קבוצת מחלקות השקילות.
* אם <math>m>1,\ k\ne0</math> ו־<math>ka\equiv kb\pmod m</math> אז <math>a\equiv b\pmod{m/(k,m)}</math>.
* יהי <math>\bar a\in\mathbb Z_m</math>. <math>(a,m)=1</math> אם״ם <math>\bar a</math> הפיך. ניתן למצוא את ההופכי ל־<math>\bar a</math> ע״י פתירת <math>ax+my=1</math>, ואז <math>\bar a^{-1}=\bar x</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>(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>.
* אם <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>.
* אם <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>\mathbb N</math> שעבורה יש פונקציה <math>S:\mathbb N\to\mathbb N</math> המקיימת את אקסיומות פיאנו: <math>S</math> חח״ע, <math>0\not\in\mbox{Im}(S)</math>, <math>0\in\mathbb N</math> ואם <math>K\subseteq\mathbb N</math> מקיימת <math>0\in K\ \and\ (x\in K\iff S(x)\in K)</math> אזי <math>K=\mathbb N</math>.
* <math>\mathbb Z\setminus\{0\}</math> מחולק לשלוש קבוצות: יחידות – <math>U:=\{\pm1\}</math>, ראשוניים – <math>\mathcal P:=\{p\in\mathbb Z\setminus U:\ \forall ab=p:\ a\in U\ \or\ b\in U\}</math> ופריקים – <math>\mathbb Z\setminus\{0\}\setminus U\setminus\mathcal P</math>.
* לכל <math>a\in\mathbb N^+</math> ו־<math>b</math> קיים זוג יחיד של שארית <math>r</math> ומנה <math>q</math> כך ש־<math>b=qa+r,\ 0\le r<a</math>.
* '''המשפט הבסיסי של האתריתמטיקה:''' כל מספר ב־<math>\mathbb Z\setminus\{0,\pm1\}</math> ניתן לפירוק יחיד (עד כדי סדר ההכפלה) של גורמים ראשוניים.
* '''למת אוקלידס:''' יהי <math>p\in\mathcal P</math>. אם <math>p\mid ab</math> אז <math>p\mid a\ \or\ p\mid b</math>.
* יהיו <math>p\in\mathcal P^+,\ a,m\in\mathbb N^+</math>. נסמן <math>p^m\mid\!\mid a</math> אם <math>p^m\mid a\ \and\ p^{m+1}\nmid a</math>.
* נניח ש־<math>a</math> ו/או <math>b</math> שונים מ־0. אזי קיים <math>d\in\mathbb N^+</math> יחיד (הנקרא מחלק משותף מקסימלי של <math>a,b</math> ומסומן <math>\gcd(a,b)=(a,b)</math>) עבורו <math>d\mid a,b</math> ואם <math>d'\in\mathbb Z</math> כך ש־<math>d'\mid a,b</math> אזי <math>d'\mid d</math>.
* אם <math>a\mid b,c</math> אזי <math>\forall x,y\in\mathbb Z:\ a\mid xb+yc</math>.
* <math>(a,b)=\min\{xa+yb:\ x,y\in\mathbb Z\}^+</math>.
* <math>a\mathbb Z+b\mathbb Z=(a,b)\mathbb Z</math>.
* אם <math>a,b</math> זרים ו־<math>a\mid bc</math> אזי <math>a\mid c</math>.
* אם <math>\forall i:\ p_i\in\mathcal P\ \and\ k_i,m_i\in\mathbb N</math> אזי <math>\left(\prod_i p_i^{k_i},\prod_i p_i^{m_i}\right)=\prod_i p_i^{\min\{k_i,m_i\}}</math>.
* '''אלגוריתם אוקלידס:''' נניח <math>b\ne0</math> ונרצה לחשב <math>(a,b)</math> כאשר <math>a>b</math>. אם <math>r</math> שארית החלוקה של <math>a</math> ב־<math>b</math> אזי <math>(a,b)=(b,r)</math>. נמשיך כך עד שנקבל <math>(x,0)=x</math>. ניתן להעזר באלגוריתם גם כדי לפתור את <math>ax+by=(a,b)</math>: נסמן <math>r_{-1}=a, r_0=b</math> ולכן בתהליך החישוב של <math>(a,b)</math> עם האלגוריתם נקבל <math>\forall0\le i\le k:\ r_{i-1}=r_iq_{i+1}+r_{i+1}</math> כאשר <math>r_{k+1}=(a,b)</math>. לפיכך:{{left|<math>\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}</math>}}
* '''משוואה דיאופנטית ב־2 משתנים:''' נרצה לפתור <math>ax+by=c</math> כאשר <math>x,y</math> משתנים והשאר קבועים. נחלק למקרים:
:* <math>0\ne(a,b)\nmid c</math>: אין פתרון.
:* <math>(a,b)=1</math>: ניתן לפתור <math>ax_0+by_0=1</math> ע״י אלגוריתם אוקלידס (כמפורט בהמשך הסעיף). הפתרון הכללי הוא <math>x=cx_0+bk, y=cy_0-ak</math> לכל <math>k</math>.
:* <math>1\ne(a,b)\mid c</math>: נחלק את אגפי המשוואה ב־<math>(a,b)</math> ונקבל משוואה חדשה מהמקרה הקודם.
::* אם בפרט <math>(a,b)=c</math> אז ניתן לפתור גם באמצעות אלגוריתם אוקלידס.
* נאמר ש־<math>a,b</math> חופפים מודולו <math>m>1</math> (ונסמן <math>a\equiv b\pmod m</math>) אם <math>m\mid a-b</math>. <math>\equiv</math> מגדיר יחס שקילות כאשר <math>\bar a=[a]=a+m\mathbb Z</math> מחלקת השקילות של <math>a</math> ו־<math>\mathbb Z_m</math> קבוצת מחלקות השקילות.
* אם <math>m>1,\ k\ne0</math> ו־<math>ka\equiv kb\pmod m</math> אז <math>a\equiv b\pmod{m/(k,m)}</math>.
* יהי <math>\bar a\in\mathbb Z_m</math>. <math>(a,m)=1</math> אם״ם <math>\bar a</math> הפיך. ניתן למצוא את ההופכי ל־<math>\bar a</math> ע״י פתירת <math>ax+my=1</math>, ואז <math>\bar a^{-1}=\bar x</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>(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>.
* אם <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>.
* אם <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>.
