שינויים

קפיצה אל: ניווט, חיפוש

מבנים אלגבריים למדעי המחשב - ארז שיינר

נוספו 809 בתים, 12:17, 4 בינואר 2018
/* הרצאה 12 חוג הפולינומים; פרקים 16,17 מהספר */
*תזכורת: חוג הוא קבוצה <math>R</math> עם פעולות חיבור וכפל, כך שהוא חבורה חילופית ביחד לחיבור, מקיים אסוציאטיביות בכפל, מכיל איבר יחידה ואת חוק הפילוג.
 
 
===חוג הפולינומים===
 
*יהי <math>\mathbb{F}</math> שדה, אזי <math>\mathbb{F}[x]</math> הוא חוג הפולינומים עם פעולות כפל וחיבור רגילות.
**כלומר <math>\mathbb{F}[x]=\{a_nx^n+...+a_1x+a_0|n\in\mathbb{N},a_i\in\mathbb{F}\}</math>.
*טענה(חלוקה עם שארית): יהיו שני פולינומים <math>f(x),g(x)\in\mathbb{F}[x]</math> כך ש<math>g(x)</math> אינו פולינום האפס, אזי קיימים פולינומים יחידים <math>q(x),r(x)</math> כך ש:
**<math>f(x)=q(x)g(x)+r(x)</math>.
**<math>\deg(r(x))<\deg(g(x))</math>.
*מסקנה: עבור פולינום <math>f(x)</math> ועבור נקודה <math>a\in\mathbb{F}</math> מתקיים כי <math>f(a)=0</math> אם"ם קיים פולינום <math>q(x)</math> כך ש <math>f(x)=q(x)(x-a)</math>.
*במילים: a הינו שורש של הפולינום f אם"ם הפולינום f מתחלק בפולינום x-a.
*הוכחה:
**לפי משפט החלוקה עם שארית קיימים פולינומים <math>q(x),r(x)</math> כך ש:
***<math>f(x)=q(x)(x-a)+r(x)</math>.
***<math>\deg(r(x))<\deg(x-a)=1</math>, כלומר <math>r(x)=r\inmathbb{F}</math> הוא קבוע.
**נציב <math>a</math> ונקבל <math>f(a)=r</math>.
**לכן <math>f(x)=q(x)(x-a)</math> אם ורק אם <math>f(a)=0</math>.