אין חידות חדשות, אפילו לא חידה לקראת התחרות ה – 3

[המאוכזב]

וחבל שכך..

[CodeGuru]

כותרת: חידה לקראת התחרות החדשה
בflyer החדש שיופץ לקראת התחרות יש, כמו כל שנה, חידה חדשה.
החידה בשנה הראשונה הייתה בשפת C, בשנה השניה בשפת PASCAL,
והשנה היא ללא שפה מוגדרת.
השאלה היא מה השארית של מכפלת 2000 המספרים הטבעיים הראשונים
(1*2*3*4*5*….*2000) בחלוקה ל 2003?
אתם מוזמנים לשלוח רעיונות, תוכניות שמנסות לפתור, רעיונות
מתימטיים, או כל הארה אחרת על השאלה.
בהצלחה.
CodeGuru

[Michael]

כותרת: re: solution
I suppose that this one should do:

int main(void)
{
clrscr();
unsigned long res = 1;
for(int i=1;i!=2001;i++){
res*=i; res = res%2003;
}
cout << res << endl;
return 0;
}

The output for this function is 1001

BTW, it really takes a codeguru to write English in this forum,
and I am not one….

[אלון מילשטיין]

כותרת: פתרון אפשרי
אם נבדוק את שארית החלוקה של עצרת של מספרים זוגיים (נסמן ב – N)
ב (N+3) כאשר N+3 ראשוני (ושלילי) נגלה כי השארית היא מחצית של N+2, לכן השארית במקרה זה תהיה 2/(2000+2)לכן 1001.

[CodeGuru]

כותרת: נכון, אבל למה?
אכן התשובה נכונה, אבל הפתרון שלך הוא אינדוקציה לא שלמה – ז"א
שהבחנת בחוקיות (נכונה) מסוימת מדוגמאות בלבד.
אפשר גם להוכיח טענה זאת. איך?
מה קורה אם N פריק? נסו להוכיח זאת.

[אורן בקר]

כותרת: פתרון
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.

[אורן בקר]

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

[אורן בקר]

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

[CodeGuru]

כותרת: פתרון מושלם
כל הכבוד, אכן פתרון מלא ונכון.
אפשר להוסיף שאם P איננו ראשוני, אז התוצאה היא אפס (תרגיל לקורא)
נוסיף חידה חדשה בהמשך.

[אורי יאנובר]

כותרת: תיקון לתיקון
I have a minor correction to Oren´s proof (which I find very elegant). The fundamental theorem of algebra is formulated for C &times; C, and while I believe it can be somehow adjusted to field algebra, there´s a simpler way.

Lemma: For every natural n, (x ^ 2) mod (p – 1) = 1 only if x mod p = 1 or x mod p = p – 1.

Proof: Let´s persume x is not equal to either 1 or p – 1. Let´s make an equation:
x ^ 2 = np + 1
x ^ 2 – 1 = np
(x + 1)(x – 1) = np

One of the two numbers, x + 1 or x – 1 has to be devidable by p. Because of that, either x mod p = 1 or x mod p = p – 1. We´ve reached a contradiction, and that´s why x has to be either 1 or p – 1.

Application of the lemma to multiplicative field over Zp: for every x´ belonging to the field, x´ * x´ = 1 only if x´ = 1 or x´ = p – 1.

[אורי יאנובר]

כותרת: תיקון לתיקון של עצמי
What I meant to say is that the fundamental theorem of algebra is formulated for <i>polynomials</i> whose coefficients are complex (belong to C). Moreover, I forgot to mention that n is natural and p is prime.

This is what happens when one tries to be excessively fundamentalist in proofs written around 10 P.M. Hopefully this 11 P.M. fix will do.

[מאת]

תגובות