התגובות שלי בפורום
-
תגובות
-
כותרת: ראשון ושלישי
חבר שלי (אורי ינובר, מקום שני בתחרות הקודמת) הגיע הפעם מקום שלישי ואני ניצחתי
אני תוהה מי הגיע שניכותרת: הבהרה
בקשר להוכחה שלי, שכחתי לציין שמכיוון שלפולינום 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>
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.
