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

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

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

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

תוכן עניינים

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

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

אחת הדוגמאות העתיקות הוא משפט פיתגורס \!\, 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.