משוואה דיופנטית – הבדלי גרסאות

משוואות דיופנטיות מערבות במקרים רבים קשיים חישוביים משמעותיים. פתרון המשוואה הפשוטה <math>\ xy = n</math> (עבור <math>\ x,y>1</math>) שקול ל[[פירוק מספר שלם לגורמים|בעיית הפירוק]] של המספר n לגורמיו הראשוניים, ומאמינים שעבור n גדול, זוהי בעיה קשה. יש שיטות הצפנה נפוצות (כמו [[RSA]]) שחוזקן מבוסס על ההנחה שבעיית הפירוק אכן קשה לפתרון.

 

== המשוואה <i style="font-family:Times New Roman;">ax+by=c</i> ==

למשוואה הדיופנטית <math>\ ax+by = c</math> (עבור a,b,c נתונים) יש פתרון בשלמים אם ורק אם ה[[מחלק משותף מקסימלי|מחלק המשותף המקסימלי]] של a ו-b מחלק את c.