אלגוריתם אוקלידס – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
תגיות: עריכה ממכשיר נייד עריכה דרך האתר הנייד |
מ שוחזר מעריכות של 176.12.181.65 (שיחה) לעריכה האחרונה של 192.114.23.215 |
||
שורה 1:
'''אלגוריתם אוקלידס''' הוא [[אלגוריתם]] [[אריתמטיקה|אריתמטי]] המאפשר למצוא, בהינתן שני [[מספר טבעי|מספרים טבעיים]], את ה[[מחלק משותף מקסימלי|מחלק המשותף המקסימלי]] שלהם.
התיעוד הקדום ביותר של האלגוריתם הוא בספר [[יסודות (ספר)|יסודות]] של [[אוקלידס]], בסביבות שנת 300 לפני הספירה. זהו אחד האלגוריתמים העתיקים ביותר הנמצאים בשימוש היום.
האלגוריתם הוא אחד מהכלים המרכזיים ב[[תורת המספרים]] ויש לו שימושים רבים, לדוגמה ב[[צופן]] [[RSA]].
==רקע==
המחלק המשותף המקסימלי של מספרים, המסומן <math>gcd(a,b)</math> או בקיצור <math>(a,b)</math>, היא פעולה המקבלת שני מספרים טבעיים, ומחזירה את המספר הגדול ביותר ש[[מחלק]] את שניהם.
שורה 20 ⟵ 26:
ראשית יש [[הוכחה|להוכיח]] את השוויון <math>(b,c+qb) = (b,c)</math>.
נניח ש-g מחלק את b ו-c. אז קיימים m,n טבעיים כך ש-<math>b=mg, c=ng</math>. מכאן: <math>c+qb=qmg+ng=(qm+n)g</math>.
בכיוון ההפוך, נניח ש-h מחלק את <math>c+qb</math> וגם את b. אז קיימים m,n טבעיים כך ש-<math>b=mh, c+qb=nh</math>. מכאן: <math>c=(c+qb)-qb=nh-qmh=(n-qm)h</math>. כלומר h מחלק את c, ומכאן שהוא מחלק משותף של b ושל c.
קיבלנו שמספר הוא מחלק משותף של <math>c+qb</math> ושל b [[אם ורק אם]] הוא מחלק משותף של b ושל c. לכן [[קבוצה (מתמטיקה)|קבוצת]] המחלקים המשותפים של הזוגות זהה, ובפרט האיבר המקסימלי שלהם זהה. מכאן <math>(b,c+qb) = (b,c)</math>.
==דוגמה==
| |||