PDA

צפה בגרסה המלאה : בעייה בנושא gcd



dipsy
02-01-2015, 15:48
צירפתי את השאלה.
אשמח לעזרה בסעיף ב'.

34163

OneProphecy
02-01-2015, 18:16
רוצים להוכיח שכמות הפתרונות למשוואה מודולו mn הוא כמות הפתרון מודולו m כפול כמות הפתרונות מודלו n, כאשר m,n זרים.
כיוון אחד הוא ברור - אם יש פתרון מודולו mn, אז הוא גם פתרון מודולו m וגם פתרון מודולו n.
בכיוון ההפוך, אם a פתרון מודולו m ו-b פתרון מודולו n, אז לפי משפט השאריות הסיני, קיים (ויחיד) פתרון מודולו mn.

כמו שרואים אין בכלל התייחסות למשוואה הספציפית שלך, וזה משהו מעניין שכדאי להכיר - לכל משוואה פולינומיאלית במודולו מספר n, פונקציית ספירת הפתרונות שלה ב-n היא הפונ' שסופרת את כמות הפתרונות מודולו n. מה שהוכחנו כאן הוא שהפונקציה הזו היא כפלית אריתמטית - לכל מספרים זרים היא כפלית. אם מעניין אותך, ההמשך הטבעי של הנושא הוא פתרונות של משוואות פולינומיאליות במודולו n. קרא כאן (https://he.wikipedia.org/wiki/%D7%A4%D7%95%D7%A0%D7%A7%D7%A6%D7%99%D7%94_%D7%90% D7%A8%D7%99%D7%AA%D7%9E%D7%98%D7%99%D7%AA) (תחת כפליות) וכאן (https://he.wikipedia.org/wiki/%D7%9C%D7%9E%D7%AA_%D7%94%D7%A0%D7%96%D7%9C).

dipsy
02-01-2015, 19:56
רוצים להוכיח שכמות הפתרונות למשוואה מודולו mn הוא כמות הפתרון מודולו m כפול כמות הפתרונות מודלו n, כאשר m,n זרים.
כיוון אחד הוא ברור - אם יש פתרון מודולו mn, אז הוא גם פתרון מודולו m וגם פתרון מודולו n.
בכיוון ההפוך, אם a פתרון מודולו m ו-b פתרון מודולו n, אז לפי משפט השאריות הסיני, קיים (ויחיד) פתרון מודולו mn.

כמו שרואים אין בכלל התייחסות למשוואה הספציפית שלך, וזה משהו מעניין שכדאי להכיר - לכל משוואה פולינומיאלית במודולו מספר n, פונקציית ספירת הפתרונות שלה ב-n היא הפונ' שסופרת את כמות הפתרונות מודולו n. מה שהוכחנו כאן הוא שהפונקציה הזו היא כפלית אריתמטית - לכל מספרים זרים היא כפלית. אם מעניין אותך, ההמשך הטבעי של הנושא הוא פתרונות של משוואות פולינומיאליות במודולו n. קרא כאן (https://he.wikipedia.org/wiki/%D7%A4%D7%95%D7%A0%D7%A7%D7%A6%D7%99%D7%94_%D7%90% D7%A8%D7%99%D7%AA%D7%9E%D7%98%D7%99%D7%AA) (תחת כפליות) וכאן (https://he.wikipedia.org/wiki/%D7%9C%D7%9E%D7%AA_%D7%94%D7%A0%D7%96%D7%9C).


תודה אבל זה לא כלכך ברור לי.
גם מה שרשמת כ"ברור" (כיוון אחד) אז לא היה לי הכי ברור שבעולם.

אפשר טיפה יותר מפורט?

OneProphecy
02-01-2015, 22:44
בהסבר f היא כמו הפונ' פסי אצלך (זו שסופרת את הפתרונות).

לכל פתרון a מודולו n ופתרון b מודולו m, לפי משפט השאריות הסיני (כאן משתמשים בזרות) יש פתרון יחיד מודולו mn, ולכן (f(nm)>=f(n)f(m.

אבל אני טוען שלא יכול להיות שזה גדול ממש - אם כן, אז יש פתרון כלשהו מדולו mn - נניח t, שלא מגיע מפתרון למערכת
(x^3-x-1=0mod(n
(x^3-x-1=0mod(m
(שים לב שכאן מדברים על x במודולו mn).
אז מתקיים (t^3-t-1=0mod(mn, כלומר mn|t^3-t-1. אבל m|mn,n|mn ולכן גם n|t^3-t-1 ו- m|t^3-t-1, כלומר
(t^3-t-1=0mod(m (וכאן t נלקח להיות במודולו m), ו-(t^3-t-1=0mod(n (כאן t נלקח במודולו n). אז יוצא שהוא כן מגיע מפתרון למערכת כזו.

עיקר העניין בהוכחה הוא החלק הראשון - החלק השני (ה"ברור") הוא באמת ברור, כי כל פתרון מודולו mn הוא גם פתרון מודולו m ופתרון מודולו n.