ПМТ, 2004 г.

[mkmarinov]

Да се намерят всички нечетни прости числа р:
[tex]p | 1^{p-1}+2^{p-1}+...+2004^{p-1}[/tex]

[martin123456]

1. [tex]p > 2004[/tex]
[tex]\Rightarrow (p,i)=1[/tex], [tex]i \in \{1,2,\ldots,2004\}[/tex] и [tex]i^{p-1} \equiv 1 (mod p) \Rightarrow \sum \equiv 2004 (mod p)[/tex]. Искаме [tex]\sum \equiv 0 (mod p) \Rightarrow 2004 \equiv 0 (mod p) \Rightarrow p|2004[/tex]. Но [tex]p>2004[/tex].
2. [tex]p < 2004[/tex]
Нека [tex]n[/tex] от числата в [tex]\{1,2,\ldots,2004\}[/tex] се делят на [tex]p[/tex]. Значи [tex]\sum \equiv 2004 - n (mod p) \Rightarrow p|(2004-n)[/tex].
[tex]2004=pn+r[/tex], [tex]0 \le r \le p-1[/tex] и [tex]p|(2004-n)[/tex]. [tex]p|(2004-n) \Rightarrow p|(pn+r-n) \Rightarrow r \equiv n (mod p)[/tex]. [tex]\Rightarrow n=qp+r[/tex]. Заместваме [tex]2004=p(qp+r)+r = p^2q+pr+r[/tex].
2.1. [tex]q \ne 0 \Rightarrow p^2 \le 2004 \Rightarrow p \le 43[/tex].
Тук има по-малко случаи [tex]\ldots[/tex].
2.2. [tex]q =0 \Rightarrow n=r[/tex] и [tex]2004=pr+r=r(p+1)[/tex]. [tex]2004=2^2.3.167[/tex]. Делители [tex]1,2,3,4, 6,12,167,2.167, 2^2.167, 3.167, 2.3.167, 2004[/tex]. Значи за [tex]p[/tex]: (интересуват ни четни делители) [tex]p=1,2,5,11,2.167-1,2^2.167-1,2.3.167-1,2003[/tex]. Остават [tex]5,11,661,2003[/tex]