suma reszt
- mol_ksiazkowy
- Użytkownik
- Posty: 11374
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
suma reszt
Dana jest Liczba pierwsza \(\displaystyle{ p 2}\). Dla każdej \(\displaystyle{ k \{1,...,p-1 \}}\) wyznaczam resztę\(\displaystyle{ r_k}\) z dzielenia liczby \(\displaystyle{ k^p}\) przez \(\displaystyle{ p^2}\). Ile wynosi suma tak otrzymanych rk....?
- max
- Użytkownik
- Posty: 3306
- Rejestracja: 10 gru 2005, o 17:48
- Płeć: Mężczyzna
- Lokalizacja: Lebendigentanz
- Podziękował: 37 razy
- Pomógł: 778 razy
suma reszt
Niech \(\displaystyle{ r_{k} = x}\) przy ustalonym \(\displaystyle{ k \{1, \ldots, p-1\}}\). Wtedy:
\(\displaystyle{ k^{p}\equiv x od{p^{2}}}\)
Ponieważ \(\displaystyle{ p|p^{2}}\), to również:
\(\displaystyle{ k^{p} \equiv x od{p}}\)
I tu była bzdura, bo korzystając z małego tw Fermata otrzymujemy co najwyżej:
\(\displaystyle{ x \equiv k od{p}}\)
\(\displaystyle{ k^{p}\equiv x od{p^{2}}}\)
Ponieważ \(\displaystyle{ p|p^{2}}\), to również:
\(\displaystyle{ k^{p} \equiv x od{p}}\)
I tu była bzdura, bo korzystając z małego tw Fermata otrzymujemy co najwyżej:
\(\displaystyle{ x \equiv k od{p}}\)
Ostatnio zmieniony 25 maja 2007, o 18:55 przez max, łącznie zmieniany 1 raz.
- przemk20
- Użytkownik
- Posty: 1094
- Rejestracja: 6 gru 2006, o 22:47
- Płeć: Mężczyzna
- Lokalizacja: Olesno
- Podziękował: 45 razy
- Pomógł: 236 razy
suma reszt
chodzi mi o taki fakt ta suma wynosi;
\(\displaystyle{ 1+2+..+p-1}\)
a gdy
\(\displaystyle{ p^2 > x > p}\)
to wtedy max sumuje
\(\displaystyle{ x (mod p) < p, \ \}\)
a skladnik sumy powinien wynosic
\(\displaystyle{ x (mod p^2) > p}\)
\(\displaystyle{ 1+2+..+p-1}\)
a gdy
\(\displaystyle{ p^2 > x > p}\)
to wtedy max sumuje
\(\displaystyle{ x (mod p) < p, \ \}\)
a skladnik sumy powinien wynosic
\(\displaystyle{ x (mod p^2) > p}\)
- Tristan
- Użytkownik
- Posty: 2353
- Rejestracja: 24 kwie 2005, o 14:28
- Płeć: Mężczyzna
- Podziękował: 27 razy
- Pomógł: 557 razy
suma reszt
Wybacz, ale nie błyszczę dzisiaj inteligencją i wciąż nie rozumiem. Dlatego podam przykład, a Ty, jeśli możesz, podasz mi na nim co Ci się nie zgadza i dlaczego.
Niech \(\displaystyle{ p=5}\). Mamy wtedy, że \(\displaystyle{ k \{ 1,2,3,4 \}}\) oraz:
\(\displaystyle{ 1^5 \equiv 1( mod\ 25) \\ 2^5 \equiv 7 ( mod\ 25) \\ 3^5 \equiv 18 ( mod\ 25) \\ 4^5 \equiv 24 ( mod\ 25)}\)
Szukana suma wynosi więc \(\displaystyle{ 1+7+18+24=2 25= \frac{5-1}{2} 5^2}\).
Niech \(\displaystyle{ p=5}\). Mamy wtedy, że \(\displaystyle{ k \{ 1,2,3,4 \}}\) oraz:
\(\displaystyle{ 1^5 \equiv 1( mod\ 25) \\ 2^5 \equiv 7 ( mod\ 25) \\ 3^5 \equiv 18 ( mod\ 25) \\ 4^5 \equiv 24 ( mod\ 25)}\)
Szukana suma wynosi więc \(\displaystyle{ 1+7+18+24=2 25= \frac{5-1}{2} 5^2}\).
- Tristan
- Użytkownik
- Posty: 2353
- Rejestracja: 24 kwie 2005, o 14:28
- Płeć: Mężczyzna
- Podziękował: 27 razy
- Pomógł: 557 razy
suma reszt
Nie mam żadnego konkretnego dowodu. Sprawdziwszy kilka początkowych przypadków doszedłem do wzoru, który pokazałem , ale sprowadza się to do wykazania, że \(\displaystyle{ n^p +(p-n)^p \equiv 0 ( mod\ p^2)}\), dla \(\displaystyle{ n \{ 1,2, ... ,p-1 \}}\). A nad dowodem tej kongruencji wciąż myślę
- Tristan
- Użytkownik
- Posty: 2353
- Rejestracja: 24 kwie 2005, o 14:28
- Płeć: Mężczyzna
- Podziękował: 27 razy
- Pomógł: 557 razy
suma reszt
Dziękuję kwadraciku . Wychodzi bezproblemowo. Teraz tylko opis...
Oczywiście \(\displaystyle{ n, p-n}\) są względnie pierwsze z \(\displaystyle{ p^2}\), więc przystają do czegoś większego od zera i mniejszego od \(\displaystyle{ p^2}\). A skoro zachodzi ta kongruencja \(\displaystyle{ n^p + (p-n)^p \equiv (mod\ p^2)}\), to znaczy, że \(\displaystyle{ n^p}\) i \(\displaystyle{ (p-n)^p}\) przystają do takich reszt, których suma jest równa \(\displaystyle{ p^2}\) ( bo jest większa od zera i mniejsza od \(\displaystyle{ 2p^2}\)). Ponieważ danych kongruencji mamy \(\displaystyle{ p-1}\) i łączymy je w pary, dostajemy więc \(\displaystyle{ \frac{p-1}{2}}\) wyrażeń, z których każde ma wartość \(\displaystyle{ p^2}\), stąd szukana suma wynosi \(\displaystyle{ \frac{p-1}{2} p^2}\).
Oczywiście \(\displaystyle{ n, p-n}\) są względnie pierwsze z \(\displaystyle{ p^2}\), więc przystają do czegoś większego od zera i mniejszego od \(\displaystyle{ p^2}\). A skoro zachodzi ta kongruencja \(\displaystyle{ n^p + (p-n)^p \equiv (mod\ p^2)}\), to znaczy, że \(\displaystyle{ n^p}\) i \(\displaystyle{ (p-n)^p}\) przystają do takich reszt, których suma jest równa \(\displaystyle{ p^2}\) ( bo jest większa od zera i mniejsza od \(\displaystyle{ 2p^2}\)). Ponieważ danych kongruencji mamy \(\displaystyle{ p-1}\) i łączymy je w pary, dostajemy więc \(\displaystyle{ \frac{p-1}{2}}\) wyrażeń, z których każde ma wartość \(\displaystyle{ p^2}\), stąd szukana suma wynosi \(\displaystyle{ \frac{p-1}{2} p^2}\).
-
- Użytkownik
- Posty: 15
- Rejestracja: 22 cze 2007, o 21:19
- Płeć: Mężczyzna
- Lokalizacja: Danzig
- Pomógł: 4 razy
suma reszt
wiem ze to tak troche pozno, ale lepsze to niz nic --- co kwadracik napisal to nie wiem - ja podam swoje rozumowanie
skoro p jest pierwsza i p≠2 to p jest liczba nieparzysta - czyli 2|(p-1)
niech r
skoro p jest pierwsza i p≠2 to p jest liczba nieparzysta - czyli 2|(p-1)
niech r