לדלג לתוכן
שינוי מצב סרגל צד
Math-Wiki
חיפוש
יצירת חשבון
כלים אישיים
יצירת חשבון
כניסה לחשבון
דפים לעורכים שלא נכנסו לחשבון
מידע נוסף
שיחה
תרומות
ניווט
עמוד ראשי
שינויים אחרונים
העלאת קובץ
כלים
דפים המקושרים לכאן
שינויים בדפים המקושרים
דפים מיוחדים
מידע על הדף
עריכת הדף "
תקציר תורת המספרים, סמסטר א תשע״ג
" (פסקה)
דף
שיחה
עברית
קריאה
עריכה
גרסאות קודמות
עוד
קריאה
עריכה
גרסאות קודמות
אזהרה:
אינכם מחוברים לחשבון. כתובת ה־IP שלכם תוצג בפומבי אם תבצעו עריכות כלשהן. אם
תיכנסו לחשבון
או
תיצרו חשבון
, העריכות שלכם תיוחסנה לשם המשתמש שלכם ותקבלו גם יתרונות אחרים.
בדיקת אנטי־ספאם.
אין
למלא שדה זה!
== פתרון משוואות דיופנטיות == * '''משוואה לינארית ב־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 ap\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>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>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>.
תקציר:
לתשומת לבך: תורמים אחרים עשויים לערוך או אף להסיר את תרומתך ל־Math-Wiki. אם אינך רוצה שעבודתך תהיה זמינה לעריכה על־ידי אחרים, אין לפרסם אותה פה.
כמו־כן, שמירת העריכה משמעה הבטחה שכתבת את הטקסט הזה בעצמך, או העתקת אותו ממקור שאינו מוגן בזכויות יוצרים (אפשר לעיין בדף
Math-Wiki:זכויות יוצרים
לפרטים נוספים).
אין לעשות שימוש בחומר המוגן בזכויות יוצרים ללא רשות!
ביטול
עזרה בעריכה
(נפתח בחלון חדש)