Podzielność przez 2017

Oddzielone od teorii liczb, proste problemy dotyczące zasad dzielenia itp.
vip123
Użytkownik
Użytkownik
Posty: 70
Rejestracja: 25 paź 2022, o 15:43
Płeć: Kobieta
Podziękował: 49 razy

Podzielność przez 2017

Post autor: vip123 »

Jak wykazać, że liczba
\(\displaystyle{
\left( 1+ \frac{1}{2}+ \frac{1}{3}+...+ \frac{1}{2016} \right)\cdot 2\cdot3\cdot...\cdot 2016
}\)

jest podzielna przez \(\displaystyle{ 2017}\)
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Podzielność przez 2017

Post autor: Janusz Tracz »

Jako, że \(\displaystyle{ 2017}\) to liczba pierwsza to każda z liczb \(\displaystyle{ n=1,2,\dots,2016}\) jest względnie pierwsza z \(\displaystyle{ 2017}\) zatem każda z tych liczb ma odwrotność modulo \(\displaystyle{ 2017}\). Ponad to dla każdego \(\displaystyle{ n=1,2,\dots,2016}\) istnieje tylko jedna jednoznaczna odwrotność za zbioru \(\displaystyle{ \left\{ 1,2,\dots,2016\right\} }\). Gdyby bowiem dla różnych liczb \(\displaystyle{ a,b\in \left\{ 1,2,\dots,2016\right\} }\) było tak, że miałyby identyczną odwrotność to \(\displaystyle{ a\equiv b\equiv x \mod 2017}\) dla pewnego \(\displaystyle{ x}\) to pozwalało by wnioskować o tym, że \(\displaystyle{ a=b}\), a to sprzeczność bo \(\displaystyle{ a \neq b}\). Teraz wystarczy zauważyć, że pracując \(\displaystyle{ \mod 2017}\) mamy
\begin{split}
\left( 1+ \frac{1}{2}+ \frac{1}{3}+...+ \frac{1}{2016} \right)2016! & \equiv \sum_{i=1}^{2016} 2016! \times n_i^{-1} \\
& \equiv \sum_{i=1}^{2016} - n_i^{-1} \\
& \equiv \sum_{i=1}^{2016} \left( 2017- n_i^{-1}\right) \\
& \equiv \sum_{n=1}^{2016}n,
\end{split}
gdzie
\(\displaystyle{ n_i^{-1}=\text{odwrotność mod 2017 elementu }i}\)

ponad to drugie przystawanie wynika z Twierdzenie Wilsona, trzecie ma na celu uwypuklić fakt, że liczby jakie pojawiają się w sumie to elementy zbioru \(\displaystyle{ \left\{ 1,2,\dots,2016\right\} }\). A ponieważ każdy jest inny, a my wykorzystaliśmy wszystkie to przedostatnia suma jest pewną permutacją ostatniej sumy stąd czwarta kongruencja. Wystarczy więc policzyć sumę korzystając ze znanego wzory i się jej dobrze przyjrzeć wtedy odpowiedź sama się ujawni.
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Podzielność przez 2017

Post autor: arek1357 »

Liczba 2017 to liczba pierwsza a to co masz w nawiasie to tak naprawdę suma wszystkich niezerowych elementów ciała

\(\displaystyle{ Z_{2017}}\)

Więc jaki stąd wniosek?

No właśnie ubiegł mnie kolega Alf tylko dokładniej...
Awatar użytkownika
timon92
Użytkownik
Użytkownik
Posty: 1654
Rejestracja: 6 paź 2008, o 16:47
Płeć: Mężczyzna
Lokalizacja: Katowice
Podziękował: 7 razy
Pomógł: 472 razy

Re: Podzielność przez 2017

Post autor: timon92 »

\(\frac 1k + \frac{1}{2017-k} = \frac{2017}{k(2017-k)}\), więc Twoje wyrażenie równa się \(2017 \cdot \left(\frac{1}{1\cdot 2016} + \frac{1}{2\cdot 2015} + \ldots + \frac{1}{1008 \cdot 1009}\right)\cdot 2 \cdot 3 \cdot \ldots \cdot 2016\)
vip123
Użytkownik
Użytkownik
Posty: 70
Rejestracja: 25 paź 2022, o 15:43
Płeć: Kobieta
Podziękował: 49 razy

Re: Podzielność przez 2017

Post autor: vip123 »

Janusz Tracz pisze: 20 gru 2022, o 12:50 Jako, że \(\displaystyle{ 2017}\) to liczba pierwsza to każda z liczb \(\displaystyle{ n=1,2,\dots,2016}\) jest względnie pierwsza z \(\displaystyle{ 2017}\) zatem każda z tych liczb ma odwrotność modulo \(\displaystyle{ 2017}\). Ponad to dla każdego \(\displaystyle{ n=1,2,\dots,2016}\) istnieje tylko jedna jednoznaczna odwrotność za zbioru \(\displaystyle{ \left\{ 1,2,\dots,2016\right\} }\). Gdyby bowiem dla różnych liczb \(\displaystyle{ a,b\in \left\{ 1,2,\dots,2016\right\} }\) było tak, że miałyby identyczną odwrotność to \(\displaystyle{ a\equiv b\equiv x \mod 2017}\) dla pewnego \(\displaystyle{ x}\) to pozwalało by wnioskować o tym, że \(\displaystyle{ a=b}\), a to sprzeczność bo \(\displaystyle{ a \neq b}\). Teraz wystarczy zauważyć, że pracując \(\displaystyle{ \mod 2017}\) mamy
\begin{split}
\left( 1+ \frac{1}{2}+ \frac{1}{3}+...+ \frac{1}{2016} \right)2016! & \equiv \sum_{i=1}^{2016} 2016! \times n_i^{-1} \\
& \equiv \sum_{i=1}^{2016} - n_i^{-1} \\
& \equiv \sum_{i=1}^{2016} \left( 2017- n_i^{-1}\right) \\
& \equiv \sum_{n=1}^{2016}n,
\end{split}
gdzie
\(\displaystyle{ n_i^{-1}=\text{odwrotność mod 2017 elementu }i}\)

