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

אודות מחשבון זה

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

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