דוגמאות למציאת המחלק הפחות משותף. מציאת הכפולה הכי פחות משותפת, שיטות, דוגמאות למציאת ה-LCM

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

מושגי יסוד

המחלק של מספר X שלם הוא מספר Y אחר המחלק את X ללא שארית. לדוגמה, המחלק של 4 הוא 2, ו-36 הוא 4, 6, 9. כפולה שלמה של X היא המספר Y שמתחלק ב-X ללא שארית. לדוגמה, 3 הוא כפולה של 15, ו-6 הוא 12.

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

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

מציאת GCD

ישנן שיטות רבות למציאת המחלק המשותף הגדול ביותר, המפורסמות שבהן הן:

• ספירה רציפה של מחלקים, בחירת המשותף לזוג וחיפוש הגדול שבהם;
• פירוק מספרים לגורמים בלתי ניתנים לחלוקה;
• האלגוריתם של אוקלידס;
• אלגוריתם בינארי.

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

מציאת ה-NOC

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

LCM (X, Y) = X × Y / GCD (X, Y).

לדוגמה, אם GCD (15.18) = 3, אז LCM (15.18) = 15 × 18/3 = 90. הדוגמה הברורה ביותר לשימוש ב-LCM היא מציאת מכנה משותף, שהוא הכפולה הפחות משותפת עבור שברים נתונים.

מספרים ראשוניים הדדיים

אם לזוג מספרים אין מחלקים משותפים, אז זוג כזה נקרא קו-פריים. GCD עבור זוגות כאלה תמיד שווה לאחד, ובהתבסס על החיבור בין מחלקים ומכפילים, ה-LCM עבור coprime שווה למכפלה שלהם. לדוגמה, המספרים 25 ו-28 הם ראשוניים יחסית, מכיוון שאין להם מחלקים משותפים, וה-LCM (25, 28) = 700, המתאים למכפלתם. כל שני מספרים בלתי ניתנים לחלוקה יהיו תמיד ראשוניים הדדיים.

מחלק משותף ומחשבון מרובה

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

דוגמאות מהחיים האמיתיים

מכנה משותף של שברים

הכפולה הפחות משותפת משמשת למציאת המכנה המשותף של שברים מרובים. נניח שבבעיה אריתמטית נדרש לסכם 5 שברים:

1/8 + 1/9 + 1/12 + 1/15 + 1/18.

כדי להוסיף שברים, יש לצמצם את הביטוי למכנה משותף, שמצטמצם לבעיה של מציאת ה-LCM. לשם כך, בחר 5 מספרים במחשבון והזן את ערכי המכנים בתאים המתאימים. התוכנית תחשב את LCM (8, 9, 12, 15, 18) = 360. כעת עליך לחשב את הגורמים הנוספים עבור כל שבר, המוגדרים כיחס בין LCM למכנה. לפיכך, גורמים נוספים ייראו כך:

• 360/8 = 45
• 360/9 = 40
• 360/12 = 30
• 360/15 = 24
• 360/18 = 20.

לאחר מכן, נכפיל את כל השברים בגורם הנוסף המתאים ונקבל:

45/360 + 40/360 + 30/360 + 24/360 + 20/360.

אנחנו יכולים בקלות לסכם שברים כאלה ולקבל את התוצאה בצורה 159/360. אנחנו מצמצמים את השבר ב-3 ורואים את התשובה הסופית - 53/120.

פתרון משוואות דיופנטיות לינאריות

משוואות דיופנטיות לינאריות הן ביטויים של הצורה ax + by = d. אם היחס d / gcd (a, b) הוא מספר שלם, אז המשוואה ניתנת לפתרון במספרים שלמים. בואו נבדוק כמה משוואות לפתרונות של מספרים שלמים. ראשית, בדוק את המשוואה 150x + 8y = 37. בעזרת המחשבון, מצא את ה-GCD (150.8) = 2. חלקו 37/2 = 18.5. המספר אינו מספר שלם, לכן, למשוואה אין שורשים שלמים.

