# תרגיל בית 1 — פולינומים !!! info "פרק רלוונטי" כל השאלות בתרגיל הזה מבוססות על [פרק הפולינומים](/course/lini2b/polynomials). מומלץ לקרוא קודם את הפרק (במיוחד את משפט החילוק, משפט בזו, ומשפט השורש הרציונלי) ואז לנסות לבד. !!! warning "שימו לב" הפתרונות כאן נכתבו לפני שעלו הפתרונות הרשמיים. כשיגיעו, נבדוק שוב את הניואנסים. --- ## שאלה 1 — חילוק עם שארית חלקו עם שארית את שני הפולינומים הנתונים $f, g \in \mathbb{R}[x]$ — מצאו $p, r \in \mathbb{R}[x]$ כך ש-$f = g \cdot p + r$, $\deg(r) < \deg(g)$. ### (א) $g = x + 4$, $f = x^4 - x^3 - 18x^2 + 7x + 1$ !!! tip "אסטרטגיה" כשהמחלק הוא $(x - \alpha)$ אפשר להשתמש בחילוק סינתטי (סכמת הורנר) — מהיר ופחות מועד לטעויות. כאן $\alpha = -4$. **חילוק סינתטי עם $\alpha = -4$:** | | $1$ | $-1$ | $-18$ | $7$ | $1$ | |---|---|---|---|---|---| | $-4$ | $1$ | $-5$ | $2$ | $-1$ | $5$ | חישוב: $1 \to (-4)(1) + (-1) = -5 \to (-4)(-5) + (-18) = 2 \to (-4)(2) + 7 = -1 \to (-4)(-1) + 1 = 5$. $$p(x) = x^3 - 5x^2 + 2x - 1, \qquad r = 5$$ **בדיקה:** $(x + 4)(x^3 - 5x^2 + 2x - 1) + 5 = x^4 - x^3 - 18x^2 + 7x + 1$ ✓ ### (ב) $g = x^2 + 3$, $f = 2x^5 + x^4 + 6x^3 + 3x^2$ חילוק ארוך: **שלב 1:** $\frac{2x^5}{x^2} = 2x^3$. כפול: $2x^3 \cdot (x^2 + 3) = 2x^5 + 6x^3$. $$f - 2x^3 \cdot g = (2x^5 + x^4 + 6x^3 + 3x^2) - (2x^5 + 6x^3) = x^4 + 3x^2$$ **שלב 2:** $\frac{x^4}{x^2} = x^2$. כפול: $x^2 \cdot (x^2 + 3) = x^4 + 3x^2$. $$x^4 + 3x^2 - (x^4 + 3x^2) = 0$$ $$p(x) = 2x^3 + x^2, \qquad r = 0$$ **בדיקה:** $(x^2 + 3)(2x^3 + x^2) = 2x^5 + x^4 + 6x^3 + 3x^2$ ✓ !!! note "מסקנה" כיוון ש-$r = 0$, נסיק $(x^2 + 3) \mid f$. ### (ג) $g = x^2 + x + 1$, $f = x^3 + x^2 + x + 1$ **שלב 1:** $\frac{x^3}{x^2} = x$. כפול: $x \cdot (x^2 + x + 1) = x^3 + x^2 + x$. $$f - x \cdot g = (x^3 + x^2 + x + 1) - (x^3 + x^2 + x) = 1$$ $\deg(1) = 0 < 2 = \deg(g)$, עוצרים. $$p(x) = x, \qquad r = 1$$ **בדיקה:** $(x^2 + x + 1)(x) + 1 = x^3 + x^2 + x + 1$ ✓ --- ## שאלה 2 — אי-פריקות מעל $\mathbb{Q}$ ומעל $\mathbb{R}$ קבעו האם $f = x^3 - 5x^2 + 2x + 3$ אי-פריק מעל $\mathbb{Q}$ ומעל $\mathbb{R}$. ### מעל $\mathbb{R}$ !!! tip "אסטרטגיה" $f$ פולינום ממשי מ**דרגה אי-זוגית** (3). לפי המשפט שהוכחנו, יש לו לפחות שורש ממשי אחד. נסיק שקיים $a \in \mathbb{R}$ כך ש-$f(a) = 0$, ולכן $(x - a) \mid f$ — כלומר $f = (x - a) \cdot q(x)$ עם $\deg(q) = 2$. **מסקנה:** $f$ **לא** אי-פריק מעל $\mathbb{R}$. ### מעל $\mathbb{Q}$ !!! tip "אסטרטגיה" משתמשים ב**משפט השורש הרציונלי**: אם $\frac{p}{q}$ שורש (בצמצום), אז $p \mid 3$ ו-$q \mid 1$. מועמדים: $\pm 1, \pm 3$. | $\alpha$ | $f(\alpha)$ | |---|---| | $1$ | $1 - 5 + 2 + 3 = 1$ | | $-1$ | $-1 - 5 - 2 + 3 = -5$ | | $3$ | $27 - 45 + 6 + 3 = -9$ | | $-3$ | $-27 - 45 - 6 + 3 = -75$ | אף לא אחד מאפס $\Rightarrow$ **אין שורשים רציונליים** ל-$f$. !!! note "טענה: פולינום ממעלה 3 בלי שורש רציונלי הוא אי-פריק מעל $\mathbb{Q}$" פולינום ממעלה $3$ מתפרק רק כ-(לינארי)·(ריבועי). אם הוא היה מתפרק לא-טריוויאלית מעל $\mathbb{Q}$, היה לו גורם לינארי $(x - r)$ עם $r \in \mathbb{Q}$, כלומר שורש רציונלי. אין לו → אי-פריק. **מסקנה:** $f$ **כן** אי-פריק מעל $\mathbb{Q}$. --- ## שאלה 3 — פירוק מעל $\mathbb{C}, \mathbb{R}, \mathbb{Q}$ פרקו את $f = x^3 - 2x + 4$ מעל כל אחד מהשדות. ### מציאת שורש רציונלי לפי משפט השורש הרציונלי, מועמדים: $\pm 1, \pm 2, \pm 4$. | $\alpha$ | $f(\alpha)$ | |---|---| | $1$ | $1 - 2 + 4 = 3$ | | $-1$ | $-1 + 2 + 4 = 5$ | | $2$ | $8 - 4 + 4 = 8$ | | $-2$ | $-8 + 4 + 4 = 0$ ✓ | מצאנו $\alpha = -2$ שורש, אז $(x + 2) \mid f$. ### חילוק סינתטי | | $1$ | $0$ | $-2$ | $4$ | |---|---|---|---|---| | $-2$ | $1$ | $-2$ | $2$ | $0$ | $$f = (x + 2)(x^2 - 2x + 2)$$ ### ניתוח הגורם הריבועי הדיסקרימיננטה של $x^2 - 2x + 2$: $$\Delta = 4 - 8 = -4 < 0$$ לכן אין לו שורשים ממשיים — הוא אי-פריק מעל $\mathbb{R}$ ומעל $\mathbb{Q}$. מעל $\mathbb{C}$: $x = \frac{2 \pm \sqrt{-4}}{2} = 1 \pm i$. ### פירוקים | שדה | פירוק | |---|---| | $\mathbb{Q}$ | $(x + 2)(x^2 - 2x + 2)$ | | $\mathbb{R}$ | $(x + 2)(x^2 - 2x + 2)$ | | $\mathbb{C}$ | $(x + 2)\big(x - (1+i)\big)\big(x - (1-i)\big)$ | !!! note "תצפית" מעל $\mathbb{Q}$ ומעל $\mathbb{R}$ קיבלנו את אותו פירוק — כי הגורם הריבועי כבר היה אי-פריק מעל שניהם. רק כשעוברים ל-$\mathbb{C}$ הוא מתפצל לזוג גורמים לינאריים צמודים. --- ## שאלה 4 — תכונות של mod הוכיחו: לכל פולינומים $f, g, p \in F[x]$ עם $p \neq 0$: $$(f + g) \bmod p = ((f \bmod p) + (g \bmod p)) \bmod p$$ $$(f \cdot g) \bmod p = ((f \bmod p) \cdot (g \bmod p)) \bmod p$$ ### הגדרה ונוטציה לפי משפט החילוק, $f = q_f \cdot p + r_f$ עם $\deg(r_f) < \deg(p)$ (או $r_f = 0$). **הגדרה:** $f \bmod p := r_f$. באופן דומה $g = q_g \cdot p + r_g$. ### הוכחה — חיבור $$f + g = (q_f + q_g) \cdot p + (r_f + r_g)$$ לוקחים את שני האגפים $\bmod p$: $$(f + g) \bmod p = (r_f + r_g) \bmod p$$ ובאופן בלתי תלוי: $$((f \bmod p) + (g \bmod p)) \bmod p = (r_f + r_g) \bmod p$$ שני האגפים שווים. $\blacksquare$ !!! tip "נקודה עדינה" מותר היה לרצות לטעון "$\deg(r_f + r_g) < \deg(p)$ ולכן $(r_f + r_g) \bmod p = r_f + r_g$", וזה נכון. אבל אם רוצים נוסחה אחידה שעובדת גם במקרה הכפל (שבו זה לא נכון), עדיף לכתוב את הצורה עם $\bmod$ בחוץ. ### הוכחה — כפל $$f \cdot g = (q_f p + r_f)(q_g p + r_g) = \underbrace{q_f q_g p^2 + q_f r_g p + r_f q_g p}_{\text{מכיל }p\text{ כגורם}} + r_f r_g$$ האיברים הראשונים מתחלקים ב-$p$. לוקחים $\bmod p$: $$(f \cdot g) \bmod p = (r_f r_g) \bmod p$$ ובאופן בלתי תלוי: $$((f \bmod p) \cdot (g \bmod p)) \bmod p = (r_f r_g) \bmod p$$ שני האגפים שווים. $\blacksquare$ !!! warning "למה צריך $\bmod p$ סופי בנוסחת הכפל" כאן $\deg(r_f r_g)$ יכול להגיע עד $2(\deg(p) - 1) \geq \deg(p)$, אז $r_f r_g$ עצמו לא בהכרח השארית. צריך לחלק שוב ב-$p$ לקבל את השארית הסופית. --- ## שאלה 5 — $x^k \bmod (x - \alpha) = \alpha^k$ הוכיחו באינדוקציה, תוך שימוש בשאלה 4: $x^k \bmod (x - \alpha) = \alpha^k$ לכל $k \in \mathbb{N}$ ו-$\alpha \in F$. ### בסיס: $k = 1$ $$x = 1 \cdot (x - \alpha) + \alpha$$ $\deg(\alpha) = 0 < 1 = \deg(x - \alpha)$, לכן $x \bmod (x - \alpha) = \alpha = \alpha^1$. ✓ ### צעד אינדוקציה נניח שלכל $k$ נתון מתקיים $x^k \bmod (x - \alpha) = \alpha^k$. נראה ל-$k + 1$: $$x^{k+1} = x \cdot x^k$$ לפי תכונת הכפל (שאלה 4): $$x^{k+1} \bmod (x - \alpha) = \big( (x \bmod (x - \alpha)) \cdot (x^k \bmod (x - \alpha)) \big) \bmod (x - \alpha)$$ לפי הבסיס: $x \bmod (x - \alpha) = \alpha$. לפי הנחת האינדוקציה: $x^k \bmod (x - \alpha) = \alpha^k$. מציבים: $$x^{k+1} \bmod (x - \alpha) = (\alpha \cdot \alpha^k) \bmod (x - \alpha) = \alpha^{k+1} \bmod (x - \alpha)$$ כיוון ש-$\alpha^{k+1}$ קבוע ($\deg = 0 < 1$), $\bmod$ לא משנה אותו: $$x^{k+1} \bmod (x - \alpha) = \alpha^{k+1} \qquad \blacksquare$$ --- ## שאלה 6 — $f \bmod (x - \alpha) = f(\alpha)$ הוכיחו: לכל $f \in F[x]$ ולכל $\alpha \in F$ מתקיים $f \bmod (x - \alpha) = f(\alpha)$. ### דרך i — אינדוקציה על הדרגה (משתמש בשאלות 4-5) יהי $f = a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n$. **בסיס $n = 0$:** $f = a_0$ קבוע. אז $f \bmod (x - \alpha) = a_0 = f(\alpha)$. ✓ **צעד אינדוקציה:** נניח שעבור פולינומים מדרגה $< n$ הטענה נכונה. נראה לפולינום $f$ מדרגה $n$. כתוב $f = a_n x^n + g$ כאשר $g = a_0 + \cdots + a_{n-1} x^{n-1}$ מדרגה $< n$. לפי תכונת החיבור (שאלה 4): $$f \bmod (x - \alpha) = \big( (a_n x^n \bmod (x - \alpha)) + (g \bmod (x - \alpha)) \big) \bmod (x - \alpha)$$ - $a_n x^n \bmod (x - \alpha) = a_n \cdot \alpha^n$ (מתכונות הכפל בקבוע + שאלה 5) - $g \bmod (x - \alpha) = g(\alpha)$ (הנחת אינדוקציה) מציבים: $$f \bmod (x - \alpha) = (a_n \alpha^n + g(\alpha)) \bmod (x - \alpha)$$ הביטוי $a_n \alpha^n + g(\alpha)$ הוא קבוע (לא תלוי ב-$x$), ולכן $\bmod$ לא משנה אותו: $$f \bmod (x - \alpha) = a_n \alpha^n + g(\alpha) = f(\alpha) \qquad \blacksquare$$ ### דרך ii — ישירות (משפט בזו) לפי משפט החילוק, קיימים $q(x) \in F[x]$ ו-$r$ קבוע (כי $\deg(r) < 1$) כך ש: $$f(x) = (x - \alpha) \cdot q(x) + r$$ נציב $x = \alpha$: $$f(\alpha) = (\alpha - \alpha) \cdot q(\alpha) + r = 0 + r = r$$ לכן $r = f(\alpha)$, וזו השארית — כלומר $f \bmod (x - \alpha) = f(\alpha)$. $\blacksquare$ !!! tip "השוואה" דרך i דורשת לבנות מהיסוד עם הוכחות נפרדות. דרך ii (משפט בזו) קצרה מאוד ומהווה את ההוכחה הקנונית. בקורסי אלגברה משתמשים בדרך ii. ### (ב) מסקנה: $\alpha$ שורש $\Leftrightarrow (x - \alpha) \mid f$ נתון: $\alpha$ שורש של $f$, כלומר $f(\alpha) = 0$. לפי סעיף (א): $f \bmod (x - \alpha) = f(\alpha) = 0$. "השארית בחילוק היא $0$" משמעו שהחילוק עובר ללא שארית — כלומר $(x - \alpha) \mid f$. $\blacksquare$ --- ## דף מושגים | מושג | הגדרה קצרה | |------|-----------| | **חילוק עם שארית** | $f = qg + r$, $\deg(r) < \deg(g)$ | | **חילוק סינתטי (סכמת הורנר)** | אלגוריתם מהיר לחילוק ב-$(x - \alpha)$ | | **מודולו פולינום** | $f \bmod p$ = השארית בחילוק $f$ ב-$p$ | | **משפט השורש הרציונלי** | מועמדים לשורש רציונלי הם $\pm \frac{p}{q}$ עם $p \mid a_0, q \mid a_n$ | | **משפט בזו** | $f \bmod (x - \alpha) = f(\alpha)$ | | **קריטריון אי-פריקות לדרגה 3 מעל $\mathbb{Q}$** | אי-פריק $\Leftrightarrow$ אין שורש רציונלי |