תוֹכֶן

• צעדים
• שיטה 1 מתוך 2: אלגוריתם מפריד
• שיטה 2 מתוך 2: Prime Factors
• טיפים

המחלק המשותף הגדול ביותר (GCD) של שני מספרים שלמים הוא המספר השלם הגדול ביותר המחלק כל אחד מהמספרים הללו. לדוגמה, ה- gcd עבור 20 ו- 16 הוא 4 (הן ל- 16 והן ל- 20 יש מחלקים גדולים, אך הם אינם נפוצים - למשל, 8 הוא מחלק של 16, אך לא מחלק של 20). קיימת שיטה פשוטה ושיטתית למציאת GCD, הנקראת "האלגוריתם של אוקלידס". מאמר זה יראה לכם כיצד למצוא את המחלק המשותף הגדול ביותר מבין שני מספרים שלמים.

צעדים

שיטה 1 מתוך 2: אלגוריתם מפריד

1. 1 השמט כל סימני מינוס.
2. 2 למד את הטרמינולוגיה: כאשר מחלקים 32 ב -5,
   • 32 - דיבידנד
   • 5 - מחלק
   • 6 - פרטי
   • 2 - שאר
3. 3 קבע את המספרים הגדולים ביותר. זה יהיה מתחלק, והמספר הקטן יותר יהיה המחלק.
4. 4 רשום את האלגוריתם הבא: (דיבידנד) = (מחלק) * (כמות) + (שאר)
5. 5 שים מספר גדול יותר במקום הדיבידנד ומספר קטן יותר במקום המחלק.
6. 6 מצא כמה פעמים המספר הגדול יותר מחולק במספר הקטן, וכתוב את התוצאה במקום המנה.
7. 7 מצא את השאר וכתוב אותו במיקום המתאים באלגוריתם.
8. 8 כתוב את האלגוריתם שוב, אך (א) כתוב את המחלק הקודם כדיבידנד חדש, ו- (ב) את היתר הקודם כמחלק חדש.
9. 9 חזור על השלב הקודם עד שהשאר הוא 0.
10. 10 המחלק האחרון יהיה המחלק המשותף הגדול ביותר (GCD).
11. 11 לדוגמה, בואו למצוא את ה- GCD עבור 108 ו- 30:
12. 12 שימו לב כיצד המספרים 30 ו -18 מהשורה הראשונה יוצרים את השורה השנייה. ואז 18 ו -12 יוצרים את השורה השלישית, ו -12 ו -6 מהווים את השורה הרביעית. אין שימוש בכפלים של 3, 1, 1 ו- 2. הם מייצגים את מספר הפעמים שהדיבידנד מתחלק על ידי המחלק ולכן הם ייחודיים לכל שורה.

שיטה 2 מתוך 2: Prime Factors

1. 1 השמט כל סימני מינוס.
2. 2 מצא גורמים ראשוניים של מספרים. הציגו אותם כפי שמוצג בתמונה.
   • לדוגמה, עבור 24 ו- 18:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 x 3 x 3
   • לדוגמה, עבור 50 ו -35:
     • 50- 2 x 5 x 5
     • 35- 5 x 7
3. 3 מצא גורמי ראש משותפים.
   • לדוגמה, עבור 24 ו- 18:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 איקס 3 x 3
   • לדוגמה, עבור 50 ו -35:
     • 50 - 2 x 5 x 5
     • 35- 5 x 7
4. 4 הכפל את גורמי הפריים הנפוצים.
   • עבור 24 ו -18, הכפל 2 ו 3 וקבל 6... 6 הוא המכנה המשותף הגדול ביותר של 24 ו -18.
   • אין מה להכפיל עבור 50 ו -35. 5 הוא גורם הפריים הנפוץ היחיד, והוא ה- GCD.
5. 5 עָשׂוּי!

טיפים

• אחת הדרכים לכתוב זאת היא: דיבידנד> מחלק מוד>> שארית; GCD (a, b) = b אם mod b = 0, ו- gcd (a, b) = gcd (b, mod b) אחרת.
• כדוגמה, בואו למצוא את ה- GCD (-77.91). ראשית, השתמש ב- 77 במקום ב- -77: GCD (-77.91) הופך ל- GCD (77.91). 77 הוא פחות מ -91, לכן עלינו להחליף אותם, אך שקול כיצד האלגוריתם עובד אם לא. בעת חישוב 77 mod 91, נקבל 77 (77 = 91 x 0 + 77). מכיוון שזהו לא אפס, אנו שוקלים את המצב (ב, מוד ב), כלומר GCD (77.91) = GCD (91.77). 91 mod 77 = 14 (14 הוא השאר). זה לא אפס, ולכן GCD (91.77) הופך ל- GCD (77.14). 77 mod 14 = 7. זה לא אפס, ולכן GCD (77.14) הופך ל- GCD (14.7). 14 mod 7 = 0 (מאז 14/7 = 2 ללא שארית). תשובה: GCD (-77.91) = 7.
• השיטה המתוארת שימושית מאוד לפשט שברים. בדוגמה למעלה: -77/91 = -11/13, שכן 7 הוא המכנה המשותף הגדול ביותר של -77 ו -91.
• אם a ו- b שווים לאפס, אז כל מספר שאינו אפס הוא המחלק שלהם, כך שבמקרה זה אין GCD (המתמטיקאים פשוט מאמינים שהמחלק המשותף הגדול ביותר של 0 ו- 0 הוא 0).