תקציר תורת המספרים, סמסטר א תשע״ג

סימונים

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

תקציר

• משפט פיאנו: קיימת קבוצה בודדה [math]\displaystyle{ \mathbb N }[/math] שעבורה יש פונקציה [math]\displaystyle{ S:\mathbb N\to\mathbb N }[/math] המקיימת את אקסיומות פיאנו: [math]\displaystyle{ S }[/math] חח״ע, [math]\displaystyle{ 0\not\in\mbox{Im}(S) }[/math], [math]\displaystyle{ 0\in\mathbb N }[/math] ואם [math]\displaystyle{ K\subseteq\mathbb N }[/math] מקיימת [math]\displaystyle{ 0\in K\ \and\ (x\in K\iff S(x)\in K) }[/math] אזי [math]\displaystyle{ K=\mathbb N }[/math].
• [math]\displaystyle{ \mathbb Z\setminus\{0\} }[/math] מחולק לשלוש קבוצות: יחידות – [math]\displaystyle{ U:=\{\pm1\} }[/math], ראשוניים – [math]\displaystyle{ \mathcal P:=\{p\in\mathbb Z\setminus U:\ \forall ab=p:\ a\in U\ \or\ b\in U\} }[/math] ופריקים – [math]\displaystyle{ \mathbb Z\setminus\{0\}\setminus U\setminus\mathcal P }[/math].
• לכל [math]\displaystyle{ a\in\mathbb N^+ }[/math] ו־[math]\displaystyle{ b }[/math] קיים זוג יחיד של שארית [math]\displaystyle{ r }[/math] ומנה [math]\displaystyle{ q }[/math] כך ש־[math]\displaystyle{ b=qa+r,\ 0\le r\lt a }[/math].
• המשפט הבסיסי של האתריתמטיקה: כל מספר ב־[math]\displaystyle{ \mathbb Z\setminus\{0,\pm1\} }[/math] ניתן לפירוק יחיד (עד כדי סדר ההכפלה) של גורמים ראשוניים.
• למת אוקלידס: אם [math]\displaystyle{ p\mid ab }[/math] אז [math]\displaystyle{ p\mid a\ \or\ p\mid b }[/math].
• נסמן [math]\displaystyle{ p^m\mid\!\mid a }[/math] אם [math]\displaystyle{ p^m\mid a\ \and\ p^{m+1}\nmid a }[/math].
• נניח ש־[math]\displaystyle{ a }[/math] ו/או [math]\displaystyle{ b }[/math] שונים מ־0. אזי קיים [math]\displaystyle{ d\in\mathbb N^+ }[/math] יחיד (הנקרא מחלק משותף מקסימלי של [math]\displaystyle{ a,b }[/math] ומסומן [math]\displaystyle{ \gcd(a,b)=(a,b) }[/math]) עבורו [math]\displaystyle{ d\mid a,b }[/math] ואם [math]\displaystyle{ d'\in\mathbb Z }[/math] כך ש־[math]\displaystyle{ d'\mid a,b }[/math] אזי [math]\displaystyle{ d'\mid d }[/math].
• אם [math]\displaystyle{ a\mid b,c }[/math] אזי [math]\displaystyle{ \forall x,y\in\mathbb Z:\ a\mid xb+yc }[/math].
• [math]\displaystyle{ (a,b)=\min\{xa+yb:\ x,y\in\mathbb Z\}^+ }[/math].
• [math]\displaystyle{ a\mathbb Z+b\mathbb Z=(a,b)\mathbb Z }[/math].
• אם [math]\displaystyle{ a,b }[/math] זרים ו־[math]\displaystyle{ a\mid bc }[/math] אזי [math]\displaystyle{ a\mid c }[/math].
• אם [math]\displaystyle{ \forall i:\ k_i,m_i\in\mathbb N }[/math] וה־[math]\displaystyle{ p_i }[/math] שונים זה מזה אזי [math]\displaystyle{ \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]\displaystyle{ m }[/math] יקרא חופשי מראשוניים אם [math]\displaystyle{ \nexists p\in\mathcal P:\ p^2\mid m }[/math].
• אלגוריתם אוקלידס: נניח [math]\displaystyle{ b\ne0 }[/math] ונרצה לחשב [math]\displaystyle{ (a,b) }[/math] כאשר [math]\displaystyle{ a\gt b }[/math]. אם [math]\displaystyle{ r }[/math] שארית החלוקה של [math]\displaystyle{ a }[/math] ב־[math]\displaystyle{ b }[/math] אזי [math]\displaystyle{ (a,b)=(b,r) }[/math]. נמשיך כך עד שנקבל [math]\displaystyle{ (x,0)=x }[/math]. ניתן להעזר באלגוריתם גם כדי לפתור את [math]\displaystyle{ ax+by=(a,b) }[/math]: נסמן [math]\displaystyle{ r_{-1}=a, r_0=b }[/math] ולכן בתהליך החישוב של [math]\displaystyle{ (a,b) }[/math] עם האלגוריתם נקבל [math]\displaystyle{ \forall0\le i\le k:\ r_{i-1}=r_iq_{i+1}+r_{i+1} }[/math] כאשר [math]\displaystyle{ r_{k+1}=(a,b) }[/math]. לפיכך:
  [math]\displaystyle{ \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]\displaystyle{ a,b }[/math] חופפים מודולו [math]\displaystyle{ m\gt 1 }[/math] (ונסמן [math]\displaystyle{ a\equiv b\pmod m }[/math]) אם [math]\displaystyle{ m\mid a-b }[/math]. [math]\displaystyle{ \equiv }[/math] מגדיר יחס שקילות כאשר [math]\displaystyle{ \bar a=[a]=a+m\mathbb Z }[/math] מחלקת השקילות של [math]\displaystyle{ a }[/math] ו־[math]\displaystyle{ \mathbb Z_m }[/math] קבוצת מחלקות השקילות.
• אם [math]\displaystyle{ m\gt 1,\ k\ne0 }[/math] ו־[math]\displaystyle{ ka\equiv kb\pmod m }[/math] אז [math]\displaystyle{ a\equiv b\pmod{m/(k,m)} }[/math].
• יהי [math]\displaystyle{ \bar a\in\mathbb Z_m }[/math]. [math]\displaystyle{ (a,m)=1 }[/math] אם״ם [math]\displaystyle{ \bar a }[/math] הפיך. ניתן למצוא את ההופכי ל־[math]\displaystyle{ \bar a }[/math] ע״י פתירת [math]\displaystyle{ ax+my=1 }[/math], ואז [math]\displaystyle{ \bar a^{-1}=\bar x }[/math].
• [math]\displaystyle{ U_m:=\{\bar a\in\mathbb Z_m:\ (a,m)=1\}\subset\mathbb Z_m }[/math].
• פונקציית אוילר היא [math]\displaystyle{ \varphi:\mathbb N^+\to\mathbb N^+ }[/math] עבורה [math]\displaystyle{ \varphi(1):=1,\ \varphi(m):=|U_m| }[/math].
• פונקציית אוילר כפלית אריתמטית.
• מערכת מלאה מודולו m היא קבוצה [math]\displaystyle{ \{a_i\}_{i=1}^m\subseteq\mathbb Z }[/math] עבורה [math]\displaystyle{ \forall a:\ \exists i:\ a\equiv a_i\pmod m }[/math]. קיים [math]\displaystyle{ i }[/math] יחיד כנ״ל לכל [math]\displaystyle{ a }[/math]. באופן שקול, המערכת מלאה מודולו [math]\displaystyle{ m }[/math] אם [math]\displaystyle{ \mathbb Z_m=\{\bar a_i\}_{i=1}^m }[/math].
• אם [math]\displaystyle{ \{a_i\}_{i=1}^m }[/math] מלאה מודולו [math]\displaystyle{ m }[/math], [math]\displaystyle{ (\alpha,m)=1 }[/math] ו־[math]\displaystyle{ k }[/math] שלם אזי [math]\displaystyle{ \{\alpha a_i+k\}_{i=1}^m }[/math] מלאה מודולו [math]\displaystyle{ m }[/math].
• מערכת מצומצמת מודולו m היא קבוצה [math]\displaystyle{ \{a_i\}_{i=1}^{\varphi(m)} }[/math] כך ש־[math]\displaystyle{ \forall\bar a\in U_m:\ \exists i:\ a\equiv a_i\pmod m }[/math]. באופן שקול, [math]\displaystyle{ U_m=\{\bar a_i\}_{i=1}^m }[/math].
• אם [math]\displaystyle{ \{a_i\}_{i=1}^{\varphi(m)} }[/math] מצומצמת מודולו [math]\displaystyle{ m }[/math] ו־[math]\displaystyle{ (\alpha,m)=1 }[/math] אז [math]\displaystyle{ \{\alpha a_i\}_{i=1}^{\varphi(m)} }[/math] מצומצמת מודולו [math]\displaystyle{ m }[/math].
• אם [math]\displaystyle{ \forall i:\ p_i^{e_i}\mid\!\mid m }[/math] אזי [math]\displaystyle{ \varphi(m)=m\prod_i\left(1-\frac1{p_i}\right) }[/math]. בפרט, [math]\displaystyle{ \varphi\!\left(p^e\right)=p^e-p^{e-1} }[/math].
• משפט גאוס: [math]\displaystyle{ \sum_{d\mid m}\varphi(d)=m }[/math].
• משפט אוילר: אם [math]\displaystyle{ (a,m)=1 }[/math] אז [math]\displaystyle{ a^{\varphi(m)}\equiv1\pmod m }[/math]. משפט פרמה הוא מקרה פרטי כאשר [math]\displaystyle{ m }[/math] ראשוני.
• משפט וילסון: [math]\displaystyle{ (p-1)!\equiv-1\pmod p }[/math].
• מבחן הראשוניות של Salovay & Strassen: [math]\displaystyle{ m }[/math] ראשוני אם״ם [math]\displaystyle{ m=2 }[/math] או [math]\displaystyle{ \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]\displaystyle{ m }[/math] פריק אז [math]\displaystyle{ x }[/math] שלא מקיים את התנאי הנ״ל נקרא עד לפריקות של [math]\displaystyle{ m }[/math].
• אם [math]\displaystyle{ m }[/math] פריק אז לפחות חצי מהמספרים [math]\displaystyle{ 1,2,\dots,m-1 }[/math] הם עדים לפריקות.

• משפט גאוס: [math]\displaystyle{ U_p }[/math] חבורה ציקלית, כלומר קיים [math]\displaystyle{ g\in U_p }[/math] כך ש־[math]\displaystyle{ \forall a\in U_p:\ \exists n:\ g^n\equiv a\pmod p }[/math].

• לכל [math]\displaystyle{ a }[/math] אותו [math]\displaystyle{ n }[/math] יחיד מודולו [math]\displaystyle{ p-1 }[/math] ולכן נקרא "הלוגריתם מודולו [math]\displaystyle{ p }[/math] של [math]\displaystyle{ a }[/math] לפי [math]\displaystyle{ g }[/math]" ומסומן [math]\displaystyle{ \log_g^{(p)}(a) }[/math].
• כל [math]\displaystyle{ g }[/math] כזה נקרא "שורש פרימיטיבי". יש [math]\displaystyle{ \varphi(p-1) }[/math] כאלה.
• הכללה: [math]\displaystyle{ U_n }[/math] ציקלית אם״ם [math]\displaystyle{ n\in\{2,4\}\cup\{p^k,2p^k:\ p\in\mathcal P\setminus\{2\}\ \and\ k\in\mathbb N^+\} }[/math].

פונקציות אריתמטיות

• [math]\displaystyle{ f:\mathbb N^+\to\mathbb C }[/math] נקראת פונקציה אריתמטית. בד״כ [math]\displaystyle{ \mbox{Im}(f)\subseteq\mathbb Z }[/math].
• קונבולוציית דיריכלה בין שתי פונקציות אריתמטיות [math]\displaystyle{ f,g }[/math] מוגדרת ע״י [math]\displaystyle{ (f*g)(n)=\sum_{d\mid n}d(d)g\!\left(\frac nd\right)=\sum_{mk=n}f(m)g(k) }[/math]. זו פעולה קומוטטיבית ואסוציאטיבית.
• נסמן [math]\displaystyle{ \delta_k(n):=1_{\{k\}}=\begin{cases}1,&n=k\\0,&\text{else}\end{cases} }[/math]. [math]\displaystyle{ \delta_1 }[/math] היא פונקציית היחידה ביחס לקונבולוציה, כלומר [math]\displaystyle{ \forall f:\ \delta_1*f=f }[/math].
• [math]\displaystyle{ f }[/math] אריתמטית תקרא כפלית אם [math]\displaystyle{ \forall m,n:\ f(mn)=f(m)f(n) }[/math] וכפלית אריתמטית אם [math]\displaystyle{ \forall (m,n)=1:\ f(mn)=f(m)f(n) }[/math].
• אם [math]\displaystyle{ f,g }[/math] כפליות אריתמטיות אז כך גם [math]\displaystyle{ f*g }[/math].
• פונקציית הממוצע האריתמטי של [math]\displaystyle{ f }[/math] מוגדרת ע״י [math]\displaystyle{ F(n):=\sum_{d\mid n}f(d)=(C*f)(n) }[/math] כאשר [math]\displaystyle{ \forall n:\ C(n)=1 }[/math].
• אם [math]\displaystyle{ f*g=\delta_1 }[/math] אז [math]\displaystyle{ f }[/math] נקראת הפיכה (ביחס לקונבולוציית דיריכלה) ונסמן [math]\displaystyle{ f^{-1}:=g }[/math].
• [math]\displaystyle{ f }[/math] הפיכה אם״ם [math]\displaystyle{ f(1)=\pm1 }[/math].
• אם [math]\displaystyle{ f }[/math] הפיכה וכפלית אריתמטית אז [math]\displaystyle{ f^{-1} }[/math] כפלית אריתמטית.
• פונקציית מוביוס היא [math]\displaystyle{ \mu=C^{-1} }[/math] ומקיימת [math]\displaystyle{ \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]\displaystyle{ \varphi(n)=\sum_{d\mid n}\mu\!\left(\frac md\right)d }[/math].
• מגדירים [math]\displaystyle{ \tau(n):=|\{d\in\mathbb N:\ d\mid n\}|=\sum_{d\mid n}1=(C*C)(n) }[/math].
• נגדיר [math]\displaystyle{ d_k(n):=\sum_{d\mid n}d^k }[/math]. מקרה שימושי הוא [math]\displaystyle{ d:=d_1 }[/math] ואז [math]\displaystyle{ d=C\times I }[/math] כאשר [math]\displaystyle{ \forall n:\ I(n)=n }[/math].
• [math]\displaystyle{ \varphi*\tau=d }[/math].

חוג השלמים של גאוס

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

• אם [math]\displaystyle{ \alpha\in\mathbb Z[\mathrm i] }[/math] ו־[math]\displaystyle{ u }[/math] יחידה אז [math]\displaystyle{ \alpha,u\alpha }[/math] נקראים דומים.
• נגדיר [math]\displaystyle{ N:\mathbb Z[\mathrm i]\to\mathbb Z }[/math] ע״י [math]\displaystyle{ N(a+b\mathrm i)=a^2+b^2=|a+b\mathrm i|^2 }[/math]. היא כפלית ([math]\displaystyle{ N(\alpha\beta)=N(\alpha)N(\beta) }[/math]) ו־[math]\displaystyle{ u }[/math] יחידה אם״ם [math]\displaystyle{ N(u)=1 }[/math].
• ראשוני של גאוס הוא שלם [math]\displaystyle{ \alpha }[/math] של גאוס שאינו יחידה ואם [math]\displaystyle{ \alpha=\beta\gamma }[/math] אז [math]\displaystyle{ \beta }[/math] או [math]\displaystyle{ \gamma }[/math] יחידות.
• אם [math]\displaystyle{ \alpha,\beta\in\mathbb Z[\mathrm i] }[/math] כך ש־[math]\displaystyle{ \beta\ne0 }[/math] אז יש [math]\displaystyle{ q,r\in\mathbb Z[\mathrm i] }[/math] עבורם [math]\displaystyle{ \alpha=\beta q+r }[/math] כך ש־[math]\displaystyle{ N(r)\lt N(\beta) }[/math].
• משפט גאוס: ב־[math]\displaystyle{ \mathbb Z[\mathrm i] }[/math] קיים פירוק יחיד לגורמים ראשוניים של גאוס.
• הראשוניים של גאוס מתחלקים לסוגים הבאים:

• [math]\displaystyle{ 1+\mathrm i }[/math]. הוא "קשור" ל־2 ע״י [math]\displaystyle{ 2=-(1+\mathrm i)^2 }[/math].
• לכל [math]\displaystyle{ p\equiv1\pmod4 }[/math] יש פתרון ל־[math]\displaystyle{ x^2+y^2=p }[/math]. המספרים [math]\displaystyle{ x\pm\mathrm iy }[/math] הם ראשוניים לא דומים של גאוס.
• כל [math]\displaystyle{ p\equiv3\pmod4 }[/math] הוא גם ראשוני של גאוס.

• כל ראשוני של גאוס מחלק ראשוני טבעי כלשהו.
• אם [math]\displaystyle{ N(\alpha)\in\mathcal P }[/math] אז [math]\displaystyle{ \alpha }[/math] ראשוני של גאוס.

פתרון משוואות דיופנטיות

• משוואה לינארית ב־2 נעלמים: נרצה לפתור [math]\displaystyle{ ax+by=c }[/math] כאשר [math]\displaystyle{ x,y }[/math] משתנים והשאר קבועים. נחלק למקרים:

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

• אם בפרט [math]\displaystyle{ (a,b)=c }[/math] אז ניתן לפתור גם באמצעות אלגוריתם אוקלידס.

• משפט השאריות הסיני: נניח ש־[math]\displaystyle{ \forall i\ne j:\ (m_i,m_j)=1 }[/math] ונתונה [math]\displaystyle{ \{c_i\}_{i=1}^r\subset\mathbb Z }[/math]. למערכת [math]\displaystyle{ \forall i:\ x\equiv c_i\pmod{m_i} }[/math] קיים פתרון יחיד מודולו [math]\displaystyle{ m=\prod_{i=1}^r m_i }[/math].

• אם [math]\displaystyle{ \forall j:\ x_i\equiv\delta_i(j)\pmod{m_j} }[/math] אז [math]\displaystyle{ x\equiv\sum_{i=1}^r c_ix_i\pmod m }[/math]. ה־[math]\displaystyle{ x_i }[/math]־ים מקיימים [math]\displaystyle{ x_i=\frac m{m_i}b_i }[/math] כאשר [math]\displaystyle{ b_i:\equiv\left(\frac m{m_i}\right)^{-1}\pmod{m_i} }[/math].
• הכללה: אם לא נתון ש־[math]\displaystyle{ \forall i\ne j:\ (m_i,m_j)=1 }[/math] אז יש פתרון אם״ם [math]\displaystyle{ \forall i\ne j:\ c_i\equiv c_j\pmod{(m_i,m_j)} }[/math].

משוואות ריבועיות

בפרק זה [math]\displaystyle{ p\ne2 }[/math] ו־[math]\displaystyle{ b }[/math] אי־זוגי.

• אם קיים פתרון ל־[math]\displaystyle{ x^2\equiv a\pmod p }[/math] אז [math]\displaystyle{ a }[/math] יקרא שארית ריבועית (ש״ר).
• יש [math]\displaystyle{ \frac{p+1}2 }[/math] שאריות ריבועיות ב־[math]\displaystyle{ \mathbb Z_p }[/math] והן [math]\displaystyle{ 0^2,1^2,\dots,\left(\frac{p-1}2\right)^2 }[/math].
• אם [math]\displaystyle{ m^2\equiv n^2\pmod p }[/math] אז [math]\displaystyle{ m\equiv\pm n\pmod p }[/math].
• סימן לז׳נדר: [math]\displaystyle{ \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} }[/math]. לפיכך [math]\displaystyle{ a }[/math] שארית ריבועית אם״ם [math]\displaystyle{ \left(\frac am\right)\ne-1 }[/math].
• משפט אוילר: [math]\displaystyle{ a^\frac{p-1}2\equiv\left(\frac ap\right)\pmod p }[/math].
• למת גאוס: נסמן [math]\displaystyle{ p_1:=\frac{p-1}2 }[/math] ונגדיר [math]\displaystyle{ \forall 0\le i\le p_1:\ r_i:\equiv ia\pmod p }[/math] כאשר [math]\displaystyle{ -p_1\le r_i\le p_1 }[/math]. אזי [math]\displaystyle{ \left(\frac ap\right)=\prod_{i=1}^{p_1}\sgn(r_i) }[/math].
• סימן יעקובי: יהי [math]\displaystyle{ b=\prod_{i=1}^r p_i }[/math]. מגדירים [math]\displaystyle{ \left(\frac ab\right)=\prod_{i=1}^r\left(\frac a{p_i}\right) }[/math].
• אם [math]\displaystyle{ \left(\frac ab\right)=-1 }[/math] אז ל־[math]\displaystyle{ x^2\equiv a\pmod b }[/math] אין פתרון. ההפך לא תמיד נכון.
• תכונות של סימני לז׳נדר ויעקובי:

