שינויים

* '''משפט פיאנו:''' קיימת קבוצה בודדה <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,b</math> זרים ו־<math>a\mid bc</math> אזי <math>a\mid c</math>.

* אם <math>\forall i:\ k_i,m_i\in\mathbb N</math> וה־<math>p_i</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>}}

* נאמר ש־<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>(a,m)=1</math> אז <math>a^{\varphi(m)}\equiv1\pmod m</math>. ''משפט פרמה'' הוא מקרה פרטי כאשר <math>m</math> ראשוני.

* '''משפט וילסון:''' <math>(p-1)!\equiv-1\pmod p</math>.

:* אם <math>m</math> פריק אז <math>x</math> שלא מקיים את התנאי הנ״ל נקרא עד לפריקות של <math>m</math>.

:* אם <math>m</math> פריק אז לפחות חצי מהמספרים <math>1,2,\dots,m-1</math> הם עדים לפריקות.

:* לכל <math>a</math> אותו <math>n</math> יחיד מודולו <math>p-1</math> ולכן נקרא "הלוגריתם מודולו <math>p</math> של <math>a</math> לפי <math>g</math>" ומסומן <math>\log_g^{(p)}(a)</math>.

:* כל <math>g</math> כזה נקרא "שורש פרימיטיבי". יש <math>\varphi(p-1)</math> כאלה.

* <math>f:\mathbb N^+\to\mathbb C</math> נקראת פונקציה אריתמטית. בד״כ <math>\mbox{Im}(f)\subseteq\mathbb Z</math>.

* '''קונבולוציית דיריכלה''' בין שתי פונקציות אריתמטיות <math>f,g</math> מוגדרת ע״י <math>(f*g)(n)=\sum_{d\mid n}d(d)g\!\left(\frac nd\right)=\sum_{mk=n}f(m)g(k)</math>. זו פעולה קומוטטיבית ואסוציאטיבית.

* <math>\varphi*\tau=d</math>.

האיברים ב־<math>\mathbb Z[\mathrm i]=\mathbb Z+\mathrm i\mathbb Z</math> נקראים שלמים של גאוס. איברי היחידה (כלומר <math>u\in\mathbb Z[\mathrm i]</math> עבורם <math>u^{-1}\in\mathbb Z[\mathrm i]</math>) הם <math>\pm1,\pm\mathrm i</math>.

* אם <math>\alpha\in\mathbb Z[\mathrm i]</math> ו־<math>u</math> יחידה אז <math>\alpha,u\alpha</math> נקראים דומים.

* אם <math>N(\alpha)\in\mathcal P</math> אז <math>\alpha</math> ראשוני של גאוס.

* '''משוואה לינארית ב־2 נעלמים:''' נרצה לפתור <math>ax+by=c</math> כאשר <math>x,y</math> משתנים והשאר קבועים. נחלק למקרים:

:* <math>0\ne(a,b)\nmid c</math>: אין פתרון.

:* {{הערה|הכללה:}} אם לא נתון ש־<math>\forall i\ne j:\ (m_i,m_j)=1</math> אז יש פתרון אם״ם <math>\forall i\ne j:\ c_i\equiv c_j\pmod{(m_i,m_j)}</math>.

בפרק זה <math>p\ne2</math> ו־<math>b</math> אי־זוגי.

* אם קיים פתרון ל־<math>x^2\equiv a\pmod p</math> אז <math>a</math> יקרא ''שארית ריבועית'' (ש״ר).

* יש <math>\frac{p+1}2</math> שאריות ריבועיות ב־<math>\mathbb Z_p</math> והן <math>0^2,1^2,\dots,\left(\frac{p-1}2\right)^2</math>.

* אם <math>m^2\equiv n^2\pmod p</math> אז <math>m\equiv\pm n\pmod p</math>.

* '''משפט אוילר:''' <math>a^\frac{p-1}2\equiv\left(\frac ap\right)\pmod p</math>.

* '''למת גאוס:''' נסמן <math>p_1:=\frac{p-1}2</math> ונגדיר <math>\forall 0\le i\le p_1:\ r_i:\equiv ia\pmod p</math> כאשר <math>-p_1\le r_i\le p_1</math>. אזי <math>\left(\frac ap\right)=\prod_{i=1}^{p_1}\sgn(r_i)</math>.

:* <math>\left(\frac{a_1 a_2}b\right)=\left(\frac{a_1}b\right)\left(\frac{a_2}b\right)</math> ו־<math>\left(\frac a{b_1 b_2}\right)=\left(\frac a{b_1}\right)\left(\frac a{b_2}\right)</math>.

:* <math>\left(\frac1b\right)=1</math>, <math>\left(\frac{-1}b\right)=(-1)^\frac{b-1}2</math> ו־<math>\left(\frac2b\right)=(-1)^\frac{b^2-1}8</math>.

* '''למת לגרנז׳:''' <math>-1</math> שארית ריבועית מודולו <math>p</math> אם״ם <math>p\equiv1\pmod4</math>. השורש מודולו <math>p</math> הוא <math>\frac{p-1}2!</math>.

