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

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש

בקורס זה \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.
  • מבחן הראשוניות של Solovay & 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\left\{p^k,2p^k:\ p\in\mathcal P\setminus\{2\}\ \and\ k\in\mathbb N^+\right\}.

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

  • 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 ap\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: לכל 0\le k\le p-1 המספרים x_0+kp^e (מודולו p^{e+1}) הם הפתרונות למשוואה אם״ם f(x_0)\equiv0\pmod{p^{e+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.