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

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

מיון בסיסי מבחין בין משוואות פולינומיות לבין משוואות כלליות. פרמטרים חשובים הם מספר המשוואות ומספר המשתנים. יש גם משוואות לא־פולינומיות, כמו a^x = c + n y (זו משוואה שבה מופיעה חזקת משתנה ולכן אין לה תאוריה כללית פשוטה). התאוריה המודרנית משתמשת בכלים של גאומטריה אריתמטית וממיינת משוואות לפי המאפיינים הגאומטריים שלהן, כמו הגנוס (מדד גאומטרי שמעריך את הסיבוכיות של העקום). בעקבות פתרון הבעיה העשירית של הילברט ידוע שאין אלגוריתם כללי שמכריע האם מערכת משוואות דיופנטיות נתונה יש לה פתרון שלם.

למרות זאת, תורת המספרים קלאסית פתרה הרבה מקרים, בעיקר ממעלות 2, 3 ו-4. דוגמה ידועה היא המשוואה x^2+y^2=z^2 (משולשים ישרי־זווית). פתרונותיה נקראים שלשות פיתגוריות ויש נוסחה כללית: x=2st, y=s^2-t^2, z=s^2+t^2 כאשר s,t הם מספרים טבעיים. לפי משפט פרמה האחרון, למשוואה x^n+y^n=z^n אין פתרונות שלמים לא־טריוויאליים כאשר n>2.

משוואות דיופנטיות קשורות גם לבעיות חישוביות קשות. החיבור xy=n (עם x,y>1) שקול לפירוק n לגורמיו הראשוניים. פירוק ראוי נחשב קשה לחישוב עבור מספרים גדולים, ועל כך מבוססות שיטות הצפנה כמו RSA.

למשוואה הליניארית ax+by=c (a,b,c שלמים נתונים) יש פתרון בשלמים אם ורק אם המחלק המשותף המקסימלי של a ו-b מחלק את c. נסמן את המחלק המשותף הגדול ב-d. בעזרת אלגוריתם אוקלידס המורחב (שיטה לחישוב ה-gcd וגם למציאת מקדמים) מוצאים שלמים z1,z2 כך ש-az1+bz2=d. אז x0 = z1*(c/d) ו-y0 = z2*(c/d) הם פתרון, ואת כל הפתרונות מקבלים על ידי הנוסחה:

x = x0 + t*(b/d),
y = y0 - t*(a/d)

עבור כל t שלם.

למשוואה 20x+17y=1000 המחלק המשותף הגדול של 20 ו-17 הוא d=1, והוא מחלק את 1000. באמצעות אלגוריתם אוקלידס המורחב מוצאים z1=6 ו-z2=-7 שמקיימים 20·6+17·(-7)=1. לכן x0=6000 ו-y0=-7000 הם פתרון למשוואה, ויש משפחה של פתרונות:

(x,y) = (6000+17t,
-7000-20t)

לכל t שלם.

בעקבות עקרון הסה, עבור משוואות ריבועיות הומוגניות יש פתרון שלם אם ורק אם יש לה פתרונות ממשיים ובכל השדות המקומיים המתאימים (בדיקה מודולרית לפי חזקה של ראשוני). עקרון זה לא תמיד תקף למשוואות ממעלה גבוהה יותר, וגם לא תמיד בעקומים אליפטיים. הכישלון של עקרון הסה במקרה זה נמדד על ידי חבורת שפרביץ', שלגביה יש השערות לגבי סופיותה.

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

יש משוואות פולינומיות ומשוואות שאינן פולינומיות. לדוגמה a^x = c + n y היא משוואה עם חזקות. חלק מהמשוואות האלה קלות, וחלקן מאוד קשות.

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

יש גם משפט גדול בשם משפט פרמה האחרון. הוא אומר שאם n גדול מ-2, אז אין מספרים שלמים חיוביים x,y,z שמקיימים x^n+y^n=z^n.

במשוואה ax+by=c צריך שהמחלק המשותף הגדול של a ו-b יחלק את c. "המחלק המשותף הגדול" הוא המספר הגדול ביותר שמחלק את שניהם. אפשר למצוא פתרון בעזרת שיטה חישובית שנקראת אלגוריתם של אוקלידס.

למשוואה 20x+17y=1000 המחלק המשותף הגדול הוא 1. הוא מחלק את 1000, לכן יש פתרון. בעזרת האלגוריתם מוצאים 6 ו-(-7). אז אחד מהפתרונות הוא x=6000 ו-y=-7000. כל הפתרונות הם:
(x,y) = (6000+17t, -7000-20t)
עבור כל מספר שלם t.

יש כלל בשם עקרון הסה שעוזר לפתור משוואות ריבועיות. הכלל עובד בחלק מהמקרים, אבל לא תמיד. יש משוואות קשות יותר שבהן הכלל נכשל.