* '''משפט פרמה:''' ל־<math>x^2+y^2=p</math> יש פתרון בשלמים אם״ם <math>p\equiv1\pmod4</math> (או <math>p=2</math>).

* יהי <math>a\not\equiv0\pmod p</math> ונרצה לפתור <math>x^2\equiv a\pmod p</math> כשנתון ש־<math>a</math> שארית ריבועית: <math>x:\equiv\left(\begin{cases}a^\frac{p+1}4,&p\equiv3\pmod 4\\a^\frac{p+3}8,&p\equiv5\pmod8\ \and\ a^\frac{p-1}4\equiv1\pmod p\\2a(4a)^\frac{p-5}8,&p\equiv5\pmod8\ \and\ a^\frac{p-1}4\equiv-1\pmod p\end{cases}\right)\pmod p</math>. למקרה <math>p\equiv1\pmod8</math> יש פתרון אך הוא מורכב ולא נביאו.

נרצה למצוא את הפתרונות השלמים של <math>x^2+y^2=z^2</math>.

* פתרון יקרא פרמיטיבי אם <math>(x,y,z)=1</math>.

* הפתרונות החיוביים (כלומר <math>x,y,z>1</math>) הפרמיטבים הם מהצורות הבאות: יהיו <math>m>n>0</math> זרים. אם הם אי־זוגיים אז <math>x=mn,\ y=\frac{m^2-n^2}2,\ z=\frac{m^2+n^2}2</math> ואם אחד מהם זוגי אז <math>x=2mn,\ y=m^2-n^2,\ z=m^2+n^2</math>.

* יהי <math>f</math> פולינום בשני משתנים עם מקדמים רציונלים (כלומר <math>f\in\mathbb Q[x,y]</math>) שאינה פריקה (כלומר אין <math>g,h\in\mathbb C[x,y]</math> לא קבועות כך ש־<math>f=g\cdot h</math>). העקומה <math>C_f:=\{(x,y)\in\mathbb R^2:\ f(x,y)=0\}</math> תקרא רציונלית אם קיימת לה פרמטריזציה <math>\gamma(t)=(x(t),y(t))</math> (למעט, אולי, בכמה נקודות מבודדות) כאשר <math>x,y</math> הם חלוקות של פולינומים במשתנה אחד עם מקדמים רציונלים.

* נניח ש־<math>f</math> לא פריקה ו־<math>\deg(f)=2</math>. אם ל־<math>f(x,y)=0</math> יש פתרון ב־<math>\mathbb Q^2</math> אז <math>C_f</math> רציונלית.

* '''משפט לג׳נדר:''' נרצה לדעת אם ל־<math>ax^2+by^2=c</math> יש פתרון רציונלי כאשר <math>a,b,c\in\mathbb Q</math>. ניתן להניח בה״כ ש־<math>a,b,c</math> שלמים, זרים בזוגות וחופשיים מריבועים. קיים פתרון רציונלי אם״ם <math>-ab</math> ש״ר מודולו <math>c</math>, <math>ac</math> ש״ר מודולו <math>b</math> ו־<math>bc</math> ש״ר מודולו <math>a</math>.

יהי <math>m>1</math> שאינו ריבועי. משוואת פל היא <math>x^2-my^2=1</math> כאשר <math>x,y\in\mathbb Z</math>. תמיד קיים הפתרון הטריוויאלי <math>x=1,\ y=0</math>.

* לכל משוואת פל קיים פתרון לא טריוויאלי.

:* {{הערה|הערה:}} בהינתן הפתרון המינימלי נוח לחשב את שאר הפתרונות עם הנוסחה <math>\left(x_0+\sqrt my_0\right)\left(x+\sqrt my\right)=(x_0x+my_0y)+\sqrt m(y_0x+x_0y)</math>.

יהי <math>m>1</math> ונרצה לפתור או לבדוק כמה פתרונות יש ל־<math>f(x)\equiv0\pmod m</math> כאשר <math>f\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> פתרונות.

* מגדירים <math>N_f(m)=|\{x\in\mathbb Z_m:\ f(x)\equiv0\pmod m\}|</math>. זו פונקציה כפלית אריתמטית.

* '''שיטת הנזל:''' יהי <math>x_0</math> פתרון של <math>f(x)\equiv0\pmod{p^e}</math> כאשר <math>e\in\mathbb N^+</math> ונרצה לפתור <math>f(x)\equiv0\pmod{p^{e+1}}</math>. נחלק למקרים לפי הנגזרת בנקודה זו:

:* <math>f'(x_0)\not\equiv0\pmod p</math>: לכן <math>\left(f'(x_0)\right)^{-1}\pmod p</math> קיים ו־<math>x_0+kp^e</math> עבור <math>k:\equiv-\left(f'(x_0)\right)^{-1}\frac{f(x_0)}{p^e}\pmod p</math> הוא הפתרון היחיד.

* '''משפט בסונט:''' אם <math>x_0</math> שורש של <math>f(x)\equiv0\pmod m</math> אז קיימת <math>g\in\mathbb Z_m[x]</math> כך ש־<math>f(x)=(x-x_0)g(x)</math> ו־<math>\deg(g)<\deg(f)</math>.