שיחה:89-214 סמסטר א' תשעד

חזרה לדף הקורס

גלול לתחתית העמוד

הוספת שאלה חדשה

הוסף שאלה חדשה (רשום כותרת לשאלה, רשום את תוכן השאלה ולחץ על שמירה למטה מימין לסיום).

-עזרה על עיצוב הטקסט וכתיב מתמטי תוכלו למצוא כאן

אם אתם רוצים לשאול שאלה עליכם ליצור חשבון משתמש באתר.

שאלות

שאלה 3 בתרגיל בית 1

נניח אני רוצה לבטא את המחלק המשותף המקסימלי של 840,575 כצירוף לינארי שלהם.

בשלב הראשון, אני מוצא את המחלק המשותף המקסימלי ע"י אלגוריתם אוקלידיס באופן הבא:

zz (840,575)=(575,265)=(265,45)=(45,40)=(40,5)=5 zz

המעבר הראשון משמאל לימין, נובע מכך ש: zz 840=575*1+265 zz

המעבר השני משמאל לימין, נובע מכך ש: zz 575=265*2+45 zz

המעבר השלישי משמאל לימין נובע מכך ש: zz 265=45*5+40 zz

המעבר הרביעי משמאל לימין נובע מכך ש: zz 45=40*1+5 zz

המעבר האחרון נובע מכך שהמחלק המשותף המקסימלי של 40 ו-5 הוא 5.

כעת מה שאני רוצה לעשות, זה לבטא את המחלק המשותף המקסימלי של 840,575 שהוא כאמור המספר 5, כצירוף לינארי של 840, 575. כיצד בדיוק אני עושה את זה. ראיתי פתרון בתרגול, אבל השיטה לא ממש מובנת לי. אשמח להסבר מפורט, כיצד בדיוק אני צריך לעשות את זה.

תודה מראש ושבת שלום!

שתי הערות עריכה בויקי: כדאי להשתמש בכותרות (מוסיפים עם מספר של "=" משני הצדדים) וכדאי להשתמש בכתיב מתמטי (הכפתור עם $\sqrt{n}$) כדי להכניס ביטויים מתמטיים.

התשובה לשאלה היא פשוט ליישם את אלגוריתם אוקלידס המורחב. רמז קל: זה גם מה שנדרש בשאלה 1. בקישור יש כמה דוגמאות מפורטות.

הדרך שבה מצאת את המחלק המשותף המקסימלי נכונה, ודרושה להמשך. בכל שלב (מעבר) באלגוריתם אוקלידס אפשר להציג את שארית החלוקה $r$ כצירוף של שני המספרים שמחלקים $r=n-qm$. נתחיל מן השלב האחרון ונתקדם "מעלה":

• בסוף קיבלת כי $5 = 1 \cdot 45 - 1 \cdot 40$.
• נציב את הביטוי ל-$40$ מהשלב אחד לפני האחרון $5 = 1 \cdot 45 - 1 \cdot (265 - 5 \cdot 45)$. אם נצמצם נקבל $5 = -1 \cdot 265 + 6 \cdot 45$.
• כעת מציבים ביטוי עבור $45$ עם $265$ ו-$575$.

כך ממשיכים עד שמגיעים לביטוי עם המספרים המקוריים שעבורם חיפשנו $\mathrm{gcd}$.

אם f | 2c וגם f | 2d האם אני יכול להסיק מכך ש- ( f | (2c,2d  ?

תודה.

כרמז, מה יקרה אם פשוט נסמן $n = 2c$ וגם $m = 2d$? מה יודעים אם $f | n,m$?

מה שיודעים, זה ש-f מחלק כל צירוף לינארי של n ושל m? איך אני יכול להסיק מזה ש-f מחלק את (n,m) ?

לזה בדיוק התכוונתי. לגב מה שאתה מנסה להסיק: ראינו בכיתה תכונה חשובה של ה-$\mathrm{gcd}$. איך אפשר להציג אותו?

שאלה 4 סעיף ג'

שתיי שאלות:

1. האם אני יכול לומר שקיים מספר x כך ש- x|a+b וגם x|a-b? אם כן, למה?

2. במידה ואני יכול לטעון את מה שכתבתי בשאלה 1, ובמידה והראיתי ש- x|2d, האם אני יכול לומר ש- zz (a+b,a-b) | 2d zz ? אם כן, למה?

הערת עריכה בויקי: אפשר לייצר רשימה ממוספרת על ידי שימוש בסולמית (#) בתחילת השורה.

1. לא לגמרי הבנתי את השאלה: לכל זוג מספרים הגדרנו את הממ"מ, ובכל מקרה $1$ תמיד מחלק כל מספר. בגלל זה, אפשר להתחיל את הפתרון עם הנחה כמו "יהי $e$ מחלק משותף (לאו דווקא מקסימלי) של $a+b$ ושל $a-b$..."
2. הרמז הוא שאפשר להשתמש בשאלה 4 סעיף ב' כדי לפתור את הסעיף הנוכחי. מה אתה יודע על הסכום וההפרש של $a+b$ ושל $a-b$?

מה שאני יודע שזה ש-$e$ מחלק גם את הסכום שלהם וגם את ההפרש שלהם. כלומר את $2a$ ואת $2b$.

מצוין! מה זה אומר שמתקיים $e|2a,2b$? את מה עוד $e$ מחלק?

שאלה

אם p מספר ראשוני, שלא מחלק את המספר a, למה נובע מכך ש- 1=(a,p) ? למעשה על מנת להגיד שהמחלק המשותף המקסימלי של a ו-p הוא 1, אני צריך לדעת גם ש-p לא מחלק את a, אבל גם ש-a לא מחלק את p. a לא מחלק את p מהסיבה ש-p ראשוני, ולכן בסה"כ a לא מחלק את P , ו-p לא מחלק את a ולכן המחלק המשותף המקסימלי הוא 1?

זה ההסבר?

יש כאן קצת סלט. קודם כל, רקע: עבור כל $n$ מתקיים $n|n$ וכמו כן $1|n$. כאשר אנחנו מחפשים $\mathrm{gcd}$ צריך למצוא את המספר הטבעי הגדול ביותר שמחלק גם את $p$ וגם את $a$. המספרים הטבעיים היחידים שמחלקים את $p$ הם כידוע רק $1$ ו-$p$. נתון כי $p$ לא מחלק את $a$, כלומר הוא לא מקיים את התנאי שנדרש להיות $\mathrm{gcd}$ שדורש לחלק את $a$. לכן נקבל $(a,p)=1$.

שאלה 6 בתרגיל 1

מה הכוונה למצוא מס' שלם חיובי $x$ כך ש- $17x = 1 (\bmod{53})$

לא ברור לי מה הכוונה ומה המשמעות של ה-$\mod 53$ הזה..

נא להשתמש בכפתור לנוסחאות מתמטיות. המשמעות של $\mod$ הוא לומר כי מדובר במשוואה מודולו $53$. כלומר מבקשים למצוא מספר $x$ כך שאם תכפול אותו ב-$17$ תקבל מספר שבחלוקה ב-$53$ תקבל שארית $1$.