מתמטיקה בכיף  26/12/2020

 

כתבה זהבה ש.

 

על חשבון השעון – אריתמטיקה מודולרית

הייתכן שעל ידי הוספת  14 למספר 25  נקבל  9? התשובה היא שזה בהחלט אפשרי ואנו נתקלים בחישובים מעין אלה כל הזמן. אם למשל המדובר ב 25  לחודש ספטמבר שהוא כידוע בן 30 ימים, ונרצה לחשב את התאריך שיחול 14 ימים מאוחר יותר נקבל  את תאריך ה 9 לאוקטובר, למעשה מתעניינים בתוצאה שתתקבל אחרי חיסור גודל החודש 30, מתוצאת החיבור הרגיל.  נאמר כי 39 שווה (= קונגרואנטי) ל 9 מודולו 30,

25+14=39=9 (mod30)

גם חישובי עונות השנה נעשים בדומה במחזוריות של  4 N= (עונות),  וכנ"ל ימי השבוע במחזוריות של    7 N= (ימים), חשבון השעון במחזוריות של 12 N= (ו 24 שעות), לוח השנה הסולרית במחזור של   365 N= (ימים). וכמובן שחיבור זוויות המעגל נעשה אף הוא  במחזוריות  של 360 N=  . חישובים אריתמטיים כאלה מתייחסים למספרים השונים ולפעולות ביניהם ותוצאתם הסופית היא השארית המתקבלת מחילוקם ב N, גודל המחזור הנדון. כך למשל

mod 3600) ) 980 = 4580  = 2860+  1720  וגם  mod 11) ) 7 = 40  = 5 x 8,

באופן כללי מציינים   (a = b (mod n  אם מתקיים  a =  b + K.n    כש  a,  b,  n,  K   מספרים שלמים. כלומר כשהמספר a – b   הוא כפולה שלמה של המספר n  , כלומר, כש a – b   מתחלק ב n ללא שארית. למספר המחלקn  קוראים המודולוס. פעולות החשבון האלמנטריות מוגדרות מודולו n, כש n מספר טבעי.

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

(n = 0 (mod n ,  ו  (1+ n = 1 (mod n הוא איבר היחידה. ישנו גם הופכי (שלילי )  לחיבור (n – k = – k (mod n .

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

[[ המחלק המשותף המקסימלי (greatest common divisor) של המספרים שלמים a
ו b מסומן (gcd(a, b.

כאשר   1=(gcd(a, b , אין ל a  ו b גורם משותף ואומרים ש  a ו b  זרים זה לזה.

המספר c  הוא הופכי כפלי  למספר  a מודולו  c = a-1 (mod  n) n,  אם מתקיים 

     (a,c=1(mod n

באופן כללי רואים מכאן שקיים הופכי כפלי למספר a מודולו n רק כאשר ל a וn  אין גורם מחלק משותף, דהיינו נדרש שa  ו n יהיו זרים זה לזה . כאשר המודולוס – המחלק הוא מספר ראשוני , n = p  ,  יימצא הופכי כפלי לכל מספר שאינו כפולה של p ]].

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

https://gadial.net/2013/05/13/modular_arithmetic

וגם כאן

https://he.m.wikipedia.org/wiki/%D7%97%D7%A9%D7%91%D7%95%D7%9F_%D7%9E%D7%95%D7%93%D7%95%D7%9C%D7%A8%D7%99

מי שהציג את החשבון המודולרי כדיסציפלינה מתמטית והעמיק בחקר תכונותיה הוא המתמטיקאי הגרמני הדגול קרל פרידריך גאוס, K. F. Gauss , 1777-1855. הוא עשה זאת בשנת 1796 כשהיה בסה"כ בן 19.

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

סרטון 1 .  "טבלאות" לוח כפל מודולרי מונפש – וליבת המתמטיקה  

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

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

https://youtu.be/qhbuKbxJsk8

 סרטון 2 . משחקון הדגמה -בעקבות טבלאות הכפל המודולרי

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

https://www.redblobgames.com/x/1847-mathologer-modulo-circle/#N=32&M=26.867&color=angle

סרטון 3. קיצור תולדות חייו של גאוס – נסיך המתמטיקה

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

יש לסרטון תרגום אוטומטי לאנגלית.

https://youtu.be/Pqh9CK7wBZo

 

סרטון 4.  עוד על נסיך המתמטיקה וחידת 1 עד 1000000

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

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

https://youtu.be/Dd81F6-Ar_0