• [math]\displaystyle{ a_1\equiv a_2\pmod b }[/math] אז [math]\displaystyle{ \left(\frac{a_1}b\right)=\left(\frac{a_2}b\right) }[/math].
• [math]\displaystyle{ \left(\frac{a_1 a_2}b\right)=\left(\frac{a_1}b\right)\left(\frac{a_2}b\right) }[/math] ו־[math]\displaystyle{ \left(\frac a{b_1 b_2}\right)=\left(\frac a{b_1}\right)\left(\frac a{b_2}\right) }[/math].
• [math]\displaystyle{ \left(\frac1b\right)=1 }[/math], [math]\displaystyle{ \left(\frac{-1}b\right)=(-1)^\frac{b-1}2 }[/math] ו־[math]\displaystyle{ \left(\frac2b\right)=(-1)^\frac{b^2-1}8 }[/math].
• אם גם [math]\displaystyle{ a }[/math] אי־זוגי אז [math]\displaystyle{ \left(\frac ab\right)=(-1)^\frac{(a-1)(b-1)}4\left(\frac ba\right) }[/math].

• למת לגרנז׳: [math]\displaystyle{ -1 }[/math] שארית ריבועית מודולו [math]\displaystyle{ p }[/math] אם״ם [math]\displaystyle{ p\equiv1\pmod4 }[/math]. השורש מודולו [math]\displaystyle{ p }[/math] הוא [math]\displaystyle{ \frac{p-1}2! }[/math].
• משפט פרמה: ל־[math]\displaystyle{ x^2+y^2=p }[/math] יש פתרון בשלמים אם״ם [math]\displaystyle{ p\equiv1\pmod4 }[/math] (או [math]\displaystyle{ p=2 }[/math]).