בוא נבדוק את המשוואה 1320x + 1760y = 10120. השתמש במחשבון כדי למצוא את ה-GCD (1320, 1760) = 440. נחלק 10120/440 = 23. כתוצאה מכך, אנו מקבלים מספר שלם, לכן, המשוואה הדיופנטית היא פתלת ה מקדמים.

סיכום

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

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

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

אנחנו מקבלים

• 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48.
• 36: 1, 2, 3, 4, 6, 9, 12, 18, 36.

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

הגורמים הנפוצים הם: 1, 2, 3, 4, 6, 12.

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

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

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

• הגדול ביותר מספר טבעי, שבו שני מספרים a ו-b מתחלקים ללא שארית, נקרא המחלק המשותף הגדול ביותר של המספרים הללו.

לפעמים הקיצור GCD משמש לקיצור הרשומה.

לכמה זוגות של מספרים יש אחד כגורם המשותף הגדול ביותר שלהם. מספרים כאלה נקראים מספרים ראשוניים הדדיים.לדוגמה, מספרים 24 ו-35. יש GCD = 1.

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

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

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

• 48 = 2*2*2*2*3,
• 36 = 2*2*3*3.

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

• 48 = 2*2*2*2*3 ,
• 36 = 2*2*3 *3.

הגורמים 2, 2 ו-3 יישארו. התוצר שלהם הוא 12. מספר זה יהיה המחלק המשותף הגדול ביותר של 48 ו-36.

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

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

• 1. פירוק מספרים לגורמים ראשוניים.
• 2. מהגורמים הכלולים בפירוק של אחד מספרים אלו, מחק את אלו שאינם נכללים בפירוק של מספרים אחרים.
• 3. חשב את המכפלה של הגורמים הנותרים.

ניתן לצמצם את מציאת המחלק המשותף הגדול ביותר של שלושה מספרים או יותר לממצא הרציף של ה-GCD של שני מספרים. הזכרנו זאת כאשר חקרנו את המאפיינים של GCD. שם ניסחנו והוכחנו את המשפט: המחלק המשותף הגדול ביותר של מספר מספרים a 1, a 2,…, a kשווה למספר ד ק, שנמצא בחישוב הרציף GCD (a 1, a 2) = d 2, GCD (d 2, a 3) = d 3, GCD (d 3, a 4) = d 4, …,GCD (d k-1, a k) = d k.

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

דוגמא.

מצא את המחלק המשותף הגדול ביותר של ארבעה מספרים 78 , 294 , 570 ו 36 .

פִּתָרוֹן.

בדוגמה זו a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.

ראשית, באמצעות האלגוריתם האוקלידי, אנו קובעים את המחלק המשותף הגדול ביותר ד 2שני המספרים הראשונים 78 ו 294 ... כאשר מחלקים, אנו משיגים את השוויון 294 = 78 3 + 60; 78 = 60 1 + 18;60 = 18 3 + 6ו 18 = 6 3... בדרך זו, d 2 = gcd (78, 294) = 6.

עכשיו בואו נעשה חישוב d 3 = gcd (d 2, a 3) = gcd (6, 570)... בואו ניישם שוב את האלגוריתם של אוקלידס: 570 = 6 · 95, ומכאן, d 3 = gcd (6, 570) = 6.

נשאר לחשב d 4 = gcd (d 3, a 4) = gcd (6, 36)... כי 36 מחולק ב 6 , לאחר מכן d 4 = gcd (6, 36) = 6.

לפיכך, המחלק המשותף הגדול ביותר מבין ארבעת המספרים הללו הוא d 4 = 6, זה, GCD (78, 294, 570, 36) = 6.

תשובה:

GCD (78, 294, 570, 36) = 6.

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

דוגמא.

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

פִּתָרוֹן.

הרחב את המספרים 78 , 294 , 570 ו 36 לפי גורמים ראשוניים, אנחנו מקבלים 78 = 2 3 13,294 = 2 3 7 7, 570 = 2 3 5 19, 36 = 2 2 3 3... הגורמים הראשוניים המשותפים של כל ארבעת המספרים הללו הם המספרים 2 ו 3 ... לָכֵן, GCD (78, 294, 570, 36) = 2 3 = 6.

תשובה:

GCD (78, 294, 570, 36) = 6.

