שינויים
== סימונים ==בקורס זה <math>\mathbb N=\{0,1,2,\dots\}</math> ו־<math>\mathbb N^+=\{1,2,\dots\}</math>. כמו כן, אלא אם צוין אחרת, <math>A^+:=A\cap\mathbb N^+</math> וכל , כל המשתנים והנעלמים שלמיםו־<math>p</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\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>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>m</math> יקרא חופשי מראשוניים אם <math>\nexists p\in\mathcal P:\ p^2\mid m</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>m>1,\ k\ne0</math> ו־<math>ka\equiv kb\pmod m</math> אז <math>a\equiv b\pmod{m/(k,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>(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>U_m=\{\bar a_i\}_{i=1}^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_ie_i}\mid\!\mid m</math> אזי <math>\varphi(m)=m\prod_i\left(1-\frac1{p_i}\right)</math>. בפרט, <math>\varphi\!\left(p^le\right)=p^le-p^{le-1}</math>.* '''משפט גאוס:''' <math>\sum_{d\mid m}\varphi\!\left(\frac md\rightd)=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>.* '''מבחן הראשוניות של Salovay & Strassen:''' <math>m</math> ראשוני אם״ם <math>m=2</math> או <math>\forall x\in[1,m-1]\cap\mathbb Z:\ (x,m)1=\ \and\ x^\frac{m-1}2\equiv\left(\frac xm\right)\pmod m</math>.:* אם <math>m</math> פריק אז <math>x</math> שלא מקיים את התנאי הנ״ל נקרא עד לפריקות של <math>m</math>.:* אם <math>m</math> פריק אז לפחות חצי מהמספרים <math>1,2,\dots,m-1</math> הם עדים לפריקות.* '''משפט גאוס:''' <math>U_p</math> חבורה ציקלית, כלומר קיים <math>g\in U_p</math> כך ש־<math>\forall a\in U_p:\ \exists n:\ g^n\equiv a\pmod p</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>U_n</math> ציקלית אם״ם <math>n\in\{2,4\}\cup\{p^k,2p^k:\ p\in\mathcal P\setminus\{2\}\ \and\ k\in\mathbb N^+\}</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>\delta_k(n):=1_{\{k\}}=\begin{cases}1,&n=k\\0,&\text{else}\end{cases}</math>. <math>\delta_1</math> היא פונקציית היחידה ביחס לקונבולוציה, כלומר <math>\forall f:\ \delta_1*f=f</math>.* <math>f</math> אריתמטית תקרא כפלית אם <math>\forall m,n:\ f(mn)=f(m)f(n)</math> וכפלית אריתמטית אם <math>\forall (m,n)=1:\ f(mn)=f(m)f(n)</math>.* אם <math>f,g</math> כפליות אריתמטיות אז כך גם <math>f*g</math>.* '''פונקציית הממוצע האריתמטי''' של <math>f</math> מוגדרת ע״י <math>F(n):=\sum_{d\mid n}f(d)=(C*f)(n)</math> כאשר <math>\forall n:\ C(n)=1</math>.* אם <math>f*g=\delta_1</math> אז <math>f</math> נקראת הפיכה (ביחס לקונבולוציית דיריכלה) ונסמן <math>f^{-1}:=g</math>.* <math>f</math> הפיכה אם״ם <math>f(1)=\pm1</math>.* אם <math>f</math> הפיכה וכפלית אריתמטית אז <math>f^{-1}</math> כפלית אריתמטית.* '''פונקציית מוביוס''' היא <math>\mu=C^{-1}</math> ומקיימת <math>\mu(n)=\begin{cases}(-1)^s,&n=\prod_{i=1}^s p_i\ \and\ \forall i\ne j:\ p_i\ne p_j\end{cases}</math>.* <math>\varphi(n)=\sum_{d\mid n}\mu\!\left(\frac md\right)d</math>.* מגדירים <math>\tau(n):=|\{d\in\mathbb N:\ d\mid n\}|=\sum_{d\mid n}1=(C*C)(n)</math>.* נגדיר <math>d_k(n):=\sum_{d\mid n}d^k</math>. מקרה שימושי הוא <math>d:=d_1</math> ואז <math>d=C\times I</math> כאשר <math>\forall n:\ I(n)=n</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:\mathbb Z[\mathrm i]\to\mathbb Z</math> ע״י <math>N(a+b\mathrm i)=a^2+b^2=|a+b\mathrm i|^2</math>. היא כפלית (<math>N(\alpha\beta)=N(\alpha)N(\beta)</math>) ו־<math>u</math> יחידה אם״ם <math>N(u)=1</math>.* '''ראשוני של גאוס''' הוא שלם <math>\alpha</math> של גאוס שאינו יחידה ואם <math>\alpha=\beta\gamma</math> אז <math>\beta</math> או <math>\gamma</math> יחידות.* אם <math>\alpha,\beta\in\mathbb Z[\mathrm i]</math> כך ש־<math>\beta\ne0</math> אז יש <math>q,r\in\mathbb Z[\mathrm i]</math> עבורם <math>\alpha=\beta q+r</math> כך ש־<math>N(r)<N(\beta)</math>.* '''משפט גאוס:''' ב־<math>\mathbb Z[\mathrm i]</math> קיים פירוק יחיד לגורמים ראשוניים של גאוס.* הראשוניים של גאוס מתחלקים לסוגים הבאים::* <math>1+\mathrm i</math>. הוא "קשור" ל־2 ע״י <math>2=-(1+\mathrm i)^2</math>.:* לכל <math>p\equiv1\pmod4</math> יש פתרון ל־<math>x^2+y^2=p</math>. המספרים <math>x\pm\mathrm iy</math> הם ראשוניים לא דומים של גאוס.:* כל <math>p\equiv3\pmod4</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>(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>\forall i\ne j:\ (m_i,m_j)=1</math> ונתונה <math>\{c_i\}_{ltri=1}^r\subset\mathbb Z</math>. למערכת <math>\forall i:\ x\equiv c_i\pmod{m_i}</math> קיים פתרון יחיד מודולו <math>m=\prod_{i=1}^r m_i</math>.:* אם <math>\forall j:\ x_i\equiv\delta_i(j)\pmod{m_j}</math> אז <math>x\equiv\sum_{i=1}^r c_ix_i\pmod m</math>. ה־<math>x_i</math>־ים מקיימים <math>x_i=\frac m{m_i}b_i</math> כאשר <math>b_i:\equiv\left(\frac m{m_i}\right)^{-1}\pmod{m_i}</math>.:* {{הערה|ℤהכללה:}} אם לא נתון ש־<submath>\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>\left(\frac ap\right):=\begin{cases}0,&a\equiv0\pmod p\\1,&\exists\alpha:\ \alpha^2\equiv a\pmod p\\-1,&\text{else}\end{cases}</submath>. לפיכך <math>a</math> שארית ריבועית אם״ם <math>\left(\frac am\right)\ne-1</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>b=\prod_{i=1}^r p_i</math>. מגדירים <math>\left(\frac ab\right)=\prod_{i=1}^r\left(\frac a{p_i}\right)</math>.* אם <math>\left(\frac ab\right)=-1</math> אז ל־<math>x^2\equiv a\pmod b</math> אין פתרון. ההפך לא תמיד נכון.* '''תכונות של סימני לז׳נדר ויעקובי:''':* <math>a_1\equiv a_2\pmod b</math> אז <math>\left(\frac{a_1}b\right)=\left(\frac{a_2}b\right)</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>a</math> אי־זוגי אז <math>\left(\frac ab\right)=(-1)^\frac{(a-1)(b-1)}4\left(\frac ba\right)</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>p</math> לאו דווקא ראשוני אבל <math>p\equiv3\pmod4</math> אז עדיין אין פתרון בשלמים.:* '''עקרון דיריכלה:''' נרצה לפתור את המשוואה. נסמן <math>N:=\frac{p-1}2!</math> ונניח <math>x_1+Ny_1\equiv x_1+Ny_2\pmod p</math> כך ש־<math>x_1\ne x_2\ \or\ y_1\ne y_2</math>. נסמן <math>x=x_1-x_2</math> ו־<math>y=y_1-y_2</math> והם פותרים את <math>x^2+y^2=p</math>.* '''משפט אוילר:''' ל־<math>x^2+y^2=n\in\mathbb N^+</math> יש פתרון בשלמים אם״ם <math>\forall p^e\mid\!\mid n\ \and\ p\equiv3\pmod4:\ 2\mid e</math>.* '''משפט דיריכלה:''' לכל <math>a>1</math> ו־<math>b</math> זר לו יש אינסוף ראשוניים <math>p</math> עבורם <math>p\equiv b\pmod a</math>. בפרט יש אינסוף ראשוניים עבורם <math>p\equiv1,3\pmod4</math>.* <math>a</math> שארית ריבועית מודולו <math>p</math> לכל <math>p\in\mathcal P^+</math> אם״ם <math>\sqrt a\in\mathbb Z</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>x_0+\sqrt m y_0</math> הפתרון החיובי המינימלי (נקרא "הפתרון הפונדמנטלי"), כלומר <math>x_0,y_0>0</math> כך ש־<math>x_0</math> הוא ה־<math>x</math> המינימלי הגדול מ־1 שקיים לו <math>y</math> הפותר את המשוואה. אזי כל הפתרונות הם <math>\pm\left(x_0+\sqrt my_0\right)^n</math> עבור <math>n\in\mathbb N</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(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> פתרונות.* מגדירים <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)\equiv0\pmod p</math>: הפתרונות היחידים (מודולו <math>p^{e+1}</math>) למשוואה הם <math>x_0+kp^e</math> עבור <math>0\le k\le p-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>.* '''חילוק פולינומים:''' אם <math>f,g\in\mathbb Z_m[x]</math> ו־<math>g</math> פולינום מתוקן אז קיימים <math>q,r\in\mathbb Z_m[x]</math> עבורם <math>f=g\cdot q+r</math> ו־<math>\deg(r)<\deg(g)</math>.* '''משפט לגראנז׳:''' ל־<math>f\in\mathbb Z_p[x]</math> יש לכל היותר <math>\deg(f)</math> שורשים. בנוסף, אם <math>g\in\mathbb Z[x]</math> כך של־<math>g(x)\equiv0\pmod m</math> יש יותר מ־<math>\deg(g)</math> שורשים אז אז כל המקדמים ב־<math>g</math> מתחלקים ב־<math>p</math>.:* {{הערה|הערה:}} המשפט לא מתקיים ל־<math>p</math> פריק.* <math>\prod_{a=0}^{p-1}(x-a)\equiv x^p-x\pmod p</math>.* ל־<math>f\in\mathbb Z_p[x]</math> יש <math>\deg\!\left(\gcd\!\left(f(x),x^p-x\right)\right)</math> שורשים שונים. בפרט, אם <math>\deg(f)\le p</math> אז ל־<math>f</math> יש <math>\deg(f)</math> שורשים שונים אם״ם <math>f(x)\mid x^p-x</math>.
