האלגוריתם של אוקלידס לחישוב המחלק המשותף המרבי הוא האלגוריתם הקדום ביותר שהופיע בכתב, אף על פי שללא ספק היו כבר לבבלים שיטות לביצוע חישובים מסוגים שונים. ראשוניותו בכך שהוא עוסק במפורש במקרה הכללי, ואיננו נדרשים להסיק על הצעדים שהוא מפעיל מתוך דוגמאות בודדות.
האלגוריתם מבוסס על אבחנה יסודית: לכל formula_17, המחלקים המשותפים של formula_6 ושל formula_19 הם גם המחלקים המשותפים ל-formula_6 ול-formula_21. לפיכך, לשני הזוגות יש אותו מחלק משותף מרבי: formula_22.
כדי לחשב את המחלק המשותף המרבי של שני מספרים טבעיים formula_2 פעל באופן הבא: חלק את המספר הגדול (נאמר, formula_5), במספר הקטן, וכתוב formula_25, כאשר formula_26, אז המחלק המשותף המרבי שווה ל-formula_6. אחרת, המחלק המשותף המרבי שווה לזה של formula_6 ושל formula_19 (ומכיוון שהמספר הגדול בזוג זה קטן מן המספר הגדול בזוג הקודם, התהליך מתקדם ומגיע בהכרח אל סופו).
ידוע שמספר פעולות החילוק בהפעלת האלגוריתם אינו עולה על formula_30 (כאן formula_31 מסמן את יחס הזהב), כאשר החישוב הארוך ביותר (עבור מספרים בגודל נתון) מתרחש בחישוב המחלק המשותף המרבי של מספרי פיבונאצ'י עוקבים. מכאן שמציאת המחלק המשותף המרבי היא יעילה מבחינה חישובית; האלגוריתם פועל במהירות גם עבור מספרים גדולים, בני מאות ספרות.
דוגמה.
המחלק המשותף המרבי של 1071 ו־1029 הוא 21. נראה זאת באמצעות האלגוריתם האוקלידי:
הצגת המחלק המשותף המרבי כצירוף שלם של גורמיו.
בגרסה מורחבת מעט, מאפשר האלגוריתם האוקלידי לא רק למצוא את המחלק המשותף המרבי של שני מספרים, אלא גם להציג אותו כצירוף של מכפלות שלמות של שני המספרים, כלומר: אם formula_32 ניתן למצוא formula_33 כך ש formula_34. האבחנה המרכזית בחישוב היא האבחנה הבאה: אם formula_25, וכבר ידועה לנו הצגה של formula_36 כצירוף ליניארי formula_37, ניתן לקבל משתי המשוואות את formula_36 כצירוף ליניארי של formula_39 באמצעות הצבה פשוטה: formula_40 ולכן formula_41.
ניתן לסכם את האמור לעיל באלגוריתם הבא:
Extended_GCD(a,b)
1. if b == 0 return [a,1,0]
2. q = a/b, r = a%b
3. [d,m,n]=Extended_GCD(b,r)
4. return [d,n,m-qn]
יעילות האלגוריתם זהה בסדר הגודל שלה ליעילות האלגוריתם הפשוט; מספר האיטרציות שמבצע האלגוריתם נותר זהה, ולכל איטרציה התווספו רק חישובים בסיסיים (מציאת q, חישוב m-qn).
מחלק משותף מרבי בתחומי שלמות.
בכל חוג קומוטטיבי אפשר להגדיר מחלקים: איבר formula_5 מחלק איבר formula_6, אם קיים איבר formula_44 כך ש-formula_45. יחס החילוק שהוגדר כאן הוא קדם-סדר חלש (הוא אינו אנטי-סימטרי), ובעזרתו אפשר לדבר על "מחלק מרבי" גם בחוגים שאין בהם יחס סדר טבעי:
הגדרה זו מתלכדת עם ההגדרה הרגילה, המתאימה רק לחוג השלמים.
להגדרה הכללית יש חיסרון אחד בולט: ברוב החוגים, ישנם זוגות של איברים שאין להם מחלק משותף המרבי. בעיה אחרת היא שהמחלק המשותף המרבי, אם קיים כזה, אינו יחיד; ההגדרה מבטיחה רק ששני מחלקים משותפים מרביים לאותם שני איברים, יחלקו זה את זה (איברים המחלקים זה את זה נקראים "ידידים"). מכיוון שאיברים ידידים יוצרים את אותו אידיאל, אפשר לטפל בבעיה זו על ידי ניסוח ההגדרה בשפה של אידיאלים:
ישנם תחומי שלמות מיוחדים, שבהם תמיד קיים מחלק משותף מרבי. אחת הדוגמאות היא תחום פריקות יחידה: בחוג כזה, אפשר לכתוב כל זוג איברים formula_5 ו-formula_6 כמכפלות formula_58 ו-formula_59, כאשר formula_60 הפיכים ו-formula_61 הם ראשוניים של החוג, שאינם ידידים זה לזה. במקרה זה, המחלק המשותף המרבי הוא formula_62.
מחלקה מיוחדת יותר של חוגים הם התחומים ראשיים, המתאפיינים בכך שכל אידיאל הוא ראשי. בפרט, האידיאל הנוצר על ידי זוג איברים הוא אידיאל ראשי, והיוצר שלו הוא המחלק המשותף המרבי.
בין התחומים הראשיים, החוגים האוקלידיים מתאפיינים בכך שאפשר לבצע בהם חילוק עם שארית. אלו הם בדיוק החוגים שבהם אפשר לממש את האלגוריתם של אוקלידס שתואר לעיל.
כלי להדגמת רקורסיה.
פונקציה המממשת את האלגוריתם של אוקלידס בצורה רקורסיבית משמשת לעיתים קרובות כדי להדגים את העוצמה של שימוש ברקורסיה בתכנות. הפונקציה הבאה שמחשבת gcd מפתיעה בפשטותה, בזכות השימוש ברקורסיה. התחביר מתאים למספר שפות קרובות, ביניהן C ו-Java. ניתן לכתוב פונקציה דומה בכל שפה שתומכת ברקורסיה.
int gcd(int a, int b) {
if (b==0) return (a);
else return gcd(b, a % b);
מוח
המוח הוא האיבר הראשי במערכת העצבים, המצוי בגופם של בעלי חיים רב תאיים. תפקידו של המוח הוא לקבל מידע ממערכות החוש, לעבד אותו, ולהשתמש בו על מנת לנהל את הפעילות של מערכות הגוף השונות ואת התנהגותו של בעל החיים.
פעולת המוח.
המוח הוא בבסיסו איבר לניתוב ועיבוד של מידע. הוא מקבל מידע חושי (קלט) על גירויים בסביבה ועל מצבן של מערכות הגוף, ומוציא פקודות (פלט) שמועברות לאיברי הגוף ומווסתות את פעילותם.
צורת עיבוד המידע במוח מאפשרת לבעל החיים להתאים את עצמו לסביבה ולשפר את התגובות העתידיות לגירויים, בעזרת תהליכים של למידה. כאשר אורגניזם לומד דבר מה, ניתן למצוא ביטוי ללמידה זו בשינויים שונים החלים במוחו.
המידע במוח ובמערכת העצבים עובר בעיקר באמצעות תקשורת בין תאים הנקראים תאי עצב או נוירונים, שהם רכיבי המפתח של מערכת העצבים. תהליכי העיבוד והולכת המידע במוח מבוססים על הקישוריות בין הנוירונים, אשר נפגשים זה עם זה בנקודות המכונות סינפסות. כל תא עצב יכול ליצור סינפסות עם עשרות עד אלפי תאי עצב אחרים, בהתאם למורכבות מערכת העצבים של בעל החיים.
בתוך תא העצב המידע עובר בצורה של דחף עצבי, הנקרא גם פוטנציאל פעולה. הדחף העצבי הוא אות חשמלי הנע מגוף תא העצב לאורך סיב הקרוי אקסון. בין תאי עצב שונים (או בין תא עצב לתא מטרה אחר) מועבר המידע בסינפסה בצורה של אותות כימיים, באמצעות שחרור מולקולות המשמשות כמוליכים עצביים (נוירוטרנסמיטרים). המוליך העצבי נקשר לקולטנים על התא בצדה השני של הסינפסה. הוא גורם לשינוי במתח החשמלי של אותו תא, ובכך משפיע על דפוס הדחפים העצביים שייווצר בו ויועבר הלאה בשרשרת ההולכה העצבית.
סוגי קלט שונים שמגיעים מהסביבה דרך קולטנים חושיים (למשל גלי קול או לחץ מכני), עוברים התמרה לדחפים עצביים לפני כניסתם למוח, וכך מתאפשר ייצוג של מידע חושי על ידי רשתות של תאי עצב. המוח משתמש במידע זה על מנת להגיב לגירויים ולנהל את שלל ההיבטים של ההתנהגות.
העברתם של מסרים יוצאים, הנשלחים מתוך המוח לכיוון איברי מטרה (כגון שרירים או בלוטות מסוימות), מתבצעת דרך סינפסה בין תא עצב לתא מטרה. המוליך העצבי שחוצה את הסינפסה גורם לשינוי בתפקודם הביולוגי של התאים, ובכך משפיע על פעולת איבר המטרה.
בנוסף לתאי העצב, המוח מכיל סוגים שונים של תאי גלייה. תאים אלו מספקים הגנה ותמיכה לתאי העצב, ולעיתים ממלאים גם תפקידים בוויסות תהליכי ההולכה העצבית.
המוח בבעלי חיים ובאדם.
מערכת עצבים ומוח בחסרי חוליות.
מערכת עצבים קיימת בכל בעלי החיים למעט ספוגיים, אך בחסרי חוליות פשוטים יחסית, למשל בבני מערכת הצורבים (כמו המדוזה או ההידרה), היא מאורגנת כרשת תאי עצב (neural net) המבוזרת על פני כל הגוף, כך שאין ליצורים כאלו מוח של ממש. עם זאת, רשתות כאלו נוטות להיות צפופות יותר באזורי גוף העוסקים בחישה או בתנועה. בזרועות הציד של ההידרה, למשל, ניתן למצוא צפיפות גדולה יחסית של תאי עצב הרגישים לאור ומאפשרים לה ללכוד את טרפה. נראה כי במהלך האבולוציה אזורים צפופים כאלו התפתחו לצבירים של תאי עצב או גנגליונים, ובראשם התפתח המוח, שהוא הגנגליון הראשי והגדול ביותר. גם באדם קיימים עדיין גנגליונים רבים במערכת העצבים ההיקפית, כמו גנגליוני השדרה משני צידי חוט השדרה.
במערכות בעלי־חיים שהסתגלו לתנועה מהירה התפתחה לרוב סימטריה דו־צדדית, המאפשרת תנועה מאוזנת קדימה, ובהתאם לכך התפתחו אצלם גם מערכות עצבים סימטריות, בעלות צד ימין וצד שמאל דומים זה לזה. בבעלי־חיים כאלו גם נוטה להתפתח ריכוז של איברי חוש, כמו עיניים ואיברי הרחה, בקצה הגוף הפונה לכיוון התנועה - הראש - ובהתאם לכך גם נוטים להתפתח שם גנגליונים גדולים יותר. לדוגמה, בתולעים טבעתיות ובפרוקי-רגליים, כמו סרטנים וחרקים, מערכת העצבים מורכבת משני חוטי עצב סימטרים מחוברים זה לזה בצורת סולם, העוברים לכל אורך הגוף בצד הגחוני, מתחת למערכת העיכול. כל אחד מחוטים אלו מכיל עצבים רבים, והם מתחברים למספר גנגליונים המפוזרים לאורך הגוף, ובעיקר למוח גדול מכולם באזור הראש.
מרבית חסרי החוליות הם יצורים קטנים יחסית, ומערכת העצבים שלהם קטנה הן באופן מוחלט והן יחסית לגודל גופם. בהתאם לכך גם יכולותיהם השכליות מוגבלות לרוב לצורות פשוטות מאוד של למידה. יוצאי דופן מכלל זה הם חלק מחברי מחלקת הסילוניות, בעיקר התמנונים והדיונונים, שהמוח שלהם עשוי להתקרב בגודלו היחסי לזה של חולייתנים מתקדמים, יונקים ועופות, אף שהוא שונה מאוד בצורתו ובאופן הארגון שלו. בהתאם לכך כמה תמנונים ודיונונים מפגינים יכולות מרשימות למדי של למידה וטיפול בעצמים שונים.
המוח במיתרניים ובחולייתנים.