תורת המספרים

[meravoh]

תורת המספרים

אשמח לקבל הסבר על השאלה הבאה: מצא את כל המספרים השלמים n שעבורם השבר 12n-6 לחלק ל- 10n-3 לא ניתנים לצמצום

 

[עריסטו]

../images/Emo62.gif

(a,b) מסמל את המחלק המשותף המקסימלי של a ו - b. כדי לפתור מתבססים על כך ש - (a,b)=(a,a-b). לכן:

(12n-6,10n-3)=(2n-3,10n-3)=(2n-3,12)​

(המעבר האחרון התבצע על ידי חיסור 2n-3 מ - 10n-3 חמש פעמים) לכן zzz (12n-6,10n-3)=1 zzz אם ורק אם zzz (2n-3,12)=1 zzz כלומר 2n-3 לא מתחלק ב-2 ולא מתחלק ב-3, דהיינו

2n-3=1,5 (mod 6) 2n=2,4 (mod 6) n=1,2 (mod 3)​

לכן התשובה היא - השבר לא ניתן לצמצום אם ורק אם n אינו מתחלק ב-3.

 

[slallum]

שאלה

למה (a,b) = (a,a-b)? לא הגיוני לי :S

 

[עריסטו]

הגיוני מאוד

עליך להראות ש:

אם x הוא מחלק של a ושל b אזי x הוא מחלק של a ושל a-b

אם x הוא מחלק של a ושל a-b אזי x הוא מחלק של a ושל b מצירוף שתי התוצאות תקבל שהמחלקים המשותפים של a ושל b הם בדיוק המחלקים המשותפים של a ושל a-b, ולכן המחלק המשותף המקסימלי של a ושל b הוא המחלק המשותף המקסימלי של a ושל a-b.

 

[Renatius Cartesius]

נוכיח טענה חזקה יותר...

zzz gcd(a,b)=gcd(a+b*n,b) zzz zzz gcd(a,b)=ax+by=d x ו-y הם שלמים שמקיימים את המשוואה. zzz ax+by=(a+bn)x+(y-nx)b מפה קל לראות ש... zzz gcd(a+bn,b) | gcd(a,b) zzz זה לא מספיק... עכשיו בכיוון ההפוך, כלומר מ- gcd(a+b*n,b) zzz zzz gcd(a+bn,b)=(a+bn)*s+b*r (s ו-r המקיים את המשוואה) zzz (a+bn)*s+b*r=a*s+b(n*s+r) zzz ולכן גם מתקיים: zzz gcd(a,b) | gcd(a+bn,b) zzz מכאן בקלות נובע ש: zzz gcd(a,b)=gcd(a+b*n,b) zzz מש"ל

 

[slallum]

הא, מגניב D: תודה ../images/Emo13.gif

תגידו, מאיפה אתם יודעים בכלל את כל הדברים האלה?

 

[עריסטו]

איך אתה מוכיח ש...

...יש x ו - y שמקיימים את המשוואה, בלי להסתמך על כך ש - zzz gcd(a,b)=gcd(a+bn,b) zzz?

 

[Renatius Cartesius]

אם הבנתי אותך נכון....

להוכיח שיש x ו-y שלמים המקיימים את gcd(a,b)=ax+by ? (זה די פשוט, אני חושב... להוכיח?)

 

[MaD PenGuiN]

מה פשר ה-ZZZ?

 

[Renatius Cartesius]

זה מייצב לי את הטקסט...

לדוגמא: אם לא הייתי משתמש ב- zzz gcd(a,b( ועשכיו אני כן משתמש ב- zzz gcd(a,b) zzz זה היה הסבר גרוע, שבת שלום.

 

[meravoh]

../images/Emo51.gif