תורת המספרים. שאלה

[student47]

תורת המספרים. שאלה

ראשית השאלה מדברת על 2 ההגדרות הבאות:
1.
a1,...,an היא "מערכת מלאה" של שאריות מודולו n אם a1,..,an שקולים מודולו n ל- zz 0,1,...,n-1 zz בסדר כלשהו.
למשל: 7,6,8 זו מערכת מלאה של שאריות מודולו 3 כי: 7 משאיר שארית 1 בחלוקה ב-3, 6 משאיר שארית 0 בחלוקה ב-3 ו-8 משאיר שארית 2 בחלוקה ב-3.

2. קבוצת מספרים שלמים R תיקרא "מערכת מצומצמת" של שאריות מודולו מודולו n אם מתקיים 3 תנאים:
a. לכל איבר r in R מתקיים: r,n) = 1) .
b. הקבוצה R מכילה (phi(n איברים. (phi הכוונה לפונקציית אוילר.)
c. לא קיימים שניי איברים ב-R ששקולים מודולו n.

כעת לשאלה:
א'. אם zz A = {a1,..,am} zz מערכת מלאה. alpha, beta in Z ו- alpha,n) = 1), אזי: zz B = {alpha*a1 + beta,...,alpha*am + beta} zz מערכת מלאה.
ב'. שאלה 2 בלינק הבא: http://u.math.biu.ac.il/~reznikov/courses/problems2014-Fall.pdf
לא ברור לי אם מדובר שם על מערכת מצומצמת או לא. אם מישהו יודע, אשמח להסבר.

לגבי סעיף א', ניסיתי כך:

נניח בשלילה ש-B לא מערכת מלאה.
לכן קיימים שניי איברים ב-B עבורם מתקיים: zz alpha*ai + beta = alpha*aj + beta (mod m) zz
נחסיר beta משניי האגפים ונקבל: (alpha*ai = alpha*aj (mod m האם אפשר לחלק את שניי האגפים ב-alpha, ולקבל: (ai = aj (mod m
ולהגיד שזו סתירה לכך ש-A מערכת מלאה?

האם זו הוכחה נכונה?

לגבי ב' (שאלה 2 מהלינק), אשמח לעזרה.

תודה!

 

[אורי769]

עזרה

ב-א' עשית בסה"כ בסדר. לא ניתן לחלק ב-alpha במובן הרגיל של המילה, אבל מה שכן ניתן לטעון זה:
אם x,n)=1) אז קיים y כך ש-yx=1 mod n
יש להניח שראית טענה זו ואם לא אז לא נורא קשה להוכיח אותה.

לגבי ב' - אכן מדובר במערכת מצומצמת. זו שאלת חקר ואי לכך אני מציע בחום שתפשיל שרוולים ותתחיל לחקור. איך חוקרים? תתחיל מלבחור m. רצוי שיהיה קטן אבל לא קטן מדי. נגיד 6 או 10. לא ראשוני. תבחר מערכת מצומצמת. תנסה אלפות וביטות שונים ותראה. אחרי שבודקים כמה דוגמאות, קל יותר להבין מה נכון ואז גם קל יותר להוכיח

 

[student47]

רק לפני הפשלת השרוולים בסעיף ב', צריך עוד משהו שקשור ל-א'

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

אני רוצה להראות שפונקציית אוילר היא כפלית אריתמטית. כלומר להראות ש:
עבור m,n) = 1) , מתקיים: zz phi(mn) = phi(m)*phi zz .

המרצה כתב כך:
נתבונן במערכת מלאה מודולו mn:
zz 0 1 .............. m-1 zz
zz m m+1 ........ m+(m-1) zz
. .
. .
. .
zz (n-1)m (n-1)m+1 .... (n-1)m+(m-1) zz

מה ההסבר לכך שהיא מלאה מודולו mn?
על מנת להוכיח שהיא מלאה מודולו mn, אני צריך להראות שלכל אחד מהמספרים שכתובים כאן, יש שארית אחת ויחידה בחלוקה ב-mn.

אבל אני לא ממש יודע להראות את זה.
בעקרון כל אחת מהשורות היא מערכת מלאה מודולו m.
כמו כן, מהטענה שהוכחתי בסעיף א' בפוסט הקודם, נובע שכל עמודה היא מערכת מלאה מודולו n
כי כל עמוד היא מהצורה:
zz 0*m + i zz
zz 1*m + i zz
zz 2*m + i zz
.
.
.
zz (n-1)*m + i zz

ומתקיים שהקבוצה zz {1,2,...,n-1} zz היא מערכת מלאה מודולו n.
לכן אם כופלים כל אחד מאברי הקבוצה ב-m ולמכפלה מוסיפים i, ומסתכלים על הקבוצה שמתקבלת, אז מהטענה בסעיף א' בפוסט הקודם, הקבוצה
היא מערכת מלאה מודלו n. כמו כן, מתקיים התנאי ש- (n,m) זרים (כי נתון כאן).

כלומר, כל עמודה היא מערכת מלאה מודלו n וכל שורה היא מערכת מלאה מודולו m.

1. איך מפה אני מגיע לכך שהמערכת שלנו מלאה מודולו mn?

2. איך מסיקים מזה שעבור m,n זרים, מתקיים: (phi(mn)=phi(m)*phi(n ?

ותודה רבה על העזרה!

 

[אורי769]

תשובה

תן לי דוגמא למערכת מלאה מודולו 6? תשובה: 0,1,2,3,4,5
אז מה היא מערכת מלאה מודלו mn?

לא במקרה צייר המרצה את המספרים בטבלה n על m - זה בא לרמוז לנו שב-(phi(n שורות יימצאו (phi(m איברים שהם זרים ל-mn. נסה לחשוב באילו שורות. כדי גם כאן לקחת דוגמא.