00
עדכונים

מנוי במייל

קבלת עדכונים על רשומות חדשות ישירות לתיבת האמייל
יש להזין אימייל תקין על מנת להרשם לעדכונים
ברגעים אלו נשלח אליך אימייל לאישור/ביטול ההרשמה
*שים/י לב, מרגע עשית מנוי, כותב/ת הבלוג יוכל לראות את כתובת האמייל שלך ברשימת העוקבים.
X

{ [ ( בניית עזר ) ] } - מתמטיקה, תכנות, סיכומים לבחינות הבגרות ואקסל

<<<<
 
   מתמטיקה 
   ונושאים 
   נוספים 
 
משפטים, נוסחאות ומתמטיקאים על ציר הזמן  תורת המספרים  תכנות C++/C  קומבינטוריקה  מתמטיקה/EXCEL  אסטרונומיה

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

המשפט הקטן של פרמה ומספרי קרמייקל- סקירה מתמטית מאת אהרן מוריאלי

* המאמר באדיבותו של הסופר אהרן מוריאלי.
 

המשפט הקטן של פרמה

לפני שנציג משפט זה, ראוי לעמוד על שיקול דעתם האפשרית של אנשים בפתירת בעיה עתיקת יומין שהעסיקה מתמטיקאים סינים לפני כ-2500 שנה. ננסח את הבעיה כך: מה צריך להיות טיבו של n כדי שיחלק את הביטוי   2n-2  ? נניח שבחרנו להציב את המספר 7 במקום n, התוצאה תהיה 126=2-‏27, ומספר זה מתחלק ל-7. אם נציב 5 במקום n, נקבל את המספר 30, שמתחלק ל-5, ואם נציב 11, נקבל 2046, שמתחלק ב-11. כעת, נציב במקום n את המספרים: 4, 6 ו-8. המספרים שיתקבלו לא יתחלקו במספרים אלה. לאור תוצאות אלה נוכל אולי להגיע למסקנה שאם נציב במקום n מספרים אי-זוגיים הביטוי יהיה בר-חלוקה, ואם נציב מספרים זוגיים הוא לא יהיה כן. כעת, כדי להיות בטוח בנכונות המסקנה נציב במקום n את המספר 9, והנה להפתעתנו המספר 510 אינו מתחלק ב-9. גם המספר 32766 אינו מתחלק ב-15 במקרה שנציב 15 במקום n. כאן נצטרך לעיין מחדש בנתונים שבידנו: הכלל מתקיים אם מציבים במקום n את המספרים 2, 5, 7, ו-11, אבל הוא לא מתקיים אם נציב את המספרים: 4, 6, 8, 9, ו-15. לכאורה, המסקנה נראית ברורה: הכלל מתקיים אך ורק אם n הוא מספר ראשוני. אם יהיה לנו זמן ונהיה מאוד סקרנים, נציב למשל את המספרים לפי הסדר מ-16 עד 25, ואז ניווכח שהכלל אכן מתקיים לגבי המספרים 17, 19 ו-23 ואינו מתקיים לגבי שאר המספרים, שהם פריקים כולם.

 

ואכן כך חשבו המתמטיקאים הסינים מלפני דורות רבים. הם שיערו ש-2p-2 יתחלק ב-p, אם p הוא מספר ראשוני, אבל אם p הוא מספר פריק אזי הוא לא יתחלק בו לעולם! בפועל, הכלל נכון כאשר 340 p, אבל הוא גם נכון לגבי 341=p, שהוא מספר פריק: 341=11*31. וכך נמצאה ההשערה הסינית (כך היא נודעת בספרי המתמטיקהChinese hypothesis ) נכונה רק לגבי החלק הראשון שלה, ולא נכונה לגבי החלק השני. זה נתגלה בשנת 1819 על ידי המתמטיקאי הצרפתי פייר סַרוס (Sarrus 1861-1798). כיום אפשר להבין את טעותם של הסינים: המספר 341 הוא המספר הפריק הקטן ביותר שהחלק השני של הכלל מדבר בו. באמצעים שהיו להם אז קשה היה להם לחשב את המספר 2341, שהוא מספר עצום בגודלו. מסתבר שמספר זה התנהג כאילו היה מספר ראשוני, הוא "התחזה" למספר ראשוני בכך שהוא קיים את הנוסחה הנ"ל על אף העובדה שהוא מספר פריק, ולכן הוא כונה על-ידי מתמטיקאים של ימינו בשם מספר פסאודו-ראשוני. כמאה שנים לאחר מכן, בשנת 1926, פרסם המתמטיקאי פול פּוּלֶה Poulet טבלה של מספרים פסאודו ראשוניים כאלה (נזכור! מדובר רק על בסיס 2) בתחום 50 מיליון המספרים הראשונים, ובשנת 1938 הוא שכלל את הטבלה לתחום מאה מיליון. על כן קוראים המתמטיקאים כיום למספרים אלה בשם מספרי סַרוס או מספרי פולה. מספרים אלה הם נדירים למדיי. בתוך האלף הראשון יש 3 מספרים כאלה (341, 561 ו-645 ראה טבלה מס' 1) בהשוואה ל-168 מספרים ראשוניים הקיימים בתחום זה; ובתחום המיליון הראשון יש 245 מספרים כאלה בעוד שבתחום זה יש 78,498 מספרים ראשוניים (ראה טבלה בסעיף "התפלגותם של מספרים ראשוניים" בפרק על המספרים הראשוניים).

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

 