חזרה לראש העמוד

מציאת gcd למספרים שליליים

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

דוגמא.

מצא את ה-gcd של מספרים שלמים שליליים −231 ו −140 .

פִּתָרוֹן.

הערך המוחלט של מספר −231 שווה ל 231 , ומודול המספר −140 שווה ל 140 , ו GCD (-231, -140) = GCD (231, 140)... האלגוריתם של אוקלידס נותן לנו את השוויון הבא: 231 = 140 1 + 91; 140 = 91 1 + 49; 91 = 49 1 + 42; 49 = 42 1 + 7ו 42 = 7 6... לָכֵן, GCD (231, 140) = 7... ואז המחלק המשותף הגדול ביותר המבוקש של מספרים שליליים −231 ו −140 שווה ל 7 .

תשובה:

GCD (-231, -140) = 7.

דוגמא.

קבע את ה-gcd של שלושה מספרים −585 , 81 ו −189 .

פִּתָרוֹן.

כשמוצאים את המחלק המשותף הגדול ביותר, ניתן להחליף מספרים שליליים בערכים מוחלטים, כלומר, GCD (-585, 81, -189) = GCD (585, 81, 189)... פירוק של מספרים 585 , 81 ו 189 לפי גורמים ראשוניים הם, בהתאמה, מהצורה 585 = 3 3 5 13, 81 = 3 3 3 3ו 189 = 3 3 3 7... הגורמים הראשוניים המשותפים של שלושת המספרים הללו הם 3 ו 3 ... לאחר מכן GCD (585, 81, 189) = 3 3 = 9, ומכאן, GCD (-585, 81, -189) = 9.

תשובה:

GCD (-585, 81, -189) = 9.

35. השורשים של הפולינום. המשפט של בזוט. (33 ומעלה)

36. ריבוי שורשים, קריטריון של ריבוי שורשים.

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

Yandex.RTB R-A-339285-1

מה הם מחלקים משותפים

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

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

הגדרה 1

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

דוגמה 1

הנה דוגמאות למחלק כזה: שלוש יהיה מחלק משותף למספרים - 12 ו-9, מכיוון שהשוויון 9 = 3 · 3 ו- 12 = 3 · (- 4) נכונים. למספרים 3 ו-12 יש גורמים משותפים נוספים, כגון 1, -1 ו-3. ניקח דוגמה נוספת. לארבעת המספרים השלמים 3, - 11, - 8 ו- 19 יהיו שני גורמים משותפים: 1 ו- 1.

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

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

מהו המחלק המשותף הגדול ביותר (GCD)

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

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

נעבור לניסוח ההגדרה העיקרית.

הגדרה 2

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

בכתב, המחלק המשותף הגדול ביותר מסומן לרוב על ידי הקיצור GCD. עבור שני מספרים, זה יכול להיכתב כ-GCD (a, b).

דוגמה 2

מהי דוגמה ל-GCD לשני מספרים שלמים? לדוגמה, עבור 6 ו-15 זה יהיה 3. תן לנו להצדיק את זה. ראשית, נכתוב את כל המחלקים של שישה: ± 6, ± 3, ± 1, ולאחר מכן את כל המחלקים של חמישה עשר: ± 15, ± 5, ± 3 ו-± 1. לאחר מכן אנו בוחרים את הכללים: אלה הם - 3, - 1, 1 ו-3. יש לבחור מתוכם את המספר הגדול ביותר. זה יהיה 3.

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

הגדרה 3

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

עבור מספרים a 1, a 2,..., a n, נוח לסמן את המחלק כ-GCD (a 1, a 2,..., a n). ערך המחלק עצמו נכתב כ-GCD (a 1, a 2,..., a n) = b.

דוגמה 3

להלן דוגמאות למחלק המשותף הגדול ביותר של מספר מספרים שלמים: 12, - 8, 52, 16. זה יהיה שווה לארבע, מה שאומר שאנחנו יכולים לכתוב ש-GCD (12, - 8, 52, 16) = 4.

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

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

דוגמה 4

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

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

מאפיינים בסיסיים של gcd והאלגוריתם של אוקלידס

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

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