• אם [math]\displaystyle{ p }[/math] לאו דווקא ראשוני אבל [math]\displaystyle{ p\equiv3\pmod4 }[/math] אז עדיין אין פתרון בשלמים.
• עקרון דיריכלה: נרצה לפתור את המשוואה. נסמן [math]\displaystyle{ N:=\frac{p-1}2! }[/math] ונניח [math]\displaystyle{ x_1+Ny_1\equiv x_1+Ny_2\pmod p }[/math] כך ש־[math]\displaystyle{ x_1\ne x_2\ \or\ y_1\ne y_2 }[/math]. נסמן [math]\displaystyle{ x=x_1-x_2 }[/math] ו־[math]\displaystyle{ y=y_1-y_2 }[/math] והם פותרים את [math]\displaystyle{ x^2+y^2=p }[/math].

• משפט אוילר: ל־[math]\displaystyle{ x^2+y^2=n\in\mathbb N^+ }[/math] יש פתרון בשלמים אם״ם [math]\displaystyle{ \forall p^e\mid\!\mid n\ \and\ p\equiv3\pmod4:\ 2\mid e }[/math].
• משפט דיריכלה: לכל [math]\displaystyle{ a\gt 1 }[/math] ו־[math]\displaystyle{ b }[/math] זר לו יש אינסוף ראשוניים [math]\displaystyle{ p }[/math] עבורם [math]\displaystyle{ p\equiv b\pmod a }[/math]. בפרט יש אינסוף ראשוניים עבורם [math]\displaystyle{ p\equiv1,3\pmod4 }[/math].
• [math]\displaystyle{ a }[/math] שארית ריבועית מודולו [math]\displaystyle{ p }[/math] לכל [math]\displaystyle{ p\in\mathcal P^+ }[/math] אם״ם [math]\displaystyle{ \sqrt a\in\mathbb Z }[/math].
• יהי [math]\displaystyle{ a\not\equiv0\pmod p }[/math] ונרצה לפתור [math]\displaystyle{ x^2\equiv a\pmod p }[/math] כשנתון ש־[math]\displaystyle{ a }[/math] שארית ריבועית: [math]\displaystyle{ 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]\displaystyle{ p\equiv1\pmod8 }[/math] יש פתרון אך הוא מורכב ולא נביאו.

