משוואה דיופנטית

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

במתמטיקה משוואה דיופנטית היא משוואה שקבוצת הפתרונות שלה מוגבלת לקבוצת המספרים השלמים.

משוואות אלה קרויות על שם המתמטיקאי היווני דיופנטוס שחקר אותן.

תוכן עניינים

1 דוגמאות למשוואות דיופנטיות
2 משוואה דיופנטית לינארית

[עריכה] דוגמאות למשוואות דיופנטיות

[עריכה] שלשות פיתגוריות

אחת הדוגמאות העתיקות הוא משפט פיתגורס $\!\, x^2 +y^2= z^2$ כאשר $\left\{x , y , z \right\}\in \mathbb{Z}$ (מספרים שלמים), שלושה מספרים המהווים פתרון למשוואה נקראים שלשה פיתגורית. המספרים {3,4,5} או {5,12,13} הינם דוגמאות לשלשה פיתגורית. אם ניקח את השלשה ונכפיל אותה ב-2 נקבל שלשה פיתגורית חדשה {6,8,10}. כהכללה, כל שלשה פיתגורית ניתנת להרחבה לאין סוף שלשות. נגדיר שלשה פיתגורית פרימיטיבית כשלשה שבה המחלק המשותף המקסימלי שווה 1 כלומר $gcd\left(x,y,z\right) =1$

ניתן לייצר שלשות פיתגוריות באמצעות הנוסחה :
$\!\, x=2st, y =s^2 -t^2, z= s^2 +t ^2$ כאשר s,t מספרים טבעיים.

[עריכה] המשפט האחרון של פרמה

המשפט האחרון של פרמה : $\!\,x^n+y^n=z^n$ כאשר $\ x,y,z\in \mathbb{Z}$ (מספרים טבעייים) ו $\!\, n > 2$ המשפט טוען שלמשוואה אין פתרונות שבהם $\ x,y,z\neq 0$ .

[עריכה] שימושים להצפנה

לחלק מהמשוואות הדיופנטיות, לא קיימת דרך ישירה למציאת הפתרונות, חוץ מבדיקת כל האפשרויות, דרך בלתי־מעשית כאשר המספרים גדולים מאוד.

לדוגמה: העובדה שפירוק לגורמים של מספרים גדולים (מציאת x ו-y שלמים המקיימים את המשוואה $\!\,xy =n$ כאשר n הוא מספר שלם נתון) אינו מעשי אפילו בעזרת מחשבי על, משמשת את שיטת ההצפנה RSA.

דוגמה נוספת, בשיטת Diffie-Hellman, מנצלים את "בעיית הלוג הדיסקרטי" ( $\!\, a^x-c = by$ כאשר a,b,c הם מספרים שלמים נתונים). גם במקרה זה אין דרך ישירה למציאת הפתרון ואפילו מחשבים משוכללים לא יכולים לפתור אותה במספרים גדולים, ולכן היא אידאלית להצפנה.

[עריכה] משוואה דיופנטית לינארית

משוואה דיופנטית לינארית היא משוואה מהצורה : $\!\, ax+by=c$ כאשר a,b,c הם מספרים שלמים נתונים ולפחות a או b שונה מאפס.
פתרון הקונגרואנסיה $\!\, ax\equiv c\pmod{n}$ כאשר a,b הם מספרים שלמים נתונים וn מספר טבעי נתון,נעשה בעזרת המרה למשוואה הדיופנטית :
$\!\, ax-c=by$ אחרי סידור מתקבלת הצורה הרגילה : $\!\, ax+by=c$ .

[עריכה] תנאי לקיום פתרונות למשוואה דיופנטית לינארית

למשוואה הדיופנטית $\!\, ax+by=c$ יש פתרון אם ורק אם c מתחלק בd כאשר $gcd\left(a,b\right) =d$ .

[עריכה] פתרון משוואה דיופנטית לינארית

כדי לפתור משוואה דיופנטית לינארית נשתמש בהרחבה של האלגוריתם למציאת מחלק משותף מקסימלי .
קודם נמצא את $gcd\left(a,b\right) =d$ ונבדוק אם הוא מחלק את c . אם כן , נחלק את המשוואה בd :
$\!\, \frac{a}{d} x+\frac{b}{d} y=\frac{c}{d}$
נרשום את $\!\, b=r_2 , a=r_1$ ,על פי האלגוריתם של אוקלידס :

$\!\, r_1=q_1 r_2 + r_3$
$\!\, r_2=q_2 r_3 + r_4$
$\!\, .$
$\!\, .$
$\!\, .$
$\!\, r_{n-2}=q_{n-2} r_{n-1} + 1$

נתחיל מהסוף ונבודד את d :
$\!\, 1=q_{n-2} r_{n-1} -r_{n-2}$

באותה צורה נבודד את $\!\, r_{n-1}$ :
$\!\, r_{n-1}=r_{n-3} - q_{n-3} r_{n-2}$

נציב :
$\!\, 1=q_{n-2} (r_{n-3} - q_{n-3} r_{n-2}) -r_{n-2}$

נמשיך כך ש $\!\, b=r_2 , a=r_1$ יבטאו את d ואלו יהיו פתרונות המשוואה :
$\!\, \frac{a}{d} x+\frac{b}{d}y = d$

נכפול ב $\!\, c$ ונקבל את הפתרונות למשוואה המקורית.

על מנת למצוא את הפתרונות הכלליים נחשב $gcd\left(a,b\right) =d$ ואז נחשב : $\!\, x =x_0 + \frac{b}{d} t , y =y_0 - \frac{a}{d} t$

[עריכה] דוגמה

נפתור את המשוואה : $\!\, 21 x+12 y=15$ נחשב : $gcd\left(21,12\right) =3$ , 15 מתחלק ב3 לכן ישנו פתרון, נחלק את המשוואה ב3 ונקבל :
$\!\, 7x+4y=5$ נפתור :

$\!\, 7= 4*1 +3$
$\!\, 4= 3*1 +1$

נתחיל לבודד :
$\!\, 1=4-3$
$\!\, 3= 7 -4$

נציב :
$\!\, 1=4-(7-4)$
$\!\, 1=(-1)*7+(2)*4$

הפתרונות בהתאמה : $\!\, x_0 =-1 , y_0 =2$

נכפול ב 15 :
$\!\, x_0 =-15 , y_0 =30$
כלומר :
$\!\, 7 *(-15) +4*(30) =15$

עכשיו נחשב את הפתרונות הכללים :
$\!\, x =-15 + \frac{12}{3} t , y =30 - \frac{21}{3} t$

$\!\, x =-15 + 4 t , y =30 - 7 t$ .