אורן בקר

עמוד

התגובות שלי בפורום

מוצגות 5 תגובות – 1 עד 5 (מתוך 5 סה״כ)
  • מאת
    תגובות
  • בתגובה ל: מי ניצח בתחרות…. #79006
    אורן בקר
    משתתף

    כותרת: ראשון ושלישי
    חבר שלי (אורי ינובר, מקום שני בתחרות הקודמת) הגיע הפעם מקום שלישי ואני ניצחתי
    אני תוהה מי הגיע שני

    בתגובה ל: מישהו פתר את השאלה האחרונה? #78965
    אורן בקר
    משתתף

    כותרת: הנה פתרון
    sub bx, ax
    sbb si, si
    and bx, si
    add ax, bx

    אפשר גם להשתמש ב sar עם עקרון דומה

    אורן בקר
    משתתף

    כותרת: תיקון
    הפולינום הוא כמובן x^2-1 ואני מקווה שלא עשיתי עוד שגיאות הדפסה / שגיאות רעיוניות.

    אורן בקר
    משתתף

    כותרת: הבהרה
    בקשר להוכחה שלי, שכחתי לציין שמכיוון שלפולינום x^2 לא ייכתנו יותר משני שורשים (p-1, 1 במקרה של Zp), כל גורם במכפלה מתבטל עם גורם *אחר*, חוץ מ – 1, שאותו כבר אפשר לראות כ"מבוטל", ו p-1)/2)שהוא התשובה הסופית (אחרת אפשר לחשוב שיש עוד מספרים שההופכי שלהם זה הם עצמם ולכן הם לא יתבטלו).

    אורן בקר
    משתתף

    כותרת: פתרון
    Let´s prove it for the general case of (p-3)! mod p, when p>=3 is prime.

    Zp is a field. Therefore each a#0 in Zp has a unique b in Zp such as that ab=1.
    Now, in Zp:
    (p-1)*(p-1)=p(p-1)-(p-1)=p(p-2)+1=1.
    (p-2)*[(p-1)/2]=(p(p-3)+2)/2=2/2=1.

    Therefore 1*…*(p-3) has a unique reciprocal for each factor except for (p-1)/2.
    That means that (p-3)!=1*…*(p-3)=(p-1)/2.

    Therefore (p-3)! mod p = (p-1)/2.

    Oren.

    p.s: For guys not familiar with the terms, search for some basic linear algebra text and for Euclid´s extended algorithm.

מוצגות 5 תגובות – 1 עד 5 (מתוך 5 סה״כ)