Witam.
Wykazać, że dla dowolnej liczby pierwszej \(\displaystyle{ p}\) oraz liczby naturalnej \(\displaystyle{ l< p-1}\) liczba
\(\displaystyle{ 1^{l}+2^{l}+...+(p-1)^{l}}\) jest podzielna przez \(\displaystyle{ p}\).
Będę wdzięczny za pomoc.
Podzielność przez liczbę pierwszą
-
Vax
- Użytkownik
- Posty: 2913
- Rejestracja: 27 kwie 2010, o 22:07
- Płeć: Mężczyzna
- Lokalizacja: Biała Podlaska / Warszawa
- Podziękował: 4 razy
- Pomógł: 612 razy
Podzielność przez liczbę pierwszą
Niech \(\displaystyle{ g}\) będzie generatorem \(\displaystyle{ \pmod{p}}\), wówczas \(\displaystyle{ \lbrace 1, \ 2, \ ... \, p-1\rbrace = \lbrace g^1, \ g^2, \ ... \, g^{p-1}\rbrace}\), więc teza jest równoważna:
\(\displaystyle{ 0 \equiv g^l + g^{2l} + ... + g^{(p-1)l} \equiv g^l(1+g^l+..+g^{(p-2)l}) \equiv g^l \cdot \frac{g^{(p-1)l}-1}{g^l-1} \pmod{p}}\)
Naturalnie z małego twierdzenia Fermata \(\displaystyle{ g^{(p-1)l}-1 \equiv 1-1 \equiv 0\pmod{p}}\)
Pozostaje więc pokazać, że \(\displaystyle{ g^l \not\equiv 1\pmod {p}}\). Jakby nie wprost było inaczej, to \(\displaystyle{ p-1 = ord_p (g) \le l}\) sprzeczność.
\(\displaystyle{ 0 \equiv g^l + g^{2l} + ... + g^{(p-1)l} \equiv g^l(1+g^l+..+g^{(p-2)l}) \equiv g^l \cdot \frac{g^{(p-1)l}-1}{g^l-1} \pmod{p}}\)
Naturalnie z małego twierdzenia Fermata \(\displaystyle{ g^{(p-1)l}-1 \equiv 1-1 \equiv 0\pmod{p}}\)
Pozostaje więc pokazać, że \(\displaystyle{ g^l \not\equiv 1\pmod {p}}\). Jakby nie wprost było inaczej, to \(\displaystyle{ p-1 = ord_p (g) \le l}\) sprzeczność.
-
porfirion
- Użytkownik
- Posty: 319
- Rejestracja: 6 gru 2011, o 20:54
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 11 razy
- Pomógł: 26 razy
Podzielność przez liczbę pierwszą
D-d elementarny bez słów na \(\displaystyle{ g}\) itd. (chyba poprawny :p ) :
Zróbmy sobie ładną tabelkę:
\(\displaystyle{ n^{k}-(n-1)^{k}= {k\choose 1} n^{k-1}-{k\choose 2}n^{k-2}+...+{k\choose k}(-1)^{k}}\)
\(\displaystyle{ (n-1)^{k}-(n-2)^{k}= {k\choose 1} (n-1)^{k-1}-{k\choose 2}(n-1)^{k-2}+...+{k\choose k}(-1)^{k}}\)
...
\(\displaystyle{ 2^{k}-1^{k}= {k\choose 1}2^{k-1}-{k\choose 2}2^{k-2}+...+{k\choose k}(-1)^{k}}\)
\(\displaystyle{ 1^{k}-0^{k}={k\choose 1}1^{k-1}-{k\choose 2}1^{k-2}+...+{k\choose k}(-1)^{k}}\)
Dodając wszystko stronami:
\(\displaystyle{ n^{k}={k\choose 1} f_{k-1}(n)-{k\choose 2} f_{k-2}(n)+...+{k\choose k}(-1)^{k} \cdot n}\)
Skąd:
\(\displaystyle{ f_{k-1}(n)= \frac{n^{k}+{k\choose 2}f_{k-2}(n)-...-{k\choose k}(-1)^{k} \cdot n}{k}}\)
Podstawiając \(\displaystyle{ k-1=l}\) i \(\displaystyle{ n=p-1}\):
\(\displaystyle{ f_{l}(p-1)= \frac{(p-1)^{l+1}+{l+1\choose 2}f_{l-1}(p-1)-...-{l+1\choose l+1}(-1)^{l+1} \cdot (p-1)}{l+1}}\)
Skąd na mocy indukcji (dla mniejszych \(\displaystyle{ f_{i}(p-1)}\) mamy już tezę), mamy że \(\displaystyle{ f_{l}(p-1)\equiv_{p}0}\) wtedy gdy \(\displaystyle{ (p-1)^{l+1}-(-1)^{l+1}(p-1)\equiv_{p}0}\)
a to ostatnie to \(\displaystyle{ (p-1)^{l}\equiv(-1)^{l}}\) C.K.D.
UWAGA: dzieleniem przez \(\displaystyle{ l+1}\) się nie przejmujemy, bo z założenia \(\displaystyle{ l+1<p}\)
Zróbmy sobie ładną tabelkę:
\(\displaystyle{ n^{k}-(n-1)^{k}= {k\choose 1} n^{k-1}-{k\choose 2}n^{k-2}+...+{k\choose k}(-1)^{k}}\)
\(\displaystyle{ (n-1)^{k}-(n-2)^{k}= {k\choose 1} (n-1)^{k-1}-{k\choose 2}(n-1)^{k-2}+...+{k\choose k}(-1)^{k}}\)
...
\(\displaystyle{ 2^{k}-1^{k}= {k\choose 1}2^{k-1}-{k\choose 2}2^{k-2}+...+{k\choose k}(-1)^{k}}\)
\(\displaystyle{ 1^{k}-0^{k}={k\choose 1}1^{k-1}-{k\choose 2}1^{k-2}+...+{k\choose k}(-1)^{k}}\)
Dodając wszystko stronami:
\(\displaystyle{ n^{k}={k\choose 1} f_{k-1}(n)-{k\choose 2} f_{k-2}(n)+...+{k\choose k}(-1)^{k} \cdot n}\)
Skąd:
\(\displaystyle{ f_{k-1}(n)= \frac{n^{k}+{k\choose 2}f_{k-2}(n)-...-{k\choose k}(-1)^{k} \cdot n}{k}}\)
Podstawiając \(\displaystyle{ k-1=l}\) i \(\displaystyle{ n=p-1}\):
\(\displaystyle{ f_{l}(p-1)= \frac{(p-1)^{l+1}+{l+1\choose 2}f_{l-1}(p-1)-...-{l+1\choose l+1}(-1)^{l+1} \cdot (p-1)}{l+1}}\)
Skąd na mocy indukcji (dla mniejszych \(\displaystyle{ f_{i}(p-1)}\) mamy już tezę), mamy że \(\displaystyle{ f_{l}(p-1)\equiv_{p}0}\) wtedy gdy \(\displaystyle{ (p-1)^{l+1}-(-1)^{l+1}(p-1)\equiv_{p}0}\)
a to ostatnie to \(\displaystyle{ (p-1)^{l}\equiv(-1)^{l}}\) C.K.D.
UWAGA: dzieleniem przez \(\displaystyle{ l+1}\) się nie przejmujemy, bo z założenia \(\displaystyle{ l+1<p}\)