ponad to drugie przystawanie wynika z Twierdzenie Wilsona, trzecie ma na celu uwypuklić fakt, że liczby jakie pojawiają się w sumie to elementy zbioru \(\displaystyle{ \left\{ 1,2,\dots,2016\right\} }\). A ponieważ każdy jest inny, a my wykorzystaliśmy wszystkie to przedostatnia suma jest pewną permutacją ostatniej sumy stąd czwarta kongruencja. Wystarczy więc policzyć sumę korzystając ze znanego wzory i się jej dobrze przyjrzeć wtedy odpowiedź sama się ujawni.
Chciałam się upewnić czy dobrze zrozumiałam. W pierwszej klasie ciężko umieć arytmetykę modularną.
Moją liczbę
\(\displaystyle{
\left( 1+ \frac{1}{2}+ \frac{1}{3}+...+ \frac{1}{2016} \right)2016!
}\)
dzieląc przez \(\displaystyle{ 2017}\) otrzymuję resztę postaci
\(\displaystyle{
\sum_{n=1}^{2016}n=1+2+3+...+2016 = \frac{1+2016}{2} \cdot 2016=1008 \cdot 2017
}\)
która również jest podzielna przez \(\displaystyle{ 2017}\)
Stąd cała liczba dzieli się przez \(\displaystyle{ 2017}\)
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Podzielność przez 2017

Post autor: Janusz Tracz »

vip123 pisze: 20 gru 2022, o 14:14 Moją liczbę
\(\displaystyle{
\left( 1+ \frac{1}{2}+ \frac{1}{3}+...+ \frac{1}{2016} \right)2016!
}\)
dzieląc przez \(\displaystyle{ 2017}\) otrzymuję resztę postaci
\(\displaystyle{
\sum_{n=1}^{2016}n=1+2+3+...+2016 = \frac{1+2016}{2} \cdot 2016=1008 \cdot 2017
}\)
która również jest podzielna przez \(\displaystyle{ 2017}\)
Stąd cała liczba dzieli się przez \(\displaystyle{ 2017}\)
Dokładnie tak. Tylko to nie resztę otrzymujesz lecz inną liczbę która ma taką samą resztę. A z tego, że ta inna liczba ma resztę zero wynika już podzielność.
Jan Kraszewski
Administrator
Administrator
Posty: 34128
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Podzielność przez 2017

Post autor: Jan Kraszewski »

vip123 pisze: 20 gru 2022, o 14:14Chciałam się upewnić czy dobrze zrozumiałam. W pierwszej klasie ciężko umieć arytmetykę modularną.
Wersja timona92 nie wymaga arytmetyki modularnej.

JK
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Podzielność przez 2017

Post autor: a4karo »

To zadanie rodzi kolejne: dla jakich `N` liczba
\(\displaystyle{ \red{N!\left(1+\frac12+\frac13+\cdots+\frac{1}{N-2}+\frac{1}{N-1}+\frac{1}{N}\right)}}\) jest podzielna przez `N+1`.

W przypadku parzystych `N` odpowiedź pozytywną daje metoda pokazana przez timona92 wykorzystująca fakt, że wyrazy sumy można połączyć w pary i
\(\displaystyle{ \frac{1}{k}+\frac{1}{N+1}=\frac{N+1}{k(N+1-k})}\)

Gdy `N=2n-1` jest nieparzyste postępujemy tak samo, ale pozostaje środkowy wyraz sumy w nawiasie `1/n`, który nie ma pary. Musimy zatem odpowiedzieć na pytanie kiedy `N+1=2n` dzieli \(\displaystyle{ \frac{N!}{n}=\magenta{1\cdot2\cdot\dots\cdot(n-1)}\cdot\blue{(n+1)\cdot\dots\cdot(2n-1)}}\)
Dla `N=1` czerwona liczba jest równa `1` i nie jest podzielna przez `2`.
Podobnie dla `N=3` otrzymujemy `11`, co nie dzieli `24`.
Załóżmy zatem, że \(\displaystyle{ N\ge 5}\), czyli \(\displaystyle{ n\ge 3}\)
Niebieskich czynników jest co najmniej dwa, a zatem dwójkę, która ma dzielić `2n` możemy "zabrać" z jednego z nich.
Pozostaje zatem do rozstrzygnięcia kiedy fiolet dzieli `n`.
Oczywiście gdy `n` jest liczbą pierwszą, to to się nie uda.
Jeżeli `n` nie jest pierwsze i rozkłada się na dwa różne czynniki, to oba są filetowe i podzielność zachodzi.
Pozostaje przypadek gdy `n=p^2`, gdzie `p` jest liczbą pierwszą. I tu znów dwa przypadki:
Jeżeli `p>2`, to `p<2p<p^2=n`, wiec `p^2` dzieli fioletową liczbę i jest dobrze.
Jeżeli zaś `p=2`, to `n=4` i `N=7` i widać, że \(\displaystyle{ 1\cdot2\cdot3\cdot 5\cdot 6\cdot 7}\) nie dzieli `2n=8`

Teza zadanie zachodzi zatem dla wszystkich `N` parzystych oraz dla nieparzystych `N` większych od `7` i takich, że \(\displaystyle{ \frac{N+1}{2}}\) nie jest liczbą pierwszą.
Ostatnio zmieniony 21 gru 2022, o 15:57 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
ODPOWIEDZ