מחלק משותף מקסימלי
מחלק משותף מרבי הוא המספר הגדול ביותר שמחלק שני מספרים בלי שארית. לדוגמה, המחלק המשותף המרבי של 12 ו‑18 הוא 6. אם לשני מספרים יש את אותם גורמים ראשוניים (מספרים שאי אפשר לחלק אותם עוד), המשותף ביניהם נותן את ה‑gcd. אם אין גורם משותף גדול מ‑1, קוראים להם זרים (אין להם מחלק משותף גדול). אין צורך לפר...
P (מחלקת סיבוכיות)
P היא קבוצה של בעיות שאפשר לפתור בצורה "מהירה" יחסית. "מהירה" כאן פירושו זמן פולינומי. זמן פולינומי אומר שהזמן גדל בצורה לא מוגזמת כשהקלט גדל. דוגמאות פשוטות ב-P הן חישוב המחלק המשותף הגדול של שני מספרים (GCD) ועץ פורש מינימלי. גם בדיקת האם מספר הוא ראשוני נכנסה ל-P בשנת 2002. בחירת זמן פולינומי ש...
כפולה משותפת מינימלית
כפולה משותפת מינימלית היא המספר החיובי הקטן ביותר ששני מספרים מתחלקים בו. דוגמה קצרה: הכפולה המשותפת של 21 ו-6 היא 42. איך מוצאים את זה? יש שתי דרכים עיקריות. אפשר לפרק מספרים למספרים ראשוניים. מספר ראשוני הוא מספר שמתחלק רק ב-1 ובעצמו. אפשר גם להכפיל את שני המספרים ולחלק ב"המחלק המשותף הגדול ביות...
מחלק
מספר a הוא מחלק של מספר b אם יש מספר שלם c כך ש‑b=a·c. זה אומר שהחלוקה של b ב‑a לא נותנת שארית. דוגמה פשוטה: 5 מחלק את 35 כי 35=5·7. אבל 5 לא מחלק את 33. חוקים קצרים: אם a מחלק b וגם b מחלק c אז a מחלק גם את c. כל מספר מחלק את עצמו. אפס מחלק אפס אבל חלוקה ב‑0 אינה נכונה. לכל מספר טבעי יש מספר מס...