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

בקורס זה [math]\displaystyle{ \mathbb N=\{0,1,2,\dots\} }[/math] ו־[math]\displaystyle{ \mathbb N^+=\{1,2,\dots\} }[/math]. כמו כן, אלא אם צוין אחרת, [math]\displaystyle{ A^+:=A\cap\mathbb N^+ }[/math] וכל המשתנים והנעלמים שלמים.

משפט פיאנו: קיימת קבוצה בודדה [math]\displaystyle{ \mathbb N }[/math] שעבורה יש פונקציה [math]\displaystyle{ S:\mathbb N\to\mathbb N }[/math] המקיימת את אקסיומות פיאנו: [math]\displaystyle{ S }[/math] חח״ע, [math]\displaystyle{ 0\not\in\mbox{Im}(S) }[/math], [math]\displaystyle{ 0\in\mathbb N }[/math] ואם [math]\displaystyle{ K\subseteq\mathbb N }[/math] מקיימת [math]\displaystyle{ 0\in K\ \and\ (x\in K\iff S(x)\in K) }[/math] אזי [math]\displaystyle{ K=\mathbb N }[/math].
[math]\displaystyle{ \mathbb Z\setminus\{0\} }[/math] מחולק לשלוש קבוצות: יחידות – [math]\displaystyle{ U:=\{\pm1\} }[/math], ראשוניים – [math]\displaystyle{ \mathcal P:=\{p\in\mathbb Z\setminus U:\ \forall ab=p:\ a\in U\ \or\ b\in U\} }[/math] ופריקים – [math]\displaystyle{ \mathbb Z\setminus\{0\}\setminus U\setminus\mathcal P }[/math].
לכל [math]\displaystyle{ a\in\mathbb N^+ }[/math] ו־[math]\displaystyle{ b }[/math] קיים זוג יחיד של שארית [math]\displaystyle{ r }[/math] ומנה [math]\displaystyle{ q }[/math] כך ש־[math]\displaystyle{ b=qa+r,\ 0\le r\lt a }[/math].
המשפט הבסיסי של האתריתמטיקה: כל מספר ב־[math]\displaystyle{ \mathbb Z\setminus\{0,\pm1\} }[/math] ניתן לפירוק יחיד (עד כדי סדר ההכפלה) של גורמים ראשוניים.
למת אוקלידס: יהי [math]\displaystyle{ p\in\mathcal P }[/math]. אם [math]\displaystyle{ p\mid ab }[/math] אז [math]\displaystyle{ p\mid a\ \or\ p\mid b }[/math].
יהיו [math]\displaystyle{ p\in\mathcal P^+,\ a,m\in\mathbb N^+ }[/math]. נסמן [math]\displaystyle{ p^m\mid\!\mid a }[/math] אם [math]\displaystyle{ p^m\mid a\ \and\ p^{m+1}\nmid a }[/math].
נניח ש־[math]\displaystyle{ a }[/math] ו/או [math]\displaystyle{ b }[/math] שונים מ־0. אזי קיים [math]\displaystyle{ d\in\mathbb N^+ }[/math] יחיד (הנקרא מחלק משותף מקסימלי של [math]\displaystyle{ a,b }[/math] ומסומן [math]\displaystyle{ \gcd(a,b)=(a,b) }[/math]) עבורו [math]\displaystyle{ d\mid a,b }[/math] ואם [math]\displaystyle{ d'\in\mathbb Z }[/math] כך ש־[math]\displaystyle{ d'\mid a,b }[/math] אזי [math]\displaystyle{ d'\mid d }[/math].
אם [math]\displaystyle{ a\mid b,c }[/math] אזי [math]\displaystyle{ \forall x,y\in\mathbb Z:\ a\mid xb+yc }[/math].
[math]\displaystyle{ (a,b)=\min\{xa+yb:\ x,y\in\mathbb Z\}^+ }[/math].
[math]\displaystyle{ a\mathbb Z+b\mathbb Z=(a,b)\mathbb Z }[/math].
אם [math]\displaystyle{ a,b }[/math] זרים ו־[math]\displaystyle{ a\mid bc }[/math] אזי [math]\displaystyle{ a\mid c }[/math].
אם [math]\displaystyle{ \forall i:\ p_i\in\mathcal P\ \and\ k_i,m_i\in\mathbb N }[/math] אזי [math]\displaystyle{ \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]\displaystyle{ b\ne0 }[/math] ונרצה לחשב [math]\displaystyle{ (a,b) }[/math] כאשר [math]\displaystyle{ a\gt b }[/math]. אם [math]\displaystyle{ r }[/math] שארית החלוקה של [math]\displaystyle{ a }[/math] ב־[math]\displaystyle{ b }[/math] אזי [math]\displaystyle{ (a,b)=(b,r) }[/math]. נמשיך כך עד שנקבל [math]\displaystyle{ (x,0)=x }[/math]. ניתן להעזר באלגוריתם גם כדי לפתור את [math]\displaystyle{ ax+by=(a,b) }[/math]: נסמן [math]\displaystyle{ r_{-1}=a, r_0=b }[/math] ולכן בתהליך החישוב של [math]\displaystyle{ (a,b) }[/math] עם האלגוריתם נקבל [math]\displaystyle{ \forall0\le i\le k:\ r_{i-1}=r_iq_{i+1}+r_{i+1} }[/math] כאשר [math]\displaystyle{ r_{k+1}=(a,b) }[/math]. לפיכך:
[math]\displaystyle{ \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]
משוואה דיאופנטית ב־2 משתנים: נרצה לפתור [math]\displaystyle{ ax+by=c }[/math] כאשר [math]\displaystyle{ x,y }[/math] משתנים והשאר קבועים. נחלק למקרים:

[math]\displaystyle{ 0\ne(a,b)\nmid c }[/math]: אין פתרון.
[math]\displaystyle{ (a,b)=1 }[/math]: ניתן לפתור [math]\displaystyle{ ax_0+by_0=1 }[/math] ע״י אלגוריתם אוקלידס (כמפורט בהמשך הסעיף). הפתרון הכללי הוא [math]\displaystyle{ x=cx_0+bk, y=cy_0-ak }[/math] לכל [math]\displaystyle{ k }[/math].
[math]\displaystyle{ 1\ne(a,b)\mid c }[/math]: נחלק את אגפי המשוואה ב־[math]\displaystyle{ (a,b) }[/math] ונקבל משוואה חדשה מהמקרה הקודם.

אם בפרט [math]\displaystyle{ (a,b)=c }[/math] אז ניתן לפתור גם באמצעות אלגוריתם אוקלידס.

נאמר ש־[math]\displaystyle{ a,b }[/math] חופפים מודולו [math]\displaystyle{ m\gt 1 }[/math] (ונסמן [math]\displaystyle{ a\equiv b\pmod m }[/math]) אם [math]\displaystyle{ m\mid a-b }[/math]. [math]\displaystyle{ \equiv }[/math] מגדיר יחס שקילות כאשר [math]\displaystyle{ \bar a=[a]=a+m\mathbb Z }[/math] מחלקת השקילות של [math]\displaystyle{ a }[/math] ו־[math]\displaystyle{ \mathbb Z_m }[/math] קבוצת מחלקות השקילות.
אם [math]\displaystyle{ m\gt 1,\ k\ne0 }[/math] ו־[math]\displaystyle{ ka\equiv kb\pmod m }[/math] אז [math]\displaystyle{ a\equiv b\pmod{m/(k,m)} }[/math].
יהי [math]\displaystyle{ \bar a\in\mathbb Z_m }[/math]. [math]\displaystyle{ (a,m)=1 }[/math] אם״ם [math]\displaystyle{ \bar a }[/math] הפיך. ניתן למצוא את ההופכי ל־[math]\displaystyle{ \bar a }[/math] ע״י פתירת [math]\displaystyle{ ax+my=1 }[/math], ואז [math]\displaystyle{ \bar a^{-1}=\bar x }[/math].
[math]\displaystyle{ U_m:=\{\bar a\in\mathbb Z_m:\ (a,m)=1\}\subset\mathbb Z_m }[/math].
פונקציית אוילר היא [math]\displaystyle{ \varphi:\mathbb N^+\to\mathbb N^+ }[/math] עבורה [math]\displaystyle{ \varphi(1):=1,\ \varphi(m):=|U_m| }[/math].
משפט אוילר: אם [math]\displaystyle{ (m,n)=1 }[/math] אז [math]\displaystyle{ \varphi(mn)=\varphi(m)\varphi(n) }[/math].
מערכת מלאה מודולו m היא קבוצה [math]\displaystyle{ \{a_i\}_{i=1}^m\subseteq\mathbb Z }[/math] עבורה [math]\displaystyle{ \forall a:\ \exists i:\ a\equiv a_i\pmod m }[/math]. קיים [math]\displaystyle{ i }[/math] כנ״ל יחיד לכל [math]\displaystyle{ a }[/math]. באופן שקול, המערכת מלאה מודולו [math]\displaystyle{ m }[/math] אם [math]\displaystyle{ \mathbb Z_m=\{\bar a_i\}_{i=1}^m }[/math].
אם [math]\displaystyle{ \{a_i\}_{i=1}^m }[/math] מלאה מודולו [math]\displaystyle{ m }[/math], [math]\displaystyle{ (\alpha,m)=1 }[/math] ו־[math]\displaystyle{ k }[/math] שלם אזי [math]\displaystyle{ \{\alpha a_i+k\}_{i=1}^m }[/math] מלאה מודולו [math]\displaystyle{ m }[/math].
מערכת מצומצמת מודולו m היא קבוצה [math]\displaystyle{ \{a_i\}_{i=1}^{\varphi(m)} }[/math] כך ש־[math]\displaystyle{ \forall\bar a\in U_m:\ \exists i:\ a\equiv a_i\pmod m }[/math].
אם [math]\displaystyle{ \{a_i\}_{i=1}^{\varphi(m)} }[/math] מצומצמת מודולו [math]\displaystyle{ m }[/math] ו־[math]\displaystyle{ (\alpha,m)=1 }[/math] אז [math]\displaystyle{ \{\alpha a_i\}_{i=1}^{\varphi(m)} }[/math] מצומצמת מודולו [math]\displaystyle{ m }[/math].