גליון 1 — אלגברה מודרנית ח'

תרגיל 1

תרגיל (1)

הוכיחו כי קיימים $\infty$ מספרים ראשוניים מהצורה $4n+3$ (כאשר $n=0,1,2,\dots$ )

הוכחה:
נניח בשלילה כי קיים מספר סופי של ראשוניים מהצורה $4n+3$ . אזי, הקבוצה $A=\left\{ p=4n+3 \mid n \in \mathbb{Z},\;\R{\text{ ראשוני}}p \right\}$ סופית. כלומר, קיים $L \in \mathbb{Z}$ כך ש- $|A|=L$ . נסמן את האיברים בקבוצה: $p_{1},p_{2},\dots,p_{L}$ .
נגדיר $n=4p_{1}p_{2}\cdots p_{L}-1$ . מכיוון ש- $n> \max A$ מתקיים כי $n$ אינו ראשוני. המספר אינו זוגי שכן $4p_{1}p_{2}\cdots p_{L}$ זוגי. לכן, $2 \nmid n$ .
לכן, כל גורם שלו הוא אי זוגי, או במילים אחרות, כל גורם שלו הוא מהצורה $4k+1$ או $4k+3$ .
נניח כעת כי כל הגורמים של $n$ הם מהצורה $4n+1$ . נטען טענת עזר: כל מספר המורכב רק מגורמים של $4n+1$ יהיה בתצורת $4n+1$ ונוכיח באינדוקציה.
בסיס: עבור $k=1$ מתקיים $(4n+1)^1=4n+1$ שהינו מספר מהתצורה $4n+1$ .
צעד: נניח כי עבור $k\geq 1$ מתקיים ש- $(4n+1)^k$ הינו מספר מהתצורה $4n+1$ ונראה כי זה מתקיים עבור $k+1$ .
נסמן: $(4n+1)^k=4m+1$ ואז:

(4n+1)^{k+1}\!=\!(4n+1)^k(4n+1)\!=\!(4m+1)(4n+1)\!=4^2nm+4n+4m+1=4(4nm+n+m)+1

לכן, מכיוון ש- $n$ הוא במבנה $4n+3$ קיים לו גורם ראשוני מהתצורה $4n+3$ . לכן, קיים $1\leq i\leq L$ כך ש- $p_{i} \mid 4p_{1}p_{2}\cdots p_{L}-1$ .
בנוסף, נשים לב כי $p_{i}\mid 4p_{1}p_{2}\cdots p_{L}$ ולכן, לפי לינאריות החלוקה, $p_{i}\mid (4p_{1}p_{2}\cdots p_{L}-1-1(4p_{2}p_{2}\cdots p_{L}))=1$ בסתירה לכך ש- $p_{i}>1$ ולכן לא מחלק אותו.
לכן, קיימים $\infty$ ראשוניים מהצורה $4n+3$ .
∎

תרגיל 2

תרגיל (2 [א])

יהיו $a,b \in \mathbb{Z}$ ונתון כי $(a,b)=d$ . הוכיחו כי $\left( \frac{a}{d}, \frac{b}{d} \right)=1$ .

הוכחה:
נתון כי $(a,b)=d$ ולכן $d \mid a$ וגם $d \mid b$ . לכן, קיימים $k,m \in \mathbb{Z}$ כך ש- $a=dk$ וגם $b=dm$ .
לכן, $\frac{b}{d}=m\cdot 1$ ולכן, לפי הגדרה, $1 \mid \frac{b}{d}$ . בנוסף, $\frac{a}{d}=k\cdot 1$ ולכן, $1 \mid \frac{a}{d}$ . לכן, $1$ מחלק משותף של $\frac{a}{d}$ ו- $\frac{b}{d}$ .
נניח כי קיים $1\neq e \in \mathbb{N}$ כך ש- $e \mid \frac{a}{d}\land e \mid \frac{b}{d}$ . כלומר, קיימים $k_{1},k_{2} \in \mathbb{Z}$ כך ש- $\frac{a}{d}=ek_{1}$ ו- $\frac{b}{d}=ek_{2}$ . אזי $b=ek_{2}d$ ו- $a=ek_{1}d$ .
נשים לב כי $ed \mid a$ וגם $ed \mid b$ ובנוסף, מכיוון ש- $e,d \in \mathbb{N}$ אזי $ed>\max\left\{ e,d \right\}$ ולכן, $d$ אינו הממ"גב של $a,b$ בסתירה לכך ש- $(a,b)=d$ .
לכן, לכל $e \in \mathbb{Z}$ כך ש- $e \mid a \land e \mid b$ מתקיים $1 \mid e$ .
לכן, לפי הגדרה, $\left( \frac{a}{d}, \frac{b}{d} \right)=1$ .
∎

תרגיל (2 [ב])

יהיו $a,b \in \mathbb{Z}$ כך ש- $a,b$ זרים.
הוכיחו כי $(a+b,a-b)=1$ או $(a+b,a-b)=2$ .

הוכחה:
נסמן $d=(a+b,a-b)$ . קיומו מובטח לפי משפט. לפי הגדרה, $d \mid a+b$ וגם $d \mid a-b$ . כלומר, קיימים $c_{1},c_{2} \in \mathbb{Z}$ כך שמתקיים: $a-b=dc_{1}$ ו- $a+b=dc_{2}$ .