הגדרה 4

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

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

הגדרה 5

אם ניתן לחלק את המספר a במספר b, אזי קבוצת המחלקים המשותפים של שני המספרים הללו תהיה דומה לקבוצת המחלקים של המספר b, כלומר GCD (a, b) = b.

הבה נוכיח את האמירה הזו.

הוכחה 1

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

באמצעות תכונה זו, נוכל למצוא את המחלק המשותף הגדול ביותר של שני מספרים אם ניתן לחלק את אחד מהם בשני. מחלק כזה שווה לאחד משני המספרים הללו, שבאמצעותו ניתן לחלק את המספר השני. לדוגמה, GCD (8, 24) = 8, שכן 24 הוא כפולה של שמונה.

הגדרה 6 הוכחה 2

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

הגדרה 7

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

לפני ניסוח המאפיין, אנו ממליצים לך לחזור על המשפט שהוכחנו במאמר על חלוקה עם השארית. לפיו ניתן לייצג את המספר המתחלק a כ-bq + r, כאשר b הוא מחלק, q הוא מספר שלם כלשהו (הוא נקרא גם מנה לא שלמה), ו-r הוא שארית המקיימת את התנאי 0 ≤ r ≤ b .

נניח שיש לנו שני מספרים שלמים גדולים מ-0, שעבורם יתקיימו השוויון הבא:

a = b q 1 + r 1, 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1

השוויון הזה מסתיים כאשר r k + 1 הופך ל-0. זה יקרה בלי להיכשל, שכן הרצף b> r 1> r 2> r 3, ... הוא סדרה של מספרים שלמים יורדים, שיכולים לכלול רק מספר סופי מהם. לפיכך, r k הוא המחלק המשותף הגדול ביותר של a ו-b, כלומר r k = gcd (a, b).

קודם כל צריך להוכיח ש-r k הוא מחלק משותף של המספרים a ו-b, ואחרי זה - ש-r k הוא לא רק מחלק, אלא המחלק המשותף הגדול ביותר מבין שני מספרים נתונים.

בואו נסתכל על רשימת השוויון למעלה, מלמטה למעלה. לפי השוויון האחרון,
r k - 1 ניתן לחלק ב- r k. בהתבסס על עובדה זו, כמו גם התכונה המוכחת הקודמת של המחלק המשותף הגדול ביותר, ניתן לטעון שניתן לחלק את r k - 2 ב- r k, שכן
r k - 1 מתחלק ב- r k ו- r k מתחלק ב- r k.

השוויון השלישי מלמטה מאפשר לנו להסיק שניתן לחלק את r k - 3 ב- r k וכן הלאה. השני מלמטה הוא ש-b מתחלק ב-r k, והראשון הוא ש-a מתחלק ב-r k. מכל זה אנו מסיקים ש-r k הוא מחלק משותף של a ו-b.

כעת נוכיח כי r k = gcd (א, ב). מה אני צריך לעשות? הראה שכל מחלק משותף של a ו-b יחלק את r k. נסמן אותו ב-r 0.

בואו נסתכל על אותה רשימה של שוויון, אבל מלמעלה למטה. בהתבסס על המאפיין הקודם, אנו יכולים להסיק ש-r 1 מתחלק ב-r 0, כלומר, לפי השוויון השני, r 2 מתחלק ב-r 0. אנחנו יורדים למטה את כל השוויון ומהאחרונים נסיק ש-r k מתחלק ב-r 0. לכן, r k = gcd (א, ב).

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

נעבור לנכסים אחרים.

הגדרה 8

אם a ו-b הם מספרים שלמים שאינם שווים ל-0, אז חייבים להיות שני מספרים שלמים אחרים u 0 ו-v 0 שעבורם השוויון GCD (a, b) = a u 0 + b v 0 יהיה תקף.

השוויון שניתן בהצהרת המאפיין הוא הייצוג הליניארי של המחלק המשותף הגדול ביותר של a ו-b. זה נקרא יחס בזוט, והמספרים u 0 ו- v 0 נקראים מקדמי בזוט.

הוכחה 3

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

a = b q 1 + r 1, 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1

