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

אור שחף ב־17:23, 28 באוגוסט 2013

2013-08-28T17:23:19Z

→ הגרסה הקודמת		גרסה מ־17:23, 28 באוגוסט 2013
שורה 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>.
	* '''מבחן הראשוניות של ~~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>.		* '''מבחן הראשוניות של 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> הם עדים לפריקות.

אור שחף ב־11:26, 24 בינואר 2013

2013-01-24T11:26:14Z

→ הגרסה הקודמת		גרסה מ־11:26, 24 בינואר 2013
שורה 123:		שורה 123:
	* מגדירים <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>p~~^{e+~~1}</math>~~) למשוואה הם~~ <math>x_0+kp^e</math> ~~עבור~~ <math>0\~~le k~~\le p-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>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>.

אור שחף ב־06:06, 24 בינואר 2013

2013-01-24T06:06:05Z

→ הגרסה הקודמת		גרסה מ־06:06, 24 בינואר 2013
שורה 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>\nexists p\in\mathcal P:\ p^2\mid 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> קבוצת מחלקות השקילות.

אור שחף: /* משוואות ריבועיות */

2013-01-23T21:34:04Z

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

→ הגרסה הקודמת		גרסה מ־21:34, 23 בינואר 2013
שורה 83:		שורה 83:
	* יש <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 am\right)\ne-1</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>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>.

אור שחף ב־20:44, 23 בינואר 2013

2013-01-23T20:44:37Z

אור שחף: /* סימונים */

2013-01-23T16:32:22Z

סימונים

→ הגרסה הקודמת		גרסה מ־16:32, 23 בינואר 2013
שורה 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> ראשוני.

	== תקציר ==		== תקציר ==

אור שחף: /* פתרון משוואות דיופנטיות */

2013-01-23T16:32:00Z

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

→ הגרסה הקודמת		גרסה מ־16:32, 23 בינואר 2013
שורה 111:		שורה 111:
	* יהי <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>.

	===== משוואות פל =====		===== משוואות פל =====
שורה 117:		שורה 117:
	* לכל משוואת פל קיים פתרון לא טריוויאלי.		* לכל משוואת פל קיים פתרון לא טריוויאלי.
	* יהי <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>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>\left(x_0+\sqrt my_0\right)\left(x+\sqrt my\right)=(x_0x+my_0y)+\sqrt m(y_0x+x_0y)</math>.

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

אור שחף: /* פתרון משוואות דיופנטיות */

2013-01-23T15:46:02Z

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

→ הגרסה הקודמת		גרסה מ־15:46, 23 בינואר 2013
שורה 75:		שורה 75:
	:* <math>1\ne(a,b)\mid c</math>: נחלק את אגפי המשוואה ב־<math>(a,b)</math> ונקבל משוואה חדשה מהמקרה הקודם.		:* <math>1\ne(a,b)\mid c</math>: נחלק את אגפי המשוואה ב־<math>(a,b)</math> ונקבל משוואה חדשה מהמקרה הקודם.
	::* אם בפרט <math>(a,b)=c</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 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 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>.

אור שחף: /* מערכות משוואות */

2013-01-23T15:45:38Z

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

→ הגרסה הקודמת		גרסה מ־15:45, 23 בינואר 2013
שורה 76:		שורה 76:
	::* אם בפרט <math>(a,b)=c</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 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 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>.

אור שחף ב־15:43, 23 בינואר 2013

2013-01-23T15:43:05Z

הצגת שינויים

→ הגרסה הקודמת		גרסה מ־20:44, 23 בינואר 2013
שורה 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>.
שורה 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> יקרא ''שארית ריבועית'' (ש״ר).
שורה 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> פתרונות.