הבדלים בין גרסאות בדף "תקציר תורת המספרים, סמסטר א תשע״ג"
מתוך Math-Wiki
שורה 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 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>\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>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>\mathbb Z\setminus\{0,\pm1\}</math> ניתן לפירוק יחיד (עד כדי סדר ההכפלה) של גורמים ראשוניים. | ||
− | * '''למת אוקלידס:''' | + | * '''למת אוקלידס:''' אם <math>p\mid ab</math> אז <math>p\mid a\ \or\ p\mid b</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</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\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\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>a,b</math> זרים ו־<math>a\mid bc</math> אזי <math>a\mid c</math>. | ||
− | * אם <math>\forall i: | + | * אם <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>}} | * '''אלגוריתם אוקלידס:''' נניח <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,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>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>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>\varphi:\mathbb N^+\to\mathbb N^+</math> עבורה <math>\varphi(1):=1,\ \varphi(m):=|U_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> | + | * '''מערכת מלאה מודולו ''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>. | * אם <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>\{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: | + | * אם <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 | + | * '''משפט גאוס:''' <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> ראשוני. | * '''משפט אוילר:''' אם <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\}_{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
תוכן עניינים
סימונים
בקורס זה ו־. כמו כן, אלא אם צוין אחרת, , כל המשתנים והנעלמים שלמים ו־ ראשוני.
תקציר
- משפט פיאנו: קיימת קבוצה בודדה שעבורה יש פונקציה המקיימת את אקסיומות פיאנו: חח״ע, , ואם מקיימת אזי .
- מחולק לשלוש קבוצות: יחידות – , ראשוניים – ופריקים – .
- לכל ו־ קיים זוג יחיד של שארית ומנה כך ש־.
- המשפט הבסיסי של האתריתמטיקה: כל מספר ב־ ניתן לפירוק יחיד (עד כדי סדר ההכפלה) של גורמים ראשוניים.
- למת אוקלידס: אם אז .
- נסמן אם .
- נניח ש־ ו/או שונים מ־0. אזי קיים יחיד (הנקרא מחלק משותף מקסימלי של ומסומן ) עבורו ואם כך ש־ אזי .
- אם אזי .
- .
- .
- אם זרים ו־ אזי .
- אם וה־ שונים זה מזה אזי .
- יקרא חופשי מראשוניים אם .
- אלגוריתם אוקלידס: נניח ונרצה לחשב כאשר . אם שארית החלוקה של ב־ אזי . נמשיך כך עד שנקבל . ניתן להעזר באלגוריתם גם כדי לפתור את : נסמן ולכן בתהליך החישוב של עם האלגוריתם נקבל כאשר . לפיכך:
- נאמר ש־ חופפים מודולו (ונסמן ) אם . מגדיר יחס שקילות כאשר מחלקת השקילות של ו־ קבוצת מחלקות השקילות.
- אם ו־ אז .
- יהי . אם״ם הפיך. ניתן למצוא את ההופכי ל־ ע״י פתירת , ואז .
- .
- פונקציית אוילר היא עבורה .
- פונקציית אוילר כפלית אריתמטית.
- מערכת מלאה מודולו m היא קבוצה עבורה . קיים יחיד כנ״ל לכל . באופן שקול, המערכת מלאה מודולו אם .
- אם מלאה מודולו , ו־ שלם אזי מלאה מודולו .
- מערכת מצומצמת מודולו m היא קבוצה כך ש־. באופן שקול, .
- אם מצומצמת מודולו ו־ אז מצומצמת מודולו .
- אם אזי . בפרט, .
- משפט גאוס: .
- משפט אוילר: אם אז . משפט פרמה הוא מקרה פרטי כאשר ראשוני.
- משפט וילסון: .
- מבחן הראשוניות של Salovay & Strassen: ראשוני אם״ם או .
- אם פריק אז שלא מקיים את התנאי הנ״ל נקרא עד לפריקות של .
- אם פריק אז לפחות חצי מהמספרים הם עדים לפריקות.
- משפט גאוס: חבורה ציקלית, כלומר קיים כך ש־.
- לכל אותו יחיד מודולו ולכן נקרא "הלוגריתם מודולו של לפי " ומסומן .
- כל כזה נקרא "שורש פרימיטיבי". יש כאלה.
- הכללה: ציקלית אם״ם .
פונקציות אריתמטיות
- נקראת פונקציה אריתמטית. בד״כ .
- קונבולוציית דיריכלה בין שתי פונקציות אריתמטיות מוגדרת ע״י . זו פעולה קומוטטיבית ואסוציאטיבית.
- נסמן . היא פונקציית היחידה ביחס לקונבולוציה, כלומר .
- אריתמטית תקרא כפלית אם וכפלית אריתמטית אם .
- אם כפליות אריתמטיות אז כך גם .
- פונקציית הממוצע האריתמטי של מוגדרת ע״י כאשר .
- אם אז נקראת הפיכה (ביחס לקונבולוציית דיריכלה) ונסמן .
- הפיכה אם״ם .
- אם הפיכה וכפלית אריתמטית אז כפלית אריתמטית.
- פונקציית מוביוס היא ומקיימת .
- .
- מגדירים .
- נגדיר . מקרה שימושי הוא ואז כאשר .
- .
חוג השלמים של גאוס
האיברים ב־ נקראים שלמים של גאוס. איברי היחידה (כלומר עבורם ) הם .
- אם ו־ יחידה אז נקראים דומים.
- נגדיר ע״י . היא כפלית () ו־ יחידה אם״ם .
- ראשוני של גאוס הוא שלם של גאוס שאינו יחידה ואם אז או יחידות.
- אם כך ש־ אז יש עבורם כך ש־.
- משפט גאוס: ב־ קיים פירוק יחיד לגורמים ראשוניים של גאוס.
- הראשוניים של גאוס מתחלקים לסוגים הבאים:
- . הוא "קשור" ל־2 ע״י .
- לכל יש פתרון ל־. המספרים הם ראשוניים לא דומים של גאוס.
- כל הוא גם ראשוני של גאוס.
- כל ראשוני של גאוס מחלק ראשוני טבעי כלשהו.
- אם אז ראשוני של גאוס.
פתרון משוואות דיופנטיות
- משוואה לינארית ב־2 נעלמים: נרצה לפתור כאשר משתנים והשאר קבועים. נחלק למקרים:
- : אין פתרון.
- : ניתן לפתור ע״י אלגוריתם אוקלידס (כמפורט בהמשך הסעיף). הפתרון הכללי הוא לכל .
- : נחלק את אגפי המשוואה ב־ ונקבל משוואה חדשה מהמקרה הקודם.
- אם בפרט אז ניתן לפתור גם באמצעות אלגוריתם אוקלידס.
מערכות משוואות
- משפט השאריות הסיני: נניח ש־ ונתונה . למערכת קיים פתרון יחיד מודולו .
- אם אז . ה־־ים מקיימים כאשר .
- הכללה: אם לא נתון ש־ אז יש פתרון אם״ם .
משוואות ריבועיות
בפרק זה ו־ אי־זוגי.
- אם קיים פתרון ל־ אז יקרא שארית ריבועית (ש״ר).
- יש שאריות ריבועיות ב־ והן .
- אם אז .
- סימן לז׳נדר: . לפיכך שארית ריבועית אם״ם .
- משפט אוילר: .
- למת גאוס: נסמן ונגדיר כאשר . אזי .
- סימן יעקובי: יהי . מגדירים .
- אם אז ל־ אין פתרון. ההפך לא תמיד נכון.
- תכונות של סימני לז׳נדר ויעקובי:
- אז .
- ו־.
- , ו־.
- אם גם אי־זוגי אז .
- למת לגרנז׳: שארית ריבועית מודולו אם״ם . השורש מודולו הוא .
- משפט פרמה: ל־ יש פתרון בשלמים אם״ם (או ).
- אם לאו דווקא ראשוני אבל אז עדיין אין פתרון בשלמים.
- עקרון דיריכלה: נרצה לפתור את המשוואה. נסמן ונניח כך ש־. נסמן ו־ והם פותרים את .
- משפט אוילר: ל־ יש פתרון בשלמים אם״ם .
- משפט דיריכלה: לכל ו־ זר לו יש אינסוף ראשוניים עבורם . בפרט יש אינסוף ראשוניים עבורם .
- שארית ריבועית מודולו לכל אם״ם .
- יהי ונרצה לפתור כשנתון ש־ שארית ריבועית: . למקרה יש פתרון אך הוא מורכב ולא נביאו.
משוואות פיתגורס
נרצה למצוא את הפתרונות השלמים של .
- פתרון יקרא פרמיטיבי אם .
- הפתרונות החיוביים (כלומר ) הפרמיטבים הם מהצורות הבאות: יהיו זרים. אם הם אי־זוגיים אז ואם אחד מהם זוגי אז .
עקומות רציונליות
- יהי פולינום בשני משתנים עם מקדמים רציונלים (כלומר ) שאינה פריקה (כלומר אין לא קבועות כך ש־). העקומה תקרא רציונלית אם קיימת לה פרמטריזציה (למעט, אולי, בכמה נקודות מבודדות) כאשר הם חלוקות של פולינומים במשתנה אחד עם מקדמים רציונלים.
- נניח ש־ לא פריקה ו־. אם ל־ יש פתרון ב־ אז רציונלית.
- משפט לג׳נדר: נרצה לדעת אם ל־ יש פתרון רציונלי כאשר . ניתן להניח בה״כ ש־ שלמים, זרים בזוגות וחופשיים מריבועים. קיים םתרון רציונלי אם״ם ש״ר מודולו , ש״ר מודולו ו־ ש״ר מודולו .
משוואות פל
יהי שאינו ריבועי. משוואת פל היא כאשר . תמיד קיים הפתרון הטריוויאלי .
- לכל משוואת פל קיים פתרון לא טריוויאלי.
- יהי הפתרון החיובי המינימלי (נקרא "הפתרון הפונדמנטלי"), כלומר כך ש־ הוא ה־ המינימלי הגדול מ־1 שקיים לו הפותר את המשוואה. אזי כל הפתרונות הם עבור .
- הערה: בהנתן הפתרון המינימלי נוח לחשב את שאר הפתרונות עם הנוסחה .
משוואות פולינומיאליות
יהי ונרצה לפתור או לבדוק כמה פתרונות יש ל־ כאשר .
- משוואה לינארית: . קיים פתרון אם״ם . אם פתרון פרטי של אז כל הפתרונות הם כאשר , ויש פתרונות.
- מגדירים . זו פונקציה כפלית אריתמטית.
- שיטת הנזל: יהי פתרון של כאשר ונרצה לפתור . נחלק למקרים לפי הנגזרת בנקודה זו:
- : הפתרונות היחידים (מודולו ) למשוואה הם עבור .
- : לכן קיים ו־ עבור הוא הפתרון היחיד.
- משפט בסונט: אם שורש של אז קיימת כך ש־ ו־.
- חילוק פולינומים: אם ו־ פולינום מתוקן אז קיימים עבורם ו־.
- משפט לגראנז׳: ל־ יש לכל היותר שורשים. בנוסף, אם כך של־ יש יותר מ־ שורשים אז אז כל המקדמים ב־ מתחלקים ב־.
- הערה: המשפט לא מתקיים ל־ פריק.
- .
- ל־ יש שורשים שונים. בפרט, אם אז ל־ יש שורשים שונים אם״ם .