\begin{align*} 2a=d(c_{1}+c_{2}) \qquad 2b=d(c_{1}-c_{2}) \end{align*}

לפי הנ"ל מתקיים כי $d \mid 2a$ וגם $d \mid 2b$ ולכן, לפי הגדרת ה- $gcd$ מתקיים $d \mid (2a,2b)$ . לפי משפט $d \mid 2(a,b)$ .
נתון כי $a,b$ זרים. כלומר, $(a,b)=1$ . לכן, $d \mid 2$ . כלומר, קיים $k \in \mathbb{Z}$ כך ש- $2=dk$ .

אם $d=1$ אז $k=2$ וסיימנו.
אם $d=2$ אז $k=1$ וסיימנו.
אם $d>2$ אז $k<1$ ובנוסף, מכיוון ש- $d>0$ ו- $2>0$ מתקיים כי $k>0$ בסתירה לכך ש- $k \in \mathbb{Z}$ .

לכן, $(a+b,a-b)=1$ או $(a+b,a-b)=2$ .
∎

תרגיל 3

תרגיל (3 [א])

יהיו $a,b \in \mathbb{Z}$ ו- $n\in \mathbb{N}$ . הוכיחו כי למשוואה $b=ax+ny$ יש פתרון שלם $(a,n)\mid b\iff$ .

הוכחה:
$:\impliedby$ קיימים $x,y \in \mathbb{Z}$ כך ש- $b=ax+ny$ . לפי משפט, קיים $d \in \mathbb{Z}$ יחיד כך ש- $(a,n)=d$ .
לפי הגדרת ממג"ב מתקיים כי $(a,n)\mid x$ וגם $(a,n)\mid n$ . לכן, לפי תכונות חלוקה: $(a,n)\mid ax+ny=b$ .
$:\implies$ נתון כי $(a,n)\mid b$ . לכן, לפי הגדרה, קיים $q \in \mathbb{Z}$ כך ש- $b=q(a,n)$ . לפי זהות בזו, קיימים $x_{0},y_{0}\in \mathbb{Z}$ כך ש- $b=q(ax_{0}+ny_{0})$ .
נסמן $x=qx_{0},y=qy_{0}$ ואז: $b=ax+ny$ כנדרש.
∎

תרגיל (3 [ב])

יהיו $a,b \in \mathbb{Z}$ ו- $n \in \mathbb{N}$ . הוכיחו כי למשוואה $ax\equiv b\pmod{n}$ יש פתרון $(a,n)\mid b\iff$ .

הוכחה:
לפי הגדרת מודלו מתקיים כי:

ax\equiv b\pmod{n}\iff \exists m \in \mathbb{Z}:\;ax=b+mn

נסמן $y=-m \in \mathbb{Z}$ ואז:

ax\equiv b\pmod{n}\iff \exists y \in \mathbb{Z}:\;ax+yn=b

לפי סעיף א':

ax\equiv b\pmod{n}\iff ax+yn=b \iff (a,n)\mid b

∎

תרגיל 1

תרגיל (1)

הוכיחו כי קיימים $\infty$ מספרים ראשוניים מהצורה $4n+3$ (כאשר $n=0,1,2,\dots$ )

(4n+1)^{k+1}\!=\!(4n+1)^k(4n+1)\!=\!(4m+1)(4n+1)\!=4^2nm+4n+4m+1=4(4nm+n+m)+1

תרגיל 2

תרגיל (2 [א])

יהיו $a,b \in \mathbb{Z}$ ונתון כי $(a,b)=d$ . הוכיחו כי $\left( \frac{a}{d}, \frac{b}{d} \right)=1$ .

תרגיל (2 [ב])

יהיו $a,b \in \mathbb{Z}$ כך ש- $a,b$ זרים.
הוכיחו כי $(a+b,a-b)=1$ או $(a+b,a-b)=2$ .

\begin{align*} 2a=d(c_{1}+c_{2}) \qquad 2b=d(c_{1}-c_{2}) \end{align*}

אם $d=1$ אז $k=2$ וסיימנו.
אם $d=2$ אז $k=1$ וסיימנו.
אם $d>2$ אז $k<1$ ובנוסף, מכיוון ש- $d>0$ ו- $2>0$ מתקיים כי $k>0$ בסתירה לכך ש- $k \in \mathbb{Z}$ .

לכן, $(a+b,a-b)=1$ או $(a+b,a-b)=2$ .
∎

תרגיל 3

תרגיל (3 [א])

יהיו $a,b \in \mathbb{Z}$ ו- $n\in \mathbb{N}$ . הוכיחו כי למשוואה $b=ax+ny$ יש פתרון שלם $(a,n)\mid b\iff$ .

תרגיל (3 [ב])

יהיו $a,b \in \mathbb{Z}$ ו- $n \in \mathbb{N}$ . הוכיחו כי למשוואה $ax\equiv b\pmod{n}$ יש פתרון $(a,n)\mid b\iff$ .

הוכחה:
לפי הגדרת מודלו מתקיים כי:

ax\equiv b\pmod{n}\iff \exists m \in \mathbb{Z}:\;ax=b+mn

נסמן $y=-m \in \mathbb{Z}$ ואז:

ax\equiv b\pmod{n}\iff \exists y \in \mathbb{Z}:\;ax+yn=b

לפי סעיף א':

ax\equiv b\pmod{n}\iff ax+yn=b \iff (a,n)\mid b

∎