חידה קלילה

[הפרבולה]

חידה קלילה

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

 

[aaa123]

פתרון

המספר הוא מהצורה 10x+3
20x+6 זהה למספר שנכתב 3x
ולכן הספרה היחידות של x היא 6.
&nbsp
זה אומר שהמספר הוא מהצורה 100x+63
200x+126 זהה למספר שנכתב בצורה 3x6
ולכן ספרת היחידות של x היא 2
&nbsp
זה אומר שהמספר הוא מהצורה 1000x+263
2000x+526 זהה למספר שנכתב בצורה 3x26
ולכן ספרת היחידות של x היא 5
זה אומר שהמספר הוא מהצורה 10000x+5263
20000x+10526 זהה למספר שנכתב בצורה 3x526
ולכן ספרת היחידות של x היא 0
זה אומר שהמספר הוא מהצורה 100000x+5263
200000x+10526 זהה למספר שנכתב בצורה 3x0526
ולכן ספרת היחידות של x היא 1
זה אומר שהמספר הוא מהצורה 1000000x+105263
2000000x+210526 זהה למספר שנכתב בצורה 3x10526
ולכן ספרת היחידות של x היא 2
זה אומר שהמספר הוא מהצורה 10000000x+2105263
20000000x+4210526
&nbsp
אפשר לבנות את הטבלה הבאה במקום לרשום את כל האפסים
&nbsp
ספרה
שארית קודמת
תוצאת הכפלה ב2 פלוס שארית(ספרה שניה היא הספרה בהתחלה)
שארית עתידית
&nbsp
אני מקבל שהטבלה מחזורית עם אינסוף מקומות שבהם תוצאת הכפלה פלוס שארית נותנת 3 ולכן יש אינסוף פתרונות.
&nbsp
הקטן בהם הוא
157894736842105263
השני בגודלו הוא
157894736842105263157894736842105263
&nbsp

 

[הפרבולה]

 

[עריסטו]

אפשר לפתור גם כך

נניח שיש במספר n+1 ספרות, והמספר הוא 10x+3, מקבלים משוואה
3*10^n+x = 2(10x+3)
3*10^n+x = 20x+6
3*10^n = 19x+6
(3*10^n-6)/19 = x
מחפשים n כך שהביטוי באגף השמאלי יהיה שלם, מקבלים שזה מתקיים ל - n=17, 35, 53 וכן הלאה. מכל ערך של n מקבלים ערך של x, למשל אם n=17 אז x=15789473684210526 (ובאמת יש בו 17 ספרות) ומתקבל פתרון 157894736842105263. זו תחילת הייצוג העשרוני של 3/19 וזה מסביר את התופעה - אם מעבירים את ה-3 להתחלה מקבלים את הייצוג העשרוני של 6/19 (הייצוגים של 1/19, 2/19 וכו' הם כולם תמורות מעגליות של המספר הנ"ל).

 

[הפרבולה]

למה היצוגים של 1/19 2/19 3/19 ... הם תמורות מעגליות

של היצוג המחזורי של 1/19 ?
אגב גם בשביעיות יש תופעה דומה של תמורות מעגליות:
1/7 = 0.142857...
2/7 = 0.285714...
3/7 = 0.428571...
4/7 = 0.571428...
5/7 = 0.714285...
6/7 = 0.857142...
אבל למשל עבור 1/13 2/13 ... זה לא בדיוק ככה ( יש 2 קבוצות שונות של תמורות מעגליות )
מעניין לחקור את זה לעוד מספרים ...

 

[עריסטו]

זה בגלל ש

החזקה הראשונה של 10 שנותנת שארית 1 בחילוק ב-19 היא 10 בחזקת 18. לכן כשעושים חילוק ארוך ומחלקים 1 ב-19 מקבלים במהלך החישוב את כל השאריות האפשריות. אם מחלקים למשל את 5 ב-19 פשוט מתחילים את המעגל משארית אחרת.

 

[עריסטו]

המשך...

אם p הוא ראשוני זר ל- 10, אז לכל a בין 1 ל- p-1 אורך המחזור של a/p הוא אותו אורך, והאורך הזה הוא מחלק של p-1. האם יש אינסוף ראשוניים p שעבורם אורך המחזור הוא p-1? זאת בעיה פתוחה:
[URL]https://en.wikipedia.org/wiki/Artin%27s_conjecture_on_primitive_roots[/URL]

 

[הפרבולה]

איך מוכיחים את הטענה הזאת

"אם p הוא ראשוני זר ל- 10, אז לכל a בין 1 ל- p-1 אורך המחזור של a/p הוא אותו אורך, והאורך הזה הוא מחלק של p-1"

 

[עריסטו]

אני מבין מההדגשה

שברור לך למה לכל a אורך המחזור הוא אותו אורך, והשאלה היא רק למה האורך הוא מחלק של p-1.
אני אסביר באמצעות דוגמה:
כשמחלקים את 1 ב-13 בחילוק ארוך מקבלים סדרת שאריות - 10, 9, 12, 3, 4, 1 וכעת הסדרה חוזרת על עצמה.
כשמחלקים את 2 ב-13 בחילוק ארוך מקבלים סדרת שאריות - 7, 5, 11, 6, 8, 2 וכעת הסדרה חוזרת על עצמה.
תנסה להסביר למה הסדרה תמיד חוזרת על עצמה והמחזוריות מתחילה מהשארית הראשונה, למה אין אף שארית שמופיעה בשתי הסדרות ולמה שתי הסדרות הן באותו אורך. (וכמובן כל זה נכון לא רק ל-13)
מכל זה נובע ששתי הסדרות יחד מכילות כל שארית בין 1 ל-12 פעם אחת (אם יש שארית שעדיין לא הופיעה ניקח מספר חדש ונחלק אותו ב-13) ולכן אורך המחזור הוא מחלק של 12.
תסביר למה מכל זה נובע ש-10 בחזקת 12 נותן שארית 1 בחילוק ב-13 - וקיבלנו הוכחה למשפט הקטן של פרמה.

 

[עריסטו]

הנה עוד טענה נחמדה

ניקח את המחזור של 2/13 למשל:
153846
נחלק לשני חלקים שווים
153
846
ונחבר:
קיבלנו 999
האם זה נכון בכל מקרה בו אורך המחזור זוגי (תמיד מקבלים מחרוזת של תשיעיות)?

 

[הפרבולה]

הוכחה

יהיה x מספר שלם שמיצג את המחזוריות של 1 חלקי p ( ראשוני ), למשל עבור 1/7
x=142857 אז ראינו ש p*x=q כאשר q הוא מספר שכל ספרותיו הם 9 במקרה של 1/7 אז q=999999.
אם עבור a/p יש תמורה מעגלית של x נקראה לה x1 אז עבור (p-a)/p יש תמורה מעגלית נוספת x2 של אותו x ו x1+x2=q, כלומר אפשר לחלק את ספרותיו של x לזוגות שסכום כל זוג שווה ל 9 , ואם x1 היא תמורה מעגלית של ספרותיו של x2 אז ההזזה המעגלית חיבת להיות שווה למחצית המחזור כלומר ל (p-1)/2.

נראה לי שהוכחנו עוד תכונה - גודל המחזור חיב להיות זוגי.

 

[עריסטו]

אורך המחזור של 1/3 ו-1/37 למשל הוא אי זוגי

ובכלל - אם p הוא גורם ראשוני של 999...999 (2n+1 תשיעיות) אז אורך המחזור הוא מחלק של 2n+1 ולכן אי זוגי.

 

[הפרבולה]

אז יש לי טעות בהוכחה

הנחתי שאם x1 x2 הם היצוג המחזורי השלם של a/p ו (p-a)/p אז סכומם הוא אכן מספר ששכל ספרותיו 9 , אבל לא הוכחתי ש x1 הוא בהכרח תמורה מעגלית של x2.
צריך לחשוב על זה עוד .....

 

[הפרבולה]

הוכחה אחרת

יהיה x מספר שלם שמיצג את השבר העשרוני של a חלקי p , p ראשוני a שלם בין 1 ל p-1. למשל עבור p=1/13 אז x=076923
יהיה n אורך המחזור המינימלי ( בדוגמה לעיל n=6 ), אז מתקיים
a/p = x/(10^n -1)
אם n זוגי: n=2*m אז:
a/p = x / [ (10^m -1)*(10^m+1) ] =>
1= p * x / [ (10^m -1)*(10^m+1) *a ]
p לא מצטמצם עם a כי p ראשוני ו a קטן ממנו.
p גם לא מצטמצם עם zzz 10^m-1 zzz (שהוא מספר עם m ספרות 9). אחרת מלכתחילה אורך המחזור היה מכסימום m ולא 2m
לכן x מתחלק ב zzz 10^m-1 zzz
נרשום את x בצורה הבאה:
x = k*10^m +r
k מורכב מ m הספרות האחרונת של x , ו r מורכב מ m הספרות הראשונות, בדוגמה לעיל k=076 r=923
אז קיים מספר שלם t שהוא תוצאת החלוקה של x ב zzz 10^m-1 zzz
x = k*10^m +r = t *( 10^m-1)
10^m *(t - k) = r + t
הפתרון השלם היחידי האפשרי עבור t זה t = k+1 נציב ונקבל:
10^m - 1 = r + k
קיבלנו שסכום 2 מספרים שספרותיהם הם החצי השמאלי והימני של x הוא מספר שכולו ספרות 9
משל.

 

[עריסטו]

אפשר לסיים את ההוכחה גם בצורה כזו

k*10^m +r מתחלק ב- zzz 10^m-1, וגם k(10^m-1) מתחלק בו, לכן גם ההפרש ביניהם k+r מתחלק בו.
זה בעצם סימן התחלקות ב- zzz 10^m-1. כלומר מספר מתחלק ב-999 למשל אם ורק אם כאשר מחלקים אותו לשלשות של ספרות (החל מימין) ומחברים אותן, הסכום מתחלק ב-999. באופן כללי אם כותבים מספר בבסיס b הוא מתחלק ב - b-1 אם"ם סכום ספרותיו מתחלק ב - b-1. אם נתון מספר בבסיס 10, אפשר לראות אותו כאילו הוא כתוב בבסיס 1000 וכל שלשת ספרות היא ספרה אחת, ומכאן מתקבל סימן ההתחלקות ב-999.

 

[הפרבולה]

לדעתי צריך להוסיף גם

שאחרי שהוכחנו ש k+r מתחלק ב k(10^m-1) צריך להראות שהוא גם ממש שווה לו, וזה נובע מכך ש k r הם מספרים שקטנים מ k(10^m-1) ולכן אם סכומם מתחלק בו אז הוא גם שווה לו.

 

[עריסטו]

אז נוסיף גם ש- k+r לא יכול להיות 0

 

[הפרבולה]

האמת שקודם צריך להסביר גם למה אורך המחזור קבוע

לכל a/p כאשר p ראשני ו a בין 1 ל p-1.
אנסה להוכיח:
ניקח את המספר המינימלי שמכיל n ספרות של 9 ( נסמן אותו ב q )שמחלק את p ( קיים כזה אם p זר ל 10 ), נסמן את תוצאת החילוק ב x ( שלם) לכן:
1/p = x/q = x/(10^n-1) = x/10^n + x/10^2n + x/10^3n+ .....
הטור הגאומטרי הזה הוא בעצם ההצגה העשרונית ( היחידה) של 1 חלקי p

אגב זה הוכחה שהמחזוריות מתחילה מהספרה הראשונה וזה נכון לכל p שזר ל 10 ( גם אם הוא לא ראשוני )

כעת נסתכל על a חלקי p , נניח שההצגה העשרונית שלו היא בעלת מחזוריות בגדול שונה m , m לא יכול להיות גדול מ n כי a*x קטן מ q בעל ה n ספרות של 9 ,(אז אולי m קטן יותר), a/p גם מחזורי מהספרה הראשונה , יהיה y מספר שלם שמיצג את המחזור כלומר:

a/p = y/10^m + y/10^2m +y/10^3m+.... = y/(10^m -1 )
a*(10^m -1) /p = y
באגף ימין יש מספר שלם y , מכיוון שאף a לא מחלק את p כי הוא ראשוני אז רק 10^m פחות 1 מחלק את p בסתירה לכך ש q הוא המספר הקטן ביותר שמכיל רק ספרות של 9 שמחלק את p. ולכן אורך המחזור קבוע לכל a .

עכשיו נותר להסביר את ההמשך ....

 

[עריסטו]

אפשר להוכיח שאורך המחזור מחלק את p-1

באמצעות המשפט הקטן של פרמה. ממנו נובע שהמספר שמורכב מ - p-1 תשיעיות מתחלק ב-p.
אני לא כתבתי ככה כי רציתי להראות שאפשר ללכת בכיוון ההפוך - להראות שאורך המחזור מחלק את p-1 ומזה לקבל את המשפט של פרמה.

 

[הפרבולה]

המשך

הסידרה חוזרת על עצמה בגלל שאחרי כמה פעולות של חילוק ארוך ניתקל בשארית שכבר קיבלנו מקודם ולכן תתחיל מחזוריות.
מקודם הוכחנו שאם p זר ל 10 ( בדוגמה שלך p=13 )הסידרה תהיה מחזורית מהאיבר הראשון.
וגם אם p בנוסף ראשוני אז שווים כל אורכי הסדרות המחזוריות של a/p
בסידרה לא יכול להיות שנקבל שארית שמופיעה בסידרה אחרת כי מעתה והלאה תחל מחזוריות של הסידרה האחרת בניגוד לכך שהסידרה מחזורית מהאיבר הראשון.

אז אורכי כל הסדרות השאריות שוות וחיתוך שלהם ריק והאיחוד הוא כל השאריות 1 עד p-1 לכן מחזוריות הסידרה מחלק את p-1

הוכחה למשפט פרמה הקטן
אם x שלם מיצג את המחזוריות , למשל עבור 1/13 נקבל x=076923
אז נרחיב את x עד ל p-1 ספרות בצורה מחזורית ( זה אפשרי גודל המחזור הבסיס מחלק את p-1 ) ונקבל מספר חדש מחזורי בעל p-1 ספרות למשל עבור 1/13
076923076923 =y , מתקיים ( n=p-1 )
1/p = y/10^n +y/10^2n +y/10^3n+.... = y/(10^n-1)
(10^n -1)/p = y => 10^n mod p =1
p=13 => 10^12 mod 13 =1