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

גרסה מ־15:43, 23 בינואר 2013

תוכן עניינים

1 סימונים
2 תקציר

סימונים

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

תקציר

משפט פיאנו: קיימת קבוצה בודדה $\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\mid ab$ אז $p\mid a\ \or\ p\mid b$ .
נסמן $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:\ k_i,m_i\in\mathbb N$ וה־ $p_i$ שונים זה מזה אזי $\left(\prod_i p_i^{k_i},\prod_i p_i^{m_i}\right)=\prod_i p_i^{\min\{k_i,m_i\}}$ .
$m$ יקרא חופשי מראשוניים אם $\nexists p\in\mathcal P:\ p^2\mid m$ .
אלגוריתם אוקלידס: נניח $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}$
נאמר ש־ $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 היא קבוצה $\{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$ . באופן שקול, $U_m=\{\bar a_i\}_{i=1}^m$ .
אם $\{a_i\}_{i=1}^{\varphi(m)}$ מצומצמת מודולו $m$ ו־ $(\alpha,m)=1$ אז $\{\alpha a_i\}_{i=1}^{\varphi(m)}$ מצומצמת מודולו $m$ .
אם $\forall i:\ p_i^{e_i}\mid\!\mid m$ אזי $\varphi(m)=m\prod_i\left(1-\frac1{p_i}\right)$ . בפרט, $\varphi\!\left(p^e\right)=p^e-p^{e-1}$ .
משפט גאוס: $\sum_{d\mid m}\varphi(d)=m$ .
משפט אוילר: אם $(a,m)=1$ אז $a^{\varphi(m)}\equiv1\pmod m$ . משפט פרמה הוא מקרה פרטי כאשר $m$ ראשוני.
משפט וילסון: $(p-1)!\equiv-1\pmod p$ .
מבחן הראשוניות של Salovay & Strassen: $m$ ראשוני אם״ם $m=2$ או $\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$ .

אם $m$ פריק אז $x$ שלא מקיים את התנאי הנ״ל נקרא עד לפריקות של $m$ .
אם $m$ פריק אז לפחות חצי מהמספרים $1,2,\dots,m-1$ הם עדים לפריקות.

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

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

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

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

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

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

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

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

כל ראשוני של גאוס מחלק ראשוני טבעי כלשהו.
אם $N(\alpha)\in\mathcal P$ אז $\alpha$ ראשוני של גאוס.

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

משוואה לינארית ב־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$ אז ניתן לפתור גם באמצעות אלגוריתם אוקלידס.

מערכות משוואות

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

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

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

בפרק זה $p\ne2$ ו־ $b$ אי־זוגי.

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

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

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

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

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

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

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

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

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

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

משוואות פל

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

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

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

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

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

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

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

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

הערה: המשפט לא מתקיים ל־ $p$ פריק.

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

@@ שורה 1: / שורה 1: @@
-בקורס זה <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=\{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\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>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>.
@@ שורה 12: / שורה 14: @@
 * <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>\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>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>}}
-* '''משוואה דיאופנטית ב־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>.
@@ שורה 24: / שורה 22: @@
 * <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>.
+* '''מערכת מלאה מודולו ''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>.
+* '''מערכת מצומצמת מודולו ''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_i}\mid\!\mid m</math> אזי <math>\varphi(m)=m\prod_i\left(1-\frac1{p_i}\right)</math>. בפרט, <math>\varphi\!\left(p^l\right)=p^l-p^{l-1}</math>.
+* אם <math>\forall i:\ p_i^{e_i}\mid\!\mid m</math> אזי <math>\varphi(m)=m\prod_i\left(1-\frac1{p_i}\right)</math>. בפרט, <math>\varphi\!\left(p^e\right)=p^e-p^{e-1}</math>.
-* '''משפט גאוס:''' <math>\sum_{d\mid m}\varphi\!\left(\frac md\right)=m</math>.
+* '''משפט גאוס:''' <math>\sum_{d\mid m}\varphi(d)=m</math>.
 * '''משפט אוילר:''' אם <math>(a,m)=1</math> אז <math>a^{\varphi(m)}\equiv1\pmod m</math>. ''משפט פרמה'' הוא מקרה פרטי כאשר <math>m</math> ראשוני.
-* '''פתרון משוואות פולינומיאליות מעל {{ltr|ℤ<sub>''m''</sub>}}:''' יהי <math>m>1</math> ונרצה לפתור או לבדוק כמה פתרונות יש ל־<math>f(x)\equiv0\pmod m</math> כאשר <math>f(x)\in\mathbb Z[x]</math>.
+* '''משפט וילסון:''' <math>(p-1)!\equiv-1\pmod p</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> פתרונות.
+* '''מבחן הראשוניות של 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\}_{i=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>.
+:* {{הערה|הכללה:}} אם לא נתון ש־<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>\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>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\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>.

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

גרסה מ־15:43, 23 בינואר 2013

תוכן עניינים

סימונים

תקציר

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

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

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

מערכות משוואות

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

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

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

משוואות פל

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

תפריט הניווט

כלים אישיים

גרסאות שפה

מרחבי שם

חיפוש

עוד

צפיות

ניווט

כלים