משוואה דיופנטית
מתוך ויקיפדיה, האנציקלופדיה החופשית
במתמטיקה משוואה דיופנטית היא משוואה שקבוצת הפתרונות שלה מוגבלת לקבוצת המספרים השלמים.
משוואות אלה קרויות על שם המתמטיקאי היווני דיופנטוס שחקר אותן.
תוכן עניינים |
[עריכה] דוגמאות למשוואות דיופנטיות
[עריכה] שלשות פיתגוריות
אחת הדוגמאות העתיקות הוא משפט פיתגורס
כאשר
(מספרים שלמים), שלושה מספרים המהווים פתרון למשוואה נקראים שלשה פיתגורית. המספרים {3,4,5} או {5,12,13} הינם דוגמאות לשלשה פיתגורית. אם ניקח את השלשה ונכפיל אותה ב-2 נקבל שלשה פיתגורית חדשה {6,8,10}. כהכללה, כל שלשה פיתגורית ניתנת להרחבה לאין סוף שלשות. נגדיר שלשה פיתגורית פרימיטיבית כשלשה שבה המחלק המשותף המקסימלי שווה 1 כלומר 
ניתן לייצר שלשות פיתגוריות באמצעות הנוסחה :
כאשר s,t מספרים טבעיים.
[עריכה] המשפט האחרון של פרמה
המשפט האחרון של פרמה :
כאשר
(מספרים טבעייים) ו
המשפט טוען שלמשוואה אין פתרונות שבהם
.
[עריכה] שימושים להצפנה
לחלק מהמשוואות הדיופנטיות, לא קיימת דרך ישירה למציאת הפתרונות, חוץ מבדיקת כל האפשרויות, דרך בלתי־מעשית כאשר המספרים גדולים מאוד.
לדוגמה: העובדה שפירוק לגורמים של מספרים גדולים (מציאת x ו-y שלמים המקיימים את המשוואה
כאשר n הוא מספר שלם נתון) אינו מעשי אפילו בעזרת מחשבי על, משמשת את שיטת ההצפנה RSA.
דוגמה נוספת, בשיטת Diffie-Hellman, מנצלים את "בעיית הלוג הדיסקרטי" (
כאשר a,b,c הם מספרים שלמים נתונים). גם במקרה זה אין דרך ישירה למציאת הפתרון ואפילו מחשבים משוכללים לא יכולים לפתור אותה במספרים גדולים, ולכן היא אידאלית להצפנה.
[עריכה] משוואה דיופנטית לינארית
משוואה דיופנטית לינארית היא משוואה מהצורה :
כאשר a,b,c הם מספרים שלמים נתונים ולפחות a או b שונה מאפס.
פתרון הקונגרואנסיה
כאשר a,b הם מספרים שלמים נתונים וn מספר טבעי נתון,נעשה בעזרת המרה למשוואה הדיופנטית :
אחרי סידור מתקבלת הצורה הרגילה :
.
[עריכה] תנאי לקיום פתרונות למשוואה דיופנטית לינארית
למשוואה הדיופנטית
יש פתרון אם ורק אם c מתחלק בd כאשר
.
[עריכה] פתרון משוואה דיופנטית לינארית
כדי לפתור משוואה דיופנטית לינארית נשתמש בהרחבה של האלגוריתם למציאת מחלק משותף מקסימלי .
קודם נמצא את
ונבדוק אם הוא מחלק את c . אם כן , נחלק את המשוואה בd :

נרשום את
,על פי האלגוריתם של אוקלידס :






נתחיל מהסוף ונבודד את d :

באותה צורה נבודד את
:

נציב :

נמשיך כך ש
יבטאו את d ואלו יהיו פתרונות המשוואה :

נכפול ב
ונקבל את הפתרונות למשוואה המקורית.
על מנת למצוא את הפתרונות הכלליים נחשב
ואז נחשב : 
[עריכה] דוגמה
נפתור את המשוואה :
נחשב :
, 15 מתחלק ב3 לכן ישנו פתרון, נחלק את המשוואה ב3 ונקבל :
נפתור :


נתחיל לבודד :


נציב :


הפתרונות בהתאמה : 
נכפול ב 15 :

כלומר :

עכשיו נחשב את הפתרונות הכללים :

.

