מחשבון מכנה משותף מקסימלי

לפני שממשיכים להגדרת המושג של המחלק המשותף הגדול ביותר (GCD), יש צורך להבין מהו מחלק משותף באופן כללי.

ידוע שלמספר שלם יכולים להיות מחלקים מרובים. אנו מעוניינים בגישה אליהם בו-זמנית על ידי מספר מספרים שלמים. אנו מחשיבים את המחלק המשותף של מספר מספרים שלמים כמספר שיכול לשמש כמחלק עבור כל מספר מהסדרה שצוינה.

לדוגמה, למספרים 8 ו-12 יש את המחלקים המשותפים הבאים: 1 ו-4. ניתן לאמת זאת בקלות על ידי כתיבת ביטויים מתמטיים: 8 = 4 ⋅ 2; 12 = 3 ⋅ 4.

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

קביעת המחלק המשותף הגדול ביותר

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

עבור שני מספרים a ו-b, המחלק המשותף הגדול ביותר הוא המספר שבו ניתן לחלק את a ו-b ללא שארית. ביטוי זה נכתב באופן הבא: gcd (a, b) = c.

דרך נוספת לכתוב GCD: (א, ב) = ג. עם זאת, ברוב המקרים, נעשה שימוש באפשרות הראשונה.

לדוגמה, למספרים 4 ו-16 יש את המחלק המשותף הגדול ביותר השווה ל-4. בוא נכתוב: gcd (4, 16) = 4.

בוא נתאר כיצד הגענו לתוצאה זו:

כתבנו את כל המחלקים של המספר 4. קיבלנו: 4, 2, 1.
לאחר מכן, צבענו את כל המחלקים של 16. קיבלנו: 16, 8, 4, 2, 1.
בחרנו מחלקים שמשותפים ל-4 וגם ל-16. קיבלנו: 4, 2, 1.
מהמחלקים המשותפים שהתקבלו, נבחר הגדול ביותר. זה 4.
אנו מקבלים את התשובה: עבור המספרים 4 ו-16 GCD הוא 4.

בדומה, אתה יכול למצוא את ה-GCD עבור שלושה מספרים שלמים או יותר. במקרה זה, זה יהיה המספר השלם הגדול ביותר שבו תוכל לחלק את כל המספרים מהסדרה המוצעת.

לדוגמה, המחלק הגדול ביותר עבור המספרים השלמים 6, 12, 18, 42 יהיה המספר 6, כלומר gcd (6, 12, 18, 42) = 6. התשובה התקבלה באמצעות אלגוריתם בדומה למה שתואר לעיל - עבור מספרים מסדרה, כל המחלקים נכתבו ברצף, ולאחר מכן נבחרו הגדולים שבהם.

מאפייני GCD

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

נכס 1

משינוי מקומות של מספרים, הערך הסופי של GCD לא ישתנה. אתה יכול לכתוב את ההצהרה הזו כך:

gcd(a, b) = gcd(b, a).

נכס 2

אם a מתחלק ב-b, אזי קבוצת המחלקים המשותפים של a ו-b זהה לקבוצת המחלקים של b. כתוב כך:

gcd(a, b) = b.

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

לדוגמה:

gcd(12, 4) = 4.

דומה:

gcd(10, 1) = 1.

נכס 3

אם a = bq + c, כאשר a, b, c ו-q הם מספרים שלמים, אז קבוצת המחלקים המשותפים של a ו-b זהה לקבוצת המחלקים המשותפים של b ו-c.

השוויון gcd (a, b) = gcd (b, c) הופך לתקף.

נכס 4

הביטוי gcd(ma, mb) = m ⋅ gcd(a,b) נכון בתנאי שm הוא מספר טבעי כלשהו.

נכס 5

נניח ש-p הוא כל מחלק משותף של a ו-b.

לאחר מכן:

gcd(a / p, b / p) = gcd(a, b) / p.

אם p = gcd(a,b), נקבל:

gcd (a / gcd (a, b), b / gcd (a, b)) = 1,

לכן, המספרים a / gcd (a, b) ו-b / gcd (a, b) הם ראשוניים.

נכס 6

לכל שני מספרים יש לפחות מחלק משותף אחד - זה המספר 1.

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

כיצד מוצאים את המכנה המשותף הגדול ביותר

מציאת המחלק המשותף הגדול ביותר (gcd) היא משימה פופולרית למדי. פעולה זו עוזרת לנו לבצע חישובים שבהם מופיעים שברים רגילים.

שיטות למציאת GCD

יש כמה טריקים כדי למצוא את המחלק המשותף הגדול ביותר. נשקול את הפופולריים שבהם.

מציאת ה-GCD עם פירוק של מספרים לגורמים ראשוניים

שיטה זו היא אחת השיטה הנפוצה ביותר בפתרון בעיות מתמטיות.

האלגוריתם לקביעת GCD עם פירוק לגורמים ראשוניים מורכב מהשלבים הבאים:

