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

לא מכיר כזאת

לא חושב שיש כזאת

אין כזאת נוסחה..

זה נקרא המחלק המשותף המירבי, זה קשור לתורת המספרים, המחלק המשותף המספרי של שני מספרים שלמים הוא המספר הגדול ביותר שמחלק את שניהם, בדוג' שלך אכן למספרים 10 ו- 20 המחלק המשותף המירבי הוא 10, אך זה לא בהכרח חייב להיות המספר המינימלי מבין שניהם, למשל למספרים 12 ו- 18 המחלק המשותף המירבי הוא 6, מתקיים שהמחלק המשותף המירבי של שני מספרים הוא מכפלת כל הגורמים הראשוניים המשותפים לשניהם וזה הגיוני.
בנוסף תמיד יהיה אפשר להציג את המחלק המשותף המירבי של שני המספרים כצירוף שלהם, למשל בדוגמה שלך נקבל ש-
10 = 20*0 + 10*1
יש לציין שצירוף זה לא יהיה יחיד.
הדרך הכי פשוטה לחלק את המחלק המשותף המירבי זה לפי האלגוריתם של אוקלידס ראשית יש להבין שהמחלקים המשותפים של שני מספרים a,b יהיו גם המחלקים של המספרים aq+b ו- a
לכל q
כעת כדי לחשב את המחלק המשותף המירבי של שני מספרים a,b ניקח את המספר הגדול מהשניים, נניח בלי הגבלת הכלליות שזהו a ונחלק אותו במספר הקטן b כדי למצוא את השארית נשים לב שנוכל לכתוב a = qb+r עבור r<b שזוהי השארית.
אם r = 0 אז המחלק המשותף המירבי הוא b
אחרת אם r שונה מאפס, אז המחלק המשותף המירבי שווה למחלק המשותף המירבי של b ושל r ושוב נחזור על האלגוריתם, ידוע כי r קטן מ- b ולכן נוכל לכתוב b = sr + k כאשר k<r
אם k שווה אפס אז מצאנו את המחלק המשותף המירבי, אחרת נמשיך כך עד שנקבל שהשארית היא 0 ואז מצאנו את המחלק המשותף המירבי.
אני אתן דוגמה מספרית
נמצא את המחלק המשותף המירבי של 1071 ו- 1029
נכתוב 42 + 1*1029 = 1071
פה r = 42
ולכן המחלק המשותף המירבי של 1071 ו- 1029 יהיה שווה למחלק המשותף המירבי של 1029 ושל 42
נכתוב
21 + 24*42 = 1029
השארית אינה אפס אך המחלק המשותף המירבי יהיה שווה לזה של המספרים 42 ו 21
אך מכיוון ש- 2*21 = 42
והשארית פה היא 0 אז 21 זה המחלק המירבי המשותף וכן הוא גם המחלק המשותף המירבי של שני המספרים המקוריים.
בהצלחה !