הבדלים בין גרסאות בדף "תקציר תורת המספרים, סמסטר א תשע״ג"
מתוך Math-Wiki
מ (←סימונים) |
מ |
||
(4 גרסאות ביניים של אותו משתמש אינן מוצגות) | |||
שורה 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>p</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>. | ||
שורה 14: | שורה 14: | ||
* אם <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:\ 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>\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>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> קבוצת מחלקות השקילות. | ||
שורה 30: | שורה 30: | ||
* '''משפט אוילר:''' אם <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>. | * '''משפט וילסון:''' <math>(p-1)!\equiv-1\pmod p</math>. | ||
− | * '''מבחן הראשוניות של | + | * '''מבחן הראשוניות של Solovay & 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>x</math> שלא מקיים את התנאי הנ״ל נקרא עד לפריקות של <math>m</math>. | ||
:* אם <math>m</math> פריק אז לפחות חצי מהמספרים <math>1,2,\dots,m-1</math> הם עדים לפריקות. | :* אם <math>m</math> פריק אז לפחות חצי מהמספרים <math>1,2,\dots,m-1</math> הם עדים לפריקות. | ||
שורה 36: | שורה 36: | ||
:* לכל <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>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>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>U_n</math> ציקלית אם״ם <math>n\in\{2,4\}\cup\left\{p^k,2p^k:\ p\in\mathcal P\setminus\{2\}\ \and\ k\in\mathbb N^+\right\}</math>. |
− | + | == פונקציות אריתמטיות == | |
* <math>f:\mathbb N^+\to\mathbb C</math> נקראת פונקציה אריתמטית. בד״כ <math>\mbox{Im}(f)\subseteq\mathbb Z</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>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>. זו פעולה קומוטטיבית ואסוציאטיבית. | ||
שורה 54: | שורה 54: | ||
* <math>\varphi*\tau=d</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>\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>\alpha\in\mathbb Z[\mathrm i]</math> ו־<math>u</math> יחידה אז <math>\alpha,u\alpha</math> נקראים דומים. | ||
שורה 68: | שורה 68: | ||
* אם <math>N(\alpha)\in\mathcal P</math> אז <math>\alpha</math> ראשוני של גאוס. | * אם <math>N(\alpha)\in\mathcal P</math> אז <math>\alpha</math> ראשוני של גאוס. | ||
− | + | == פתרון משוואות דיופנטיות == | |
* '''משוואה לינארית ב־2 נעלמים:''' נרצה לפתור <math>ax+by=c</math> כאשר <math>x,y</math> משתנים והשאר קבועים. נחלק למקרים: | * '''משוואה לינארית ב־2 נעלמים:''' נרצה לפתור <math>ax+by=c</math> כאשר <math>x,y</math> משתנים והשאר קבועים. נחלק למקרים: | ||
:* <math>0\ne(a,b)\nmid c</math>: אין פתרון. | :* <math>0\ne(a,b)\nmid c</math>: אין פתרון. | ||
שורה 78: | שורה 78: | ||
:* {{הערה|הכללה:}} אם לא נתון ש־<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>\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>p\ne2</math> ו־<math>b</math> אי־זוגי. | ||
* אם קיים פתרון ל־<math>x^2\equiv a\pmod p</math> אז <math>a</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>\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>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 | + | * '''סימן לז׳נדר:''' <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 ap\right)\ne-1</math>. |
* '''משפט אוילר:''' <math>a^\frac{p-1}2\equiv\left(\frac ap\right)\pmod p</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>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>. | ||
שורה 92: | שורה 92: | ||
:* <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(\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>\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>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>-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>x^2+y^2=p</math> יש פתרון בשלמים אם״ם <math>p\equiv1\pmod4</math> (או <math>p=2</math>). | ||
שורה 102: | שורה 102: | ||
* יהי <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>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^2+y^2=z^2</math>. | ||
* פתרון יקרא פרמיטיבי אם <math>(x,y,z)=1</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>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>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>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>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>m>1</math> שאינו ריבועי. משוואת פל היא <math>x^2-my^2=1</math> כאשר <math>x,y\in\mathbb Z</math>. תמיד קיים הפתרון הטריוויאלי <math>x=1,\ y=0</math>. | ||
* לכל משוואת פל קיים פתרון לא טריוויאלי. | * לכל משוואת פל קיים פתרון לא טריוויאלי. | ||
שורה 118: | שורה 118: | ||
:* {{הערה|הערה:}} בהינתן הפתרון המינימלי נוח לחשב את שאר הפתרונות עם הנוסחה <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>\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>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>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>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>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>f'(x_0)\equiv0\pmod p</math>: לכל <math>0\le k\le p-1</math> המספרים <math>x_0+kp^e</math> (מודולו <math>p^{e+1}</math>) הם הפתרונות למשוואה אם״ם <math>f(x_0)\equiv0\pmod{p^{e+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>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>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>. |
גרסה אחרונה מ־17:23, 28 באוגוסט 2013
בקורס זה ו־. כמו כן, אלא אם צוין אחרת, , כל המשתנים והנעלמים שלמים ו־ ראשוני.
תוכן עניינים
- משפט פיאנו: קיימת קבוצה בודדה שעבורה יש פונקציה המקיימת את אקסיומות פיאנו: חח״ע, , ואם מקיימת אזי .
- מחולק לשלוש קבוצות: יחידות – , ראשוניים – ופריקים – .
- לכל ו־ קיים זוג יחיד של שארית ומנה כך ש־.
- המשפט הבסיסי של האתריתמטיקה: כל מספר ב־ ניתן לפירוק יחיד (עד כדי סדר ההכפלה) של גורמים ראשוניים.
- למת אוקלידס: אם אז .
- נסמן אם .
- נניח ש־ ו/או שונים מ־0. אזי קיים יחיד (הנקרא מחלק משותף מקסימלי של ומסומן ) עבורו ואם כך ש־ אזי .
- אם אזי .
- .
- .
- אם זרים ו־ אזי .
- אם וה־ שונים זה מזה אזי .
- יקרא חופשי מריבועים אם .
- אלגוריתם אוקלידס: נניח ונרצה לחשב כאשר . אם שארית החלוקה של ב־ אזי . נמשיך כך עד שנקבל . ניתן להעזר באלגוריתם גם כדי לפתור את : נסמן ולכן בתהליך החישוב של עם האלגוריתם נקבל כאשר . לפיכך:
- נאמר ש־ חופפים מודולו (ונסמן ) אם . מגדיר יחס שקילות כאשר מחלקת השקילות של ו־ קבוצת מחלקות השקילות.
- אם ו־ אז .
- יהי . אם״ם הפיך. ניתן למצוא את ההופכי ל־ ע״י פתירת , ואז .
- .
- פונקציית אוילר היא עבורה .
- פונקציית אוילר כפלית אריתמטית.
- מערכת מלאה מודולו m היא קבוצה עבורה . קיים יחיד כנ״ל לכל . באופן שקול, המערכת מלאה מודולו אם .
- אם מלאה מודולו , ו־ שלם אזי מלאה מודולו .
- מערכת מצומצמת מודולו m היא קבוצה כך ש־. באופן שקול, .
- אם מצומצמת מודולו ו־ אז מצומצמת מודולו .
- אם אזי . בפרט, .
- משפט גאוס: .
- משפט אוילר: אם אז . משפט פרמה הוא מקרה פרטי כאשר ראשוני.
- משפט וילסון: .
- מבחן הראשוניות של Solovay & Strassen: ראשוני אם״ם או .
- אם פריק אז שלא מקיים את התנאי הנ״ל נקרא עד לפריקות של .
- אם פריק אז לפחות חצי מהמספרים הם עדים לפריקות.
- משפט גאוס: חבורה ציקלית, כלומר קיים כך ש־.
- לכל אותו יחיד מודולו ולכן נקרא "הלוגריתם מודולו של לפי " ומסומן .
- כל כזה נקרא "שורש פרימיטיבי". יש כאלה.
- הכללה: ציקלית אם״ם .
פונקציות אריתמטיות
- נקראת פונקציה אריתמטית. בד״כ .
- קונבולוציית דיריכלה בין שתי פונקציות אריתמטיות מוגדרת ע״י . זו פעולה קומוטטיבית ואסוציאטיבית.
- נסמן . היא פונקציית היחידה ביחס לקונבולוציה, כלומר .
- אריתמטית תקרא כפלית אם וכפלית אריתמטית אם .
- אם כפליות אריתמטיות אז כך גם .
- פונקציית הממוצע האריתמטי של מוגדרת ע״י כאשר .
- אם אז נקראת הפיכה (ביחס לקונבולוציית דיריכלה) ונסמן .
- הפיכה אם״ם .
- אם הפיכה וכפלית אריתמטית אז כפלית אריתמטית.
- פונקציית מוביוס היא ומקיימת .
- .
- מגדירים .
- נגדיר . מקרה שימושי הוא ואז כאשר .
- .
חוג השלמים של גאוס
האיברים ב־ נקראים שלמים של גאוס. איברי היחידה (כלומר עבורם ) הם .
- אם ו־ יחידה אז נקראים דומים.
- נגדיר ע״י . היא כפלית () ו־ יחידה אם״ם .
- ראשוני של גאוס הוא שלם של גאוס שאינו יחידה ואם אז או יחידות.
- אם כך ש־ אז יש עבורם כך ש־.
- משפט גאוס: ב־ קיים פירוק יחיד לגורמים ראשוניים של גאוס.
- הראשוניים של גאוס מתחלקים לסוגים הבאים:
- . הוא "קשור" ל־2 ע״י .
- לכל יש פתרון ל־. המספרים הם ראשוניים לא דומים של גאוס.
- כל הוא גם ראשוני של גאוס.
- כל ראשוני של גאוס מחלק ראשוני טבעי כלשהו.
- אם אז ראשוני של גאוס.
פתרון משוואות דיופנטיות
- משוואה לינארית ב־2 נעלמים: נרצה לפתור כאשר משתנים והשאר קבועים. נחלק למקרים:
- : אין פתרון.
- : ניתן לפתור ע״י אלגוריתם אוקלידס (כמפורט בהמשך הסעיף). הפתרון הכללי הוא לכל .
- : נחלק את אגפי המשוואה ב־ ונקבל משוואה חדשה מהמקרה הקודם.
- אם בפרט אז ניתן לפתור גם באמצעות אלגוריתם אוקלידס.
- משפט השאריות הסיני: נניח ש־ ונתונה . למערכת קיים פתרון יחיד מודולו .
- אם אז . ה־־ים מקיימים כאשר .
- הכללה: אם לא נתון ש־ אז יש פתרון אם״ם .
משוואות ריבועיות
בפרק זה ו־ אי־זוגי.
- אם קיים פתרון ל־ אז יקרא שארית ריבועית (ש״ר).
- יש שאריות ריבועיות ב־ והן .
- אם אז .
- סימן לז׳נדר: . לפיכך שארית ריבועית אם״ם .
- משפט אוילר: .
- למת גאוס: נסמן ונגדיר כאשר . אזי .
- סימן יעקובי: יהי . מגדירים .
- אם אז ל־ אין פתרון. ההפך לא תמיד נכון.
- תכונות של סימני לז׳נדר ויעקובי:
- אז .
- ו־.
- , ו־.
- משפט ההדדיות הריבועית: אם גם אי־זוגי אז .
- למת לגרנז׳: שארית ריבועית מודולו אם״ם . השורש מודולו הוא .
- משפט פרמה: ל־ יש פתרון בשלמים אם״ם (או ).
- אם לאו דווקא ראשוני אבל אז עדיין אין פתרון בשלמים.
- עקרון דיריכלה: נרצה לפתור את המשוואה. נסמן ונניח כך ש־. נסמן ו־ והם פותרים את .
- משפט אוילר: ל־ יש פתרון בשלמים אם״ם .
- משפט דיריכלה: לכל ו־ זר לו יש אינסוף ראשוניים עבורם . בפרט יש אינסוף ראשוניים עבורם .
- שארית ריבועית מודולו לכל אם״ם .
- יהי ונרצה לפתור כשנתון ש־ שארית ריבועית: . למקרה יש פתרון אך הוא מורכב ולא נביאו.
משוואות פיתגורס
נרצה למצוא את הפתרונות השלמים של .
- פתרון יקרא פרמיטיבי אם .
- הפתרונות החיוביים (כלומר ) הפרמיטבים הם מהצורות הבאות: יהיו זרים. אם הם אי־זוגיים אז ואם אחד מהם זוגי אז .
עקומות רציונליות
- יהי פולינום בשני משתנים עם מקדמים רציונלים (כלומר ) שאינה פריקה (כלומר אין לא קבועות כך ש־). העקומה תקרא רציונלית אם קיימת לה פרמטריזציה (למעט, אולי, בכמה נקודות מבודדות) כאשר הם חלוקות של פולינומים במשתנה אחד עם מקדמים רציונלים.
- נניח ש־ לא פריקה ו־. אם ל־ יש פתרון ב־ אז רציונלית.
- משפט לג׳נדר: נרצה לדעת אם ל־ יש פתרון רציונלי כאשר . ניתן להניח בה״כ ש־ שלמים, זרים בזוגות וחופשיים מריבועים. קיים פתרון רציונלי אם״ם ש״ר מודולו , ש״ר מודולו ו־ ש״ר מודולו .
משוואות פל
יהי שאינו ריבועי. משוואת פל היא כאשר . תמיד קיים הפתרון הטריוויאלי .
- לכל משוואת פל קיים פתרון לא טריוויאלי.
- יהי הפתרון החיובי המינימלי (נקרא "הפתרון הפונדמנטלי"), כלומר כך ש־ הוא ה־ המינימלי הגדול מ־1 שקיים לו הפותר את המשוואה. אזי כל הפתרונות הם עבור .
- הערה: בהינתן הפתרון המינימלי נוח לחשב את שאר הפתרונות עם הנוסחה .
משוואות פולינומיאליות
יהי ונרצה לפתור או לבדוק כמה פתרונות יש ל־ כאשר .
- משוואה לינארית: . קיים פתרון אם״ם . אם פתרון פרטי של אז כל הפתרונות הם כאשר , ויש פתרונות.
- מגדירים . זו פונקציה כפלית אריתמטית.
- שיטת הנזל: יהי פתרון של כאשר ונרצה לפתור . נחלק למקרים לפי הנגזרת בנקודה זו:
- : לכל המספרים (מודולו ) הם הפתרונות למשוואה אם״ם .
- : לכן קיים ו־ עבור הוא הפתרון היחיד.
- משפט בסונט: אם שורש של אז קיימת כך ש־ ו־.
- חילוק פולינומים: אם ו־ פולינום מתוקן אז קיימים עבורם ו־.
- משפט לגראנז׳: ל־ יש לכל היותר שורשים. בנוסף, אם כך של־ יש יותר מ־ שורשים אז אז כל המקדמים ב־ מתחלקים ב־.
- הערה: המשפט לא מתקיים ל־ פריק.
- .
- ל־ יש שורשים שונים. בפרט, אם אז ל־ יש שורשים שונים אם״ם .