אנו מייצגים מספרים כגורמים ראשוניים. לדוגמה, ניתן לייצג את המספר 20 כמכפלה של 2 ⋅ 2 ⋅ 5.
בחר את הגורמים שיהיו בשתי ההרחבות.
מצא את המכפלה של גורמים אלה.

בואו נשקול כמה דוגמאות ליישום האלגוריתם הזה בפועל:

קבע את ה-GCD של המספרים 12 ו-8.

פרק את 12 ו-8 לגורמים ראשוניים:

12 = 2 ⋅ 2 ⋅ 3.
8 = 2 ⋅ 2 ⋅ 2.

אנו בוחנים אילו גורמים קיימים בשתי ההרחבות. מצא: 2 ו-2.

אנחנו מכפילים את הגורמים ומקבלים:

2 ⋅ 2 = 4.

תשובה: gcd (12, 8) = 4.

קבע את ה-GCD של המספרים 75 ו-150.

רצף הפתרונות דומה לדוגמה הקודמת.

בואו נציג 75 ו-150 כגורמים ראשוניים:

75 = 3 ⋅ 5 ⋅ 5.
150 = 2 ⋅ 3 ⋅ 5 ⋅ 5.

קבע את הגורמים שחוזרים על עצמם בשתי ההרחבות: 3, 5 ו-5.

אנחנו מכפילים את המספרים המתקבלים יחד: 3 ⋅ 5 ⋅ 5 = 75.

תשובה: gcd (75, 150) = 75.

קבע את ה-GCD של המספרים 9 ו-5.

דוגמה זו משתמשת במספרים ראשוניים שהמכפיל שלהם יכול להיות רק 1.

כאשר מפרקים 9 ו-5 לגורמים ראשוניים, נראה שאין להם אותם גורמים:

5 = 5.
9 = 3 ⋅ 3.

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

האלגוריתם של אוקלידס

אלגוריתם זה נקרא על שמו של המתמטיקאי היווני הקדום אוקלידס, שתיאר אותו לראשונה בכתביו (ספרים 7 ו-10 של "ההתחלות"). ידוע כי אוקלידס לא היה המחבר של האלגוריתם הזה. עם זאת, הוא נחשב לאחד האלגוריתמים העתיקים ביותר בשימוש כיום.

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

כדי למצוא GCD (a, b), אלגוריתם זה נראה כך:

אם a = 0 אז gcd(a, b) = b כי gcd(0, b) = b והאלגוריתם נעצר.
אם b = 0 אז gcd(a, b) = a כי gcd(a, 0) = a והאלגוריתם נעצר.
חלק את a ב-b עם השארית (a = b ⋅ q + r)
מצא gcd(b, r) באמצעות האלגוריתם של אוקלידס מכיוון ש-gcd(a, b) = gcd(b, r).

כדי לוודא את יעילות השיטה בפועל, שקול דוגמה.

יש צורך לקבוע את ה-GCD של המספרים 270 ו-192.

a = 270, b = 192.
a ≠ 0.
ב ≠ 0.

חלק את a ב-b, נקבל:

270 / 192 = 1 (השאר הוא 78).

תוכל לכתוב את התוצאה כ: 270 = 192 ⋅ 1 + 78.

לאחר מכן, נחשב את gcd (192, 78), שכן gcd (270, 192) = gcd (192, 78).

בוא נמשיך הלאה.

a = 192, b = 78.
a ≠ 0.
ב ≠ 0.

חלק את a ב-b, נקבל:

192 / 78 = 2 (השאר הוא 36).

ניתן לכתוב כ:

192 = 78 ⋅ 2 + 36.

חשב gcd(78, 36) מאז gcd(192, 78) = gcd(78, 36).

a = 78, b = 36.
a ≠ 0.
ב ≠ 0.

חלק את a ב-b, נקבל:

78 / 36 = 2 (השאר הוא 0).

בוא נכתוב את התוצאה כ:

78 = 36 ⋅ 2 + 6.

חשב gcd(36, 6) שכן gcd(78, 36) = gcd(36, 6).

a = 36, b = 6.
a ≠ 0.
ב ≠ 0.

חלק את A ב-B, נקבל 36 / 6 = 6 (השאר הוא 0).

כתוב את התוצאה בטופס הבא:

36 = 6 ⋅ 6 + 0.

בהמשך נמצא gcd(6, 0) שכן gcd(36, 6) = gcd(6, 0).

a = 6, b = 0.
a ≠ 0.
b = 0.

כתוצאה מכך יש לנו:

gcd(6, 0) = 6.

לכן, יש לנו את רצף החישובים הבא:

gcd(270, 192) = gcd(192, 78) = gcd(78, 36) = gcd(36, 6) = gcd(6, 0) = 6.

כתוצאה מכך, יש לנו את התשובה:

gcd(270, 192) = 6.

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

מחשבון מכנה משותף מקסימלי

כלים אחרים