לפני שנמשיך בדיון נזכיר לקורא את טענה 30 שבפרק השביעי של הספר יסודות מאת אויקלידס, שהוזכרה בפרק שלנו על המספרים הראשוניים. הטענה נוסחה כך: אם מספר ראשוני כלשהו מחלק את מכפלת המספרים m ו-n, אזי מספר זה מחלק לפחות אחד משני המספרים הנ"ל.משפט זה נכון גם אם המספר מורכב ממכפלה של יותר משני גורמים. כעת נוכל להמשיך: נפרק את הנוסחה xp-x לגורמים, נוציא את x מחוץ לסוגריים ונקבל  (x(xp-1-1 .  ביטוי זה מתחלק, לפי הטענה, ב-p. אם נניח ש-x אינו כפולה של p, אזי הוא לא יתחלק ב-p. אבל אם נאמר כבר ש-p מחלק את כל הביטוי אבל לא את x, הרי הוא יחלק בהכרח את הביטוי 1-xp-1. וכך הגענו אל המשפט הקטן  של פרמה.

 

במכתב שכתב פרמה בשנת 1640 לחברו פרניקל דה בסי, גם הוא מתמטיקאי צרפתי חובב כפרמה, הוא הציג בפניו את המשפט, שנודע מאוחר יותר בכינוי המשפט הקטן של פרמה, להבחינו מהמשפט הגדול או האחרון שלו, שבו דנו במאמר המשפט האחרון של פרמה". המשפט אומר ש"אם x הוא מספר שאינו מתחלק למספר הראשוני p (את התנאי הזה ביקשנו להבליט בפסקה הקודמת), אזי הביטוי  xp-1-1חייב להתחלק ב-p ללא שארית". או בניסוח אחר: הביטוי xp-1 ישאיר 1 בהתחלקו ל-p. פרמה, כדרכו, לא סיפק הוכחה למשפטו, ונימוקו: "הייתי שולח לך את ההוכחה לולא חששתי מאריכותה". הראשון שהוכיח את המשפט היה המתמטיקאי והפילוסוף הגרמני לייבניץ, אלא שהוכחה זו נעלמה מעיני החוקרים, מפני שלייבניץ כתב אותה על מסמך לא מתוארך (אבל ידוע שהוא נכתב בוודאות לפני שנת 1683), והוא פשוט לא מצא לנכון לפרסם אותה. מסמך זה נתגלה רק בשנת 1806 - לאחר שאוילר כבר פרסם את ההוכחה למשפט והיא נקראת על שמו. ההוכחה הופיעה בסיכומי הדיונים שיצאו לאור בשנת 1736 מטעם אקדמיית סנט פיטרסברג. מאוחר יותר, בשנת 1760, פרסם אוילר גרסה כללית יותר של המשפט.

 

לו משפט זה היה נכון לגבי מספרים ראשוניים בלבד, אזי היה בידינו כלי נוח לזיהוי מספרים ראשוניים. למרבה הצער לא נותן המשפט בידינו כלי כזה. המשפט אמנם נכון תמיד לגבי מספרים ראשוניים, אבל, מאידך,  הוא לפעמים נכון גם לגבי מספרים פריקים. במילים אחרות ייתכן שיתקיים  nשיחלק את הביטוי 1-xn-1 גם אם n אינו מספר ראשוני. הראשון שגילה זאת היה, כזכור, פייר סרוס בשנת 1819. מספר המספרים הפריקים האלה שיקיימו את המשפט הוא אינסופי. כן אנו מוצאים שלכל בסיס x יכולים להופיע כמה מספרים פריקים שמקיימים את המשפט. הטבלה הבאה ממחישה זאת. אנו רושמים בטבלה את ששת המספרים הפסאודו-ראשוניים הראשונים לבסיסים 6-2 של x:

הבסיס x              המספרים הפסאודו-ראשוניים הראשונים השייכים לו   

2                          341, 561, 645, 1105, 1387, 1729, ...

3                          91, 121, 286, 671, 703, 949, ...

4                          15, 85, 91, 341, 435, 451, ...

5                          4, 124, 217, 561, 781, 1541, ...

6                          35, 185, 217, 301, 481, 1105, ... 

                                                           טבלה מס' 1

 

חשוב שנסב את תשומת הלב לכמה עובדות שבטבלה:

  1. כל המספרים שבטבלה הם מספרים אי-זוגיים. הדוגמה הראשונה של מספר פסאודו-ראשוני זוגי נמצאה בשנת 1950: 1103*73*2=161038 לבסיס 2. מספרים מעטים כאלה נתגלו בהמשך, אבל יש כאלה המתנגדים לכלול מספרים אלה בין המספרים הפסאודו-ראשוניים. עניין של הגדרה!
  2. מעניין שדווקא בבסיס הקטן ביותר (2) המספר הפריק הראשון הוא 341. זה מקרה נדיר, שהרי בבסיסים 1 עד 100 הוא מופיע ראשון בבסיסים 15, 60, 63  ו-78 בלבד (לא רואים זאת בטבלה). בטווח זה של הבסיסים אין מספר פריק המופיע ראשון שהוא גדול ממנו.
  3. הטבלה מראה שמספר פריק n שמקיים את הנוסחה בבסיס מסוים לא יקיים אותה בהכרח בבסיס שונה. כך, אף אם הביטויים 1‏‏‏-390 ו-490-1 מתחלקים ל-91, הרי הביטוי 1‏-290  אינו מתחלק בו. הדבר נכון גם לגבי המספר 341 שמחלק את הביטוי 1‏-2340 וגם את הביטוי 4340-1 אבל לא את הביטוי 1‏-3340.
  4. על טיבם של המספרים המקווקווים נעמוד בהמשך. נסתפק, לפי שעה, בהערה שמספרים אלה יופיעו בכל הבסיסים במקום כלשהו בטבלה. אנו רואים את המספר 561 שמופיע בטבלה בבסיסים 2 ו-5, והמספר 1105 מופיע בבסיסים 2 ו-6. אילולא קטענו את הטבלה מחוסר מקום, היינו רואים אותם מופיעים בכל בסיס. כך הדבר לגבי כל המספרים המקווקווים שרואים ושלא רואים בטבלה.

 

כזכור קראנו למספרים פריקים אלה בשם מספרים פסאודו-ראשוניים בהקשר לדיוננו ב"השערה הסינית" שהתייחסה לבסיס 2. כעת אנו רואים בטבלה שמספרים כאלה מופיעים בכל בסיס. הוכח בשנת 1903 שיש אינסוף מספרים כאלה בכל בסיס נתון, אבל הם נדירים, כאמור, בהרבה מן המספרים הראשוניים "האמיתיים".


 

מספרי קרמייקל

השאלה האם קיים מספר פריק n שמחלק את הביטוי 1-xn-1  לכל בסיס x, שהוא זר ל-n? אכן קיימים מספרים כאלה, שהקטן שבהם הוא 17*11*3=561. מספר זה מחלק את הביטוי 1-x560, כאשר במקום x אפשר להציב כל מספר חוץ מהמספרים: 17, 11, 3 שהם הגורמים שלו (כלומר לא זרים לו). מספרים אלה נקראים מספרים פסאודו-ראשוניים מוחלטים או מספרי קרמייקל, על-שם המתמטיקאי האמריקאי רוברט קרמייקל (1967-1879) שהיה הראשון שהבחין בקיומם. במאמרו הראשון בנושא זה, שפורסם בשנת 1910, הצביע קרמייקל על ארבעה מספרים פסאודו-ראשוניים מוחלטים. אחד מהם הוא 561 הנודע ושלושת האחרים הם: 17*13*5=1105; 31*13*7=2821 ו-73*31*7=15,841. שנתיים לאחר מכן הוא הציג עוד 11 מספרים כאלה בעלי שלושה גורמים ראשוניים ועוד מספר בעל ארבעה גורמים ראשוניים: 457*73*37*13=16,046,641. הוא גם העלה את ההשערה שקיימים אינסוף מספרים כאלה. השערה זו נותרה בלתי מוכחת במשך למעלה   מ-80 שנה עד שאומתה בשנת 1994 על ידי קבוצה של מתמטיקאים.

סיכום המחקר על מספרי קרמייקל מראה שאלה הם מספרים אי-זוגיים פריקים המתפרקים לפחות לשלושה גורמים ראשוניים שונים (בניסוח אחר, הם חסרי-ריבועים square-free). ידועים לנו מספרי קרמייקל שיש להם 34 גורמים ראשוניים שונים, נכון לשנת 2004.

ועכשו נשוב לטבלה מס' 1 ונציין שהמספרים המקווקווים הם מספרי קרמייקל,  ולכן אם היינו ממשיכים את הטבלה ומציינים את כל המספרים הפסאודו- ראשוניים בכל הבסיסים היינו רואים מספרים אלה (ועוד אין סוף מספרי קרמייקל) מופיעים בכל הבסיסים.

אנו מציגים להלן את שבעת מספרי קרמייקל הראשונים שבאים אחרי שלושת הראשונים המצוינים בטבלה, ואלה הם: 2465, 2821, 6601, 8911, 10585, 15841, 29341.

מעניין לציין שאם היינו מחסרים 1 ממספר קרמייקל כלשהו, אזי הוא היה מתחלק לכל אחד מהגורמים שלו לאחר שחיסרנו 1 מכל אחד מהם. נדגים: הגורמים של מספר קרמייקל הראשון הם: 17*11*3=561, אזי 560 מתחלק ל-16, ל-10 ול-2. או 17*13*5=1105 (שהוא מספר קרמייקל השני, ראה טבלה 1) ולכן 1104 מתחלק ל-16, ל-12 ול-4. זו הייתה השערתו של המתמטיקאי הגרמני אלווין קורסֶלְט שפרסם אותה בשנת 1899, אבל הוא לא יכול היה להוכיח אותה, עד שבא קרמייקל והדגים אותה על המספר 561. תכונה זו הפכה לאחד הקריטריונים שבאמצעותם מזהים מספרי קרמייקל.

 

האם אפשר לבנות מספרי קרמייקל לפי נוסחה? אכן אפשר. בשנת 1933 הראה המתמטיקאי האמריקאי ג' צ'רניק שאפשר לבנות קבוצה מצומצמת של מספרי קרמייקל שיש לה תכונות מוגדרות. אם נציב במקום k בביטוי הבא:

(6k+1)(12k+1)(18k+1) מספר אשר יביא כל אחד משלושת הגורמים להיות מספר ראשוני, אזי מכפלתם תהיה מספר קרמייקל. תנאי זה מציב הגבלות על ערכו של k. אם, למשל, k=1 אזי כל הגורמים האלה יהיו ראשוניים ומספר קרמייקל יהיה 19*13*7 = 1729 (זהו המספר השלישי מבין מספרי קרמייקל, והוא מופיע בטבלה). לא כן אם נציבk=2,3,4,5 . אבל אם נציב את המספר 6 במקום אזי כל שלושת הגורמים הנ"ל יהיו מספרים ראשוניים.

 

מהדיון במשפט הקטן של פרמה התפתח הדיון למספרים פסאודו-ראשוניים ולמספרי קרמייקל. הגיע הזמן לסגור את המעגל ולשוב למשפט בהערה נועלת: יש מקרים שבהם מתחלק הביטוי 1-xp-1  ב-p כמה פעמים. לדוגמה, 1‏-310 מתחלק     ב-112, וכן 1‏-910. חוקרים רבים סברו במשך זמן רב שפתרון מסוג זה אינו בנמצא לבסיסים 2 ו-10, ורק לאחרונה נתגלה ש- 1‏-21092 מתחלק ב-10932 ו- 1‏-23510  מתחלק ב-35112.  יתרה מזו, המספר 1‏-68112 מתחלק ב-1133. למעשה תמיד אפשר למצוא בסיס כלשהו שבו קשר זה מתקיים לגבי הריבוע של כל מספר ראשוני שנבחר.

 

אין לקדם פוסט זה

הוספת תגובה

נשארו 150 תוים
נשארו 1500 תוים

תגובה אחת

© כל הזכויות לתוכן המופיע בדף זה שייכות ל ExcelMath91 אלא אם צויין אחרת