reszta z dzielenia

[klimat]

Wyznacz resztę z dzielaenia sumy \(\displaystyle{ 1! + 2! + ... + 2018!}\) przez \(\displaystyle{ 2018}\).

[Premislav]

Ponieważ \(\displaystyle{ 2018=2\cdot 1009}\) i liczba \(\displaystyle{ 1009}\) jest pierwsza, więc to zadanie w zasadzie sprowadza się do takiego, jak na mój gust bardzo trudnego, problemu:
wyznaczyć
\(\displaystyle{ \sum_{k=1}^{p-1}k! \pmod{p}}\)
dla liczby pierwszej nieparzystej \(\displaystyle{ p}\) (tutaj akurat \(\displaystyle{ p=1009}\), ale raczej przydałoby się ogólniejsze podejście). Myślałem kiedyś (bezskutecznie) nad rozwiązaniem takiego zadania, a jedyne, co znalazłem w necie w tym temacie (może za mało wtedy szukałem), to taka dyskusja na stacku: ... y-question

Skąd masz takie zadanie?

[Bran]

Dzielniki liczby \(\displaystyle{ 2018}\), to \(\displaystyle{ 2, 1009}\), obie są pierwsze więc to tyle.

Także od \(\displaystyle{ 1009!}\) nie będzie żadnej reszty, zatem możemy śmiało to pominąć i zadanie sprowadza się do takiej sumy:

\(\displaystyle{ 1!+2!+ \dots + 1008!}\), tutaj każde będzie dawało resztę.

Najmniejszym czynnikiem, który jest większy od \(\displaystyle{ 2018}\) jest: \(\displaystyle{ 7! = 5 040}\), a reszta z dzielenia tej liczby przez daną wynosi: \(\displaystyle{ 502}\).

Czyli mamy taką sytuację: \(\displaystyle{ \frac{5040-502}{2018} = n}\), \(\displaystyle{ n \in \NN}\).

Oczywiste jest, że:
Jeżeli \(\displaystyle{ a}\) dzieli \(\displaystyle{ b-r}\), to \(\displaystyle{ a}\) dzieli \(\displaystyle{ n(b-r)}\), dla \(\displaystyle{ a,b,r,n \in \NN}\) i \(\displaystyle{ a \le b}\)

Zatem mamy: \(\displaystyle{ 1002 \cdot 502 = 503 004}\)
Dla pozostałych sześciu czynników mamy sumę reszt równą \(\displaystyle{ 873}\)

\(\displaystyle{ 503 004 + 873 = 503 877}\)

Reszta z dzielenia tego przez \(\displaystyle{ 2018}\), to \(\displaystyle{ 1395}\) i to jest odpowiedź.

[Premislav]

Niestety nie bardzo rozumiem Twoje rozwiązanie.

Najmniejszym czynnikiem, który jest większy od \(\displaystyle{ 2018}\) jest: \(\displaystyle{ 7! = 5 040}\), a reszta z dzielenia tej liczby przez daną wynosi: \(\displaystyle{ 502}\).

Niezupełnie, \(\displaystyle{ 5040=2\cdot 2018+1004=4\cdot 1009+1004}\)

Zatem mamy: \(\displaystyle{ 1002 \cdot 502 = 503 004}\)

To też nie rozumiem, skąd się wzięło, jak dla mnie zostaje Ci ta reszta z dzielenia liczby \(\displaystyle{ 5040}\) pomnożona przez \(\displaystyle{ 1+\frac{8!}{7!}+\ldots+\frac{1008!}{7!}}\), ale może czegoś nie dostrzegam.

[Majeskas]

Bran, nieszczególnie się to zgadza. Według Twojego rozumowania każda silnia większa od \(\displaystyle{ 7!}\) ma dawać resztę równą \(\displaystyle{ 502}\) (a właściwie 1004 — jak zauważył Premislav).

\(\displaystyle{ 10!=7!\cdot720\equiv1004\cdot720=722880\equiv432\pmod{2018}}\)