משוואות פיתגורס

נרצה למצוא את הפתרונות השלמים של [math]\displaystyle{ x^2+y^2=z^2 }[/math].

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

עקומות רציונליות

• יהי [math]\displaystyle{ f }[/math] פולינום בשני משתנים עם מקדמים רציונלים (כלומר [math]\displaystyle{ f\in\mathbb Q[x,y] }[/math]) שאינה פריקה (כלומר אין [math]\displaystyle{ g,h\in\mathbb C[x,y] }[/math] לא קבועות כך ש־[math]\displaystyle{ f=g\cdot h }[/math]). העקומה [math]\displaystyle{ C_f:=\{(x,y)\in\mathbb R^2:\ f(x,y)=0\} }[/math] תקרא רציונלית אם קיימת לה פרמטריזציה [math]\displaystyle{ \gamma(t)=(x(t),y(t)) }[/math] (למעט, אולי, בכמה נקודות מבודדות) כאשר [math]\displaystyle{ x,y }[/math] הם חלוקות של פולינומים במשתנה אחד עם מקדמים רציונלים.
• נניח ש־[math]\displaystyle{ f }[/math] לא פריקה ו־[math]\displaystyle{ \deg(f)=2 }[/math]. אם ל־[math]\displaystyle{ f(x,y)=0 }[/math] יש פתרון ב־[math]\displaystyle{ \mathbb Q^2 }[/math] אז [math]\displaystyle{ C_f }[/math] רציונלית.
• משפט לג׳נדר: נרצה לדעת אם ל־[math]\displaystyle{ ax^2+by^2=c }[/math] יש פתרון רציונלי כאשר [math]\displaystyle{ a,b,c\in\mathbb Q }[/math]. ניתן להניח בה״כ ש־[math]\displaystyle{ a,b,c }[/math] שלמים, זרים בזוגות וחופשיים מריבועים. קיים םתרון רציונלי אם״ם [math]\displaystyle{ -ab }[/math] ש״ר מודולו [math]\displaystyle{ c }[/math], [math]\displaystyle{ ac }[/math] ש״ר מודולו [math]\displaystyle{ b }[/math] ו־[math]\displaystyle{ bc }[/math] ש״ר מודולו [math]\displaystyle{ a }[/math].