השוויון הראשון אומר לנו ש r 1 = a - b q 1. נסמן 1 = s 1 ו - q 1 = t 1 ונכתוב את השוויון הזה כ- r 1 = s 1 a + t 1 b. כאן המספרים s 1 ו-t 1 יהיו מספרים שלמים. השוויון השני מאפשר לנו להסיק שr 2 = b - r 1 q 2 = b - (s 1 a + t 1 b) q 2 = - s 1 q 2 a + (1 - t 1 q 2) ב. נסמן - s 1 q 2 = s 2 ו- 1 - t 1 q 2 = t 2 ונכתוב מחדש את השוויון כ-r 2 = s 2 a + t 2 b, כאשר s 2 ו-t 2 יהיו גם מספרים שלמים. הסיבה לכך היא שסכום המספרים השלמים, המכפלה וההפרש שלהם הם גם מספרים שלמים. בדיוק באותו אופן נקבל מהשוויון השלישי r 3 = s 3 a + t 3 b, מהבאים r 4 = s 4 a + t 4 b וכו'. לבסוף, אנו מסיקים כי r k = s k a + t k b עבור מספר שלם s k ו- t k. מכיוון ש-rk = gcd (a, b), נסמן sk = u 0 ו-tk = v 0, כתוצאה מכך, נוכל לקבל ייצוג ליניארי של gcd בצורה הנדרשת: gcd (a, b) = au 0 + bv 0.

הגדרה 9

Gcd (m a, m b) = m gcd (a, b) עבור כל ערך טבעי M.

הוכחה 4

ניתן לבסס נכס זה באופן הבא. מכפילים את שני הצדדים של כל שוויון באלגוריתם של אוקלידס במספר m, נקבל ש-GCD (m a, m b) = m r k, ו-r k הוא GCD (a, b). לפיכך, gcd (m a, m b) = m gcd (a, b). תכונה זו של המחלק המשותף הגדול ביותר היא המשמשת למציאת ה-GCD בשיטת הפירוק הראשוני.

הגדרה 10

אם למספרים a ו-b יש מחלק משותף p, אז 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 = p (a: p) ו-b = p (b: p), אז, בהתבסס על המאפיין הקודם, אתה יכול ליצור שוויון בצורת GCD (a, b) = GCD (p (a: p), p (B: p)) = p gcd (a: p, b: p), שביניהם תהיה הוכחה של נכס זה... אנו משתמשים בהצהרה זו כאשר אנו נותנים שברים נפוציםלצורה בלתי ניתנת לצמצום.

הגדרה 11

המחלק המשותף הגדול ביותר a 1, a 2, ..., ak יהיה המספר dk, אותו ניתן למצוא על ידי חישוב רציף של GCD (a 1, a 2) = d 2, GCD (d 2, a 3) = d 3, GCD (d 3, a 4) = d 4,…, gcd (dk - 1, ak) = dk.

מאפיין זה שימושי למציאת המחלק המשותף הגדול ביותר של שלושה מספרים או יותר. ניתן להשתמש בו כדי לצמצם פעולה זו לפעולות עם שני מספרים. הבסיס שלו הוא תוצאה של האלגוריתם האוקלידי: אם קבוצת המחלקים המשותפים a 1, a 2 ו-3 חופפים לקבוצה d 2 ו- 3, אז היא חופפת למחלקים d 3. המחלקים של המספרים a 1, a 2, a 3 ו- 4 יתאימו למחלקים של d 3, כלומר הם יחפפו גם למחלקים של d 4 וכן הלאה. בסופו של דבר, נקבל שהמחלקים המשותפים של המספרים a 1, a 2,..., ak עולים בקנה אחד עם המחלקים של dk, ומכיוון שהמחלק הגדול ביותר של המספר dk יהיה המספר הזה עצמו, אז GCD (a 1, a 2,…, ak) = d k.

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

אם אתה מבחין בשגיאה בטקסט, אנא בחר אותה והקש Ctrl + Enter

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

ניווט בדף.

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

שימו לב שאם היינו פונים לטבלת הראשוניים כבר מההתחלה, היינו מגלים שהמספרים 661 ו-113 הם ראשוניים, שמהם אפשר לומר מיד שהמחלק המשותף הגדול ביותר שלהם הוא 1.

