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

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

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

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

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

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

בעקבות פתרון הבעיה העשירית של הילברט, ידוע שאין אלגוריתם המכריע האם למערכת משוואות נתונה יש פתרון. עם זאת, תורת המספרים הקלאסית התמודדה עם טיפוסים רבים של משוואות דיופנטיות (בעיקר ממעלות 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 אין פתרונות שלמים, למעט הטריוויאליים (שבהם אחד הנעלמים שווה ל-0).

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

המשוואה ax+by=c[עריכת קוד מקור | עריכה]

למשוואה הדיופנטית \ ax+by = c (עבור a,b,c נתונים) יש פתרון בשלמים אם ורק אם המחלק המשותף המקסימלי של a ו-b מחלק את c. במידה וכן נסמן gcd(a,b)=d ונייצג את d באמצעות אלגוריתם אוקלידס המורחב כך : d=aw+bz. על ידי הכפלה בc/d נקבל פתרון אחד למשוואה - ax1+by1=c. נקבל את שאר הפתרונות על ידי הנוסחאות : x = x1 + tb/d ו y = y1 - ta/d לכל t שלם.

דוגמה[עריכת קוד מקור | עריכה]

נתונה המשוואה 20x+17y=1000.
מכיוון ש-\gcd(20,17)=1|1000 קיים פתרון למשוואה.
20=17+3
17=5 \cdot 3 +2
3=2+1
1=3-2=3-(17-5 \cdot 3) = 6 \cdot 3 -17 =6(20-17) -17 = 6 \cdot 20 -7 \cdot 17 =1
נכפיל באלף ונקבל: 6000 \cdot 20 -7000\cdot 17 =1000
x_{0} = 6000,y_{0} = -7000<br נקבל x = 6000 + 17t , y = -7000 - 20t לכל t שלם.
לפתרונות הטבעיים נציב באי השוויון ונקבל -349>t>-353 ונקבל את הפתרונות x_{123} = 33,50,16 וy_{123}=20,0,40.

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

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