משוואות פל

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

• לכל משוואת פל קיים פתרון לא טריוויאלי.
• יהי [math]\displaystyle{ x_0+\sqrt m y_0 }[/math] הפתרון החיובי המינימלי (נקרא "הפתרון הפונדמנטלי"), כלומר [math]\displaystyle{ x_0,y_0\gt 0 }[/math] כך ש־[math]\displaystyle{ x_0 }[/math] הוא ה־[math]\displaystyle{ x }[/math] המינימלי הגדול מ־1 שקיים לו [math]\displaystyle{ y }[/math] הפותר את המשוואה. אזי כל הפתרונות הם [math]\displaystyle{ \pm\left(x_0+\sqrt my_0\right)^n }[/math] עבור [math]\displaystyle{ n\in\mathbb N }[/math].

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

משוואות פולינומיאליות

יהי [math]\displaystyle{ m\gt 1 }[/math] ונרצה לפתור או לבדוק כמה פתרונות יש ל־[math]\displaystyle{ f(x)\equiv0\pmod m }[/math] כאשר [math]\displaystyle{ f\in\mathbb Z[x] }[/math].

• משוואה לינארית: [math]\displaystyle{ ax\equiv b }[/math]. קיים פתרון אם״ם [math]\displaystyle{ d:=(a,m)\mid b }[/math]. אם [math]\displaystyle{ x_0 }[/math] פתרון פרטי של [math]\displaystyle{ ax\equiv b\pmod{m/d} }[/math] אז כל הפתרונות הם [math]\displaystyle{ x\equiv x_0+k\frac md\pmod m }[/math] כאשר [math]\displaystyle{ 0\le k\le d-1 }[/math], ויש [math]\displaystyle{ d }[/math] פתרונות.
• מגדירים [math]\displaystyle{ N_f(m)=|\{x\in\mathbb Z_m:\ f(x)\equiv0\pmod m\}| }[/math]. זו פונקציה כפלית אריתמטית.
• שיטת הנזל: יהי [math]\displaystyle{ x_0 }[/math] פתרון של [math]\displaystyle{ f(x)\equiv0\pmod{p^e} }[/math] כאשר [math]\displaystyle{ e\in\mathbb N^+ }[/math] ונרצה לפתור [math]\displaystyle{ f(x)\equiv0\pmod{p^{e+1}} }[/math]. נחלק למקרים לפי הנגזרת בנקודה זו:

• [math]\displaystyle{ f'(x_0)\equiv0\pmod p }[/math]: הפתרונות היחידים (מודולו [math]\displaystyle{ p^{e+1} }[/math]) למשוואה הם [math]\displaystyle{ x_0+kp^e }[/math] עבור [math]\displaystyle{ 0\le k\le p-1 }[/math].
• [math]\displaystyle{ f'(x_0)\not\equiv0\pmod p }[/math]: לכן [math]\displaystyle{ \left(f'(x_0)\right)^{-1}\pmod p }[/math] קיים ו־[math]\displaystyle{ x_0+kp^e }[/math] עבור [math]\displaystyle{ k:\equiv-\left(f'(x_0)\right)^{-1}\frac{f(x_0)}{p^e}\pmod p }[/math] הוא הפתרון היחיד.

• משפט בסונט: אם [math]\displaystyle{ x_0 }[/math] שורש של [math]\displaystyle{ f(x)\equiv0\pmod m }[/math] אז קיימת [math]\displaystyle{ g\in\mathbb Z_m[x] }[/math] כך ש־[math]\displaystyle{ f(x)=(x-x_0)g(x) }[/math] ו־[math]\displaystyle{ \deg(g)\lt \deg(f) }[/math].
• חילוק פולינומים: אם [math]\displaystyle{ f,g\in\mathbb Z_m[x] }[/math] ו־[math]\displaystyle{ g }[/math] פולינום מתוקן אז קיימים [math]\displaystyle{ q,r\in\mathbb Z_m[x] }[/math] עבורם [math]\displaystyle{ f=g\cdot q+r }[/math] ו־[math]\displaystyle{ \deg(r)\lt \deg(g) }[/math].
• משפט לגראנז׳: ל־[math]\displaystyle{ f\in\mathbb Z_p[x] }[/math] יש לכל היותר [math]\displaystyle{ \deg(f) }[/math] שורשים. בנוסף, אם [math]\displaystyle{ g\in\mathbb Z[x] }[/math] כך של־[math]\displaystyle{ g(x)\equiv0\pmod m }[/math] יש יותר מ־[math]\displaystyle{ \deg(g) }[/math] שורשים אז אז כל המקדמים ב־[math]\displaystyle{ g }[/math] מתחלקים ב־[math]\displaystyle{ p }[/math].

• הערה: המשפט לא מתקיים ל־[math]\displaystyle{ p }[/math] פריק.

• [math]\displaystyle{ \prod_{a=0}^{p-1}(x-a)\equiv x^p-x\pmod p }[/math].
• ל־[math]\displaystyle{ f\in\mathbb Z_p[x] }[/math] יש [math]\displaystyle{ \deg\!\left(\gcd\!\left(f(x),x^p-x\right)\right) }[/math] שורשים שונים. בפרט, אם [math]\displaystyle{ \deg(f)\le p }[/math] אז ל־[math]\displaystyle{ f }[/math] יש [math]\displaystyle{ \deg(f) }[/math] שורשים שונים אם״ם [math]\displaystyle{ f(x)\mid x^p-x }[/math].