תשובה:

GCD (661, 113) = 1.

מציאת gcd על ידי פירוק מספרים לגורמים ראשוניים

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

בואו ניתן דוגמה כדי להבהיר את הכלל למציאת GCD. תן לנו לדעת את הפירוק של המספרים 220 ו-600 לגורמים ראשוניים, יש להם את הצורה 220 = 2 · 2 · 5 · 11 ו-600 = 2 · 2 · 2 · 3 · 5 · 5. הגורמים הראשוניים הנפוצים המעורבים בפירוק המספרים 220 ו-600 הם 2, 2 ו-5. לכן, GCD (220, 600) = 2 2 5 = 20.

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

שקול דוגמה למציאת GCD לפי הכלל המוצהר.

דוגמא.

מצא את המכנה המשותף הגדול ביותר של 72 ו-96.

פִּתָרוֹן.

בואו נחלק את המספרים 72 ו-96 לגורמים ראשוניים:

כלומר, 72 = 2 2 2 3 3 ו- 96 = 2 2 2 2 2 2 3. גורמים ראשוניים נפוצים הם 2, 2, 2 ו-3. לפיכך, GCD (72, 96) = 2 2 2 3 = 24.

תשובה:

GCD (72, 96) = 24.

לסיכום נקודה זו, נציין כי תוקפו של הכלל הנ"ל למציאת ה-GCD נובע מהמאפיין של המחלק המשותף הגדול ביותר, הקובע כי GCD (m a 1, m b 1) = m GCD (a 1, b 1), כאשר m הוא כל מספר שלם חיובי.

מציאת GCD של שלושה מספרים או יותר

ניתן לצמצם את מציאת המחלק המשותף הגדול ביותר של שלושה מספרים או יותר לממצא הרציף של ה-GCD של שני מספרים. הזכרנו זאת כאשר חקרנו את המאפיינים של GCD. שם ניסחנו והוכחנו את המשפט: המחלק המשותף הגדול ביותר של מספר מספרים a 1, a 2, ..., ak שווה למספר dk, שנמצא בחישוב הרציף של GCD (a 1, a 2) = d 2, GCD (d 2, a 3) = d 3, GCD (d 3, a 4) = d 4,..., GCD (d k-1, ak) = dk.

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

דוגמא.

מצא את הגורם המשותף הגדול ביותר מבין ארבעת המספרים 78, 294, 570 ו-36.

פִּתָרוֹן.

בדוגמה זו, a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.

ראשית, באמצעות האלגוריתם האוקלידי, אנו קובעים את המחלק המשותף הגדול ביותר d 2 מבין שני המספרים הראשונים 78 ו-294. כאשר מחלקים, נקבל שוויון 294 = 78 · 3 + 60; 78 = 60 1 + 18; 60 = 18 3 + 6 ו-18 = 6 3. לפיכך, d 2 = gcd (78, 294) = 6.

עכשיו בואו נעשה חישוב d 3 = gcd (d 2, a 3) = gcd (6, 570)... שוב אנו מיישמים את האלגוריתם של אוקלידס: 570 = 6 · 95, לכן, d 3 = GCD (6, 570) = 6.

נשאר לחשב d 4 = gcd (d 3, a 4) = gcd (6, 36)... מכיוון ש-36 מתחלק ב-6, אז d 4 = GCD (6, 36) = 6.

לפיכך, המחלק המשותף הגדול ביותר מבין ארבעת המספרים הללו הוא d 4 = 6, כלומר GCD (78, 294, 570, 36) = 6.

תשובה:

GCD (78, 294, 570, 36) = 6.

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

דוגמא.

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

פִּתָרוֹן.

נרחיב את המספרים 78, 294, 570 ו-36 לגורמים ראשוניים, נקבל 78 = 2 3 13, 294 = 2 3 7 7, 570 = 2 3 5 19, 36 = 2 2 3 3. הגורמים הראשוניים המשותפים של כל ארבעת המספרים הללו הם 2 ו-3. לָכֵן, GCD (78, 294, 570, 36) = 2 3 = 6.