בתשובה לגדי אלכסנדרוביץ', 08/09/05 16:14
 |
|
 |
||
|
||||
 |
אני אולי לא מבין מספיק מתמטיקה, אבל איך אתה מוכיח עבור שארית a כללית ש-a^2 לא מתחלק ב-p בלי המשפט היסודי? (מעניין אותנו a^2 כי את הריבוע אפשר לפתוח לשני גורמים שבוודאות מתחלקים ב-p ועוד a^2). |
 |
 |
 |
|
|
|
||
|
||||
|
עוזי הראה בתגובה 327627. | |
|
|
|
|
|
||
|
||||
|
אכן לא הבנתי את התגובה ההיא ואיך ההוכחה שם הולכת. כנראה שאני מפספס משהו מאוד בסיסי פה, אז אני אפסיק להטריד. | |
|
|
|
|
|
||
|
||||
|
אתה לא מטריד. עוזי מתבסס על מה שמכונה "האלגוריתם האוקלידי". בעזרת האלגוריתם ניתן להראות שאם x זר ל-n אז קיימים מספרים שלמים a,b כך ש-an+bx=1. האלגוריתם הזה מתקיים באוסף מיוחד של חוגים שנקראים "חוגים אוקלידיים" ושיש בהם מושג כלשהו של חילוק עם שארית (אם תרצה אני ארחיב) - המספרים השלמים הם חוג כזה, ולא צריך את המשפט היסודי של האריתמטיקה בשביל להראות את זה. גם ההפך נכון אם an+bx=1 עם a,b שלמים אז x,n זרים (כי המחלק המשותף המקסימלי של x,n מחלק כל אחד משני האיברים בסכום אז הוא מחלק גם את מה שבצד ימין, ולכן הוא חייב להיות 1). עכשיו עוזי לוקח את המספרים שלנו וכותב ax+bn=1 ו- cy+dn=1. הוא כופל ומקבל את הדבר הבא: (ac)xy+(da+cb+db)n=1 תכפול ותעשה כינוס איברים אם אתה לא מאמין לי. אבל מה קיבלנו? מה שבסוגריים הם מספרים שלמים, ולכן אפשר להפעיל את הכיוון ההפוך ולקבל ש-xy זר ל-n.
|
|
|
|
|
|
|
||
|
||||
|
כינוס האברים לא יצא לי ממש מה שכיוונת (בתוך הסוגריים לפני n יצא לי dax+bcy+dbn, זה לא משנה כי זה בכל מקרה שלם), אבל הבנתי את ההוכחה. עוזי לא רשם שהמספרים a עד d שלמים ולא הכרתי את "האלגוריתם האוקלידי". תודה רבה. |
|
|
|
|
|
|
||
|
||||
|
בכינוס האיברים כמובן שזו טעות שלי ואתה צודק (גם בתשובה וגם בכך שזה ממילא מספר שלם). אם אתה לא מכיר את האלגוריתם האוקלידי זה קצת יותר בעייתי, כי קשה להסביר על רגל אחת. אני אנסה כאן ואפשר גם לקשר אותך לויקיפדיה: הרעיון הבסיסי הוא זה: אם יש לך יכולת לחלק דברים עם שארית (כלומר, אם יש לך איברים x,y אז קיימים איברים q,r כך ש-x=qy+r כאשר r קטן מ-y במובן מסויים שלא ניכנס אליו כאן אבל כשמדובר במספרים שלמים הוא פשוט הערך המוחלט שלהם) אז יש אלגוריתם למציאת מחלק משותף מקסימלי של שני איברים. מחלק משותף מקסימלי d של x,y הוא פשוט מספר שמחלק את x,y וכל מספר שמחלק גם את x וגם את y מחלק בהכרח גם את d. כבר אתה רואה ש-d לא יחיד - מחלק משותף מקסימלי של 6,15 הוא גם 3 וגם מינוס 3. מתברר שזה ההבדל היחיד שיכול להיות בין מחלקים מקסימליים במספרים שלמים - הסימן. איך עובד האלגוריתם האוקלידי? נניח שהמספרים שלנו הם x>y ולצורך פשטות הם טבעיים. תחלק את x ב-y ותקבל, כאמור, x=qy+r. עכשיו שים לב למשהו מעניין: מחלק משותף מקסימלי של y ו-r הוא גם מחלק משותף מקסימלי של x,y (שאנחנו מסמנים d). למה? ברור ש-d מחלק את r כי הוא מחלק את x,y והרי r=x-qy (אז d מחלק כל גורם באגף ימין ולכן מחלק את אגף שמאל). בנוסף, אם e הוא איבר שמחלק את r,y (סליחה על עודף האותיות) אז הוא מחלק גם את x, כי הרי x=qy+r. לכן e מחלק את d, כי הרי אמרנו שכל מי שמחלק את x ואת y מחלק את d. מה יצא לנו מכל זה? שעכשיו כדי למצוא את מחלק משותף מקסימלי של x,y מספיק למצוא מחלק משותף מקסימלי של y,r, והרי y>r ולכן הממדים של הבעיה שלנו מצטמצמים, ואנחנו יכולים להמשיך באותה השיטה בדיוק עד שנקבל בשלב מסויים שני מספרים a>b שאנחנו מחפשים להם מחלק משותף מקסימלי ומתקיים ש-b מחלק את a ללא שארית, ואז b הוא מן הסתם המחלק המשותף המקסימלי. כל זה ארוך ומסובך אבל לא השתמשנו בכלל במשפט היסודי של האריתמטיקה. עכשיו נשאר הטוויסט האחרון, שאני לא אוכיח לך כאן: אם d הוא מחלק משותף מקסימלי של x,y אז קיימים מספרים שלמים a,b כך ש-ax+by=d - ואפשר למצוא אותם באמצעות הרחבה קלה של האלגוריתם האוקלידי. אם כל זה ברור לך ועדיין ההוכחה של עוזי לא ברורה לך תגיד ואני אמשיך (כבר כמעט גמרנו). |
|
|
|
|
|
|
||
|
||||
|
יפה מאוד ותודה רבה. אין צורך להמשיך. | |
|
|
|
|
|
||
|
||||
|
לא חיוני לשיחה, אבל הגרסה שלהלן כל כך חמודה: כדי למצוא את הממג"ב של a ו־b, חסר מן הגדול את הקטן. המשך עד שתקבל אפס באחד מהם. השני הוא הפתרון. |
|
|
|
|
|
|
||
|
||||
|
מה שמעניין הוא אם האלגוריתם הזה יעיל באותה מידה כמו האלגוריתם המקורי. למישהו יש דוגמה שעליה האלגוריתם הזה "ייתקע" להרבה זמן? | |
|
|
|
|
|
||
|
||||
|
אם אתה מחפש את הממג"ב של 1,000,000 ו-7, האלגוריתם המחסר יבלה זמן רב בניסיון להיפטר מה-7. זו חידה נחמדה למצוא את צמדי המספרים הכי גרועים לאלגוריתם האוקלידי (רמז: בצמדים האלה, האלגוריתם המחלק מתנהג דומה מאוד לאלגוריתם המחסר). (עוד רמז: שפנים). |
|
|
|
|
|
|
||
|
||||
|
פיבונאצ'י? | |
|
|
|
|
|
||
|
||||
|
כן. (למה?) | |
|
|
|
|
|
||
|
||||
|
נניח ש-x,y הם שני מספרי פיבונאצ'י רצופים, אז x=y+z כש-z הוא זה שלפני שניהם, ו-y>z כי y עצמו הוא סכום של שני מספרים טבעיים שאחד מהם הוא z. לכן x=y+z זו גם החלוקה עם שארית של x ב-y. נחמד. |
|
|
|
|
|
|
||
|
||||
|
בינתיים רק הסברת למה בהפעלת אוקלידס על פיבונצ'י, המנה בכל סיבוב היא תמיד 1 (והשארית היא מספר פיבונצ'י קודם). אינטואיטיבית זה נראה "הכי גרוע", אבל זה תרגיל מעניין וחינוכי לנסח בדיוק את הטענה שזה באמת "הכי גרוע", ואז להוכיח אותה בזהירות. | |
|
|
|
|
|
||
|
||||
|
מה זה כבר מקדם פולינומי ביני ובינך... | |
|
|
|
|
|
||
|
||||
|
מחלק משותף גדול ביותר. | |
|
|
|
|
|
||
|
||||
|
תודה. | |
|
|
|
|
|
||
|
||||
|
עיקר שכחתי - אשמח אם תרחיב על האלגוריתם האוקלידי. | |
|
|
|
|
|
||
|
||||
|
מי שיודע מה זה כופל משותף מקסימלי? | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |