סדרת שאריות

[עריסטו]

סדרת שאריות

בוחרים מספר טבעי n. אחר כך מגדירים סדרה כך: האיבר הראשון הוא 1, ואחר כך כל איבר הוא 2 בחזקת האיבר הקודם, מודולו n. האם החל ממקום מסויים כל איברי הסדרה יהיו שווים?

 

[Alkhimey]

האם השאלה היא

לכל n? למשל עבור n=1 התנאי מתקיים. עבור כל n = 2^k אחר התנאי בטוח לא מתקיים.

 

[עריסטו]

למה?

למה עבור n=2^k התנאי לא מתקיים? הרי עבור n כזה החל ממקום מסויים כל איברי הסדרה הם 0. (הסדרה היא סדרת השאריות של 1, 2, 4, 16, 65536, ... בחילוק ב-n)

 

[Alkhimey]

לא מובן..

נניח n=2 אז הסדרה תהיה 1 0 1 0 1 0 1 0 1... a_1 = 1 a_2 = 2^1 mod 2 = 0 a_3 = 2^0 mod 2 = 1 mod 2 = 1

 

[עריסטו]

לא הגדרתי טוב

התכוונתי לומר שכל איבר הוא 2 בחזקת האיבר הקודם, ואת איברי הסדרה כותבים מודולו n. למשל, מכיוון שהסדרה מתחילה כך

1 2 4 16 65536​

אזי אם n=10 היא מתחילה כך

1 2 4 6 6​

 

[איייייל]

נסיון

התשובה היא כן (אם אין לי טעות בהוכחה...) נוכיח באינדוקציה על n: קל לראות שהטענה נכונה עבור n=1. כעת, יהי n>=2, ונניח שהטענה נכונה לכל מספר טבעי בין 1 ל n-1. לשם נוחות נסמן את אברי הסדרה בלי המודולו ב a(k) נסמן ב f את פונקציית אוילר של n (כלומר, מספר המספרים בין 1 ל n אשר זרים ל n) לפי הנחת האינדוקציה, החל ממקום מסויים הסדרה a היא קבועה מודולו f - נסמן את הערך הזה ב z. לכן, לכל k החל מ k מסויים מתקיים:

a(k) = z + b(k)*f a(k+1) = 2^(z+b(k)*f) = (2^z)*((2^f)^(b(k)) = 2^z (mod n)​

השוויון האחרון נכון מודולו n כי 2 בחזקת f שווה 1 מודולו n. כלומר, החל ממקום מסויים הסדרה a(k) קבועה מודולו n - מש"ל.

 

[עריסטו]

../images/Emo127.gif