[Teoria liczb] Podzielnosc

Zadania z kółek matematycznych lub obozów przygotowujących do OM. Problemy z minionych olimpiad i konkursów matematycznych.
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Awatar użytkownika
przemk20
Użytkownik
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

[Teoria liczb] Podzielnosc

Post autor: przemk20 » 26 paź 2007, o 17:14

znajdz wszystkie liczby naturalne \(\displaystyle{ n}\) dla ktorych zachodzi podzielnosc:
\(\displaystyle{ (2n+1) \ | \ (n!)^2 - 1}\)
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

andkom
Użytkownik
Użytkownik
Posty: 636
Rejestracja: 10 paź 2007, o 12:57
Płeć: Mężczyzna
Lokalizacja: Łódź
Pomógł: 350 razy

[Teoria liczb] Podzielnosc

Post autor: andkom » 26 paź 2007, o 20:00

Podzielność powyższa zachodzi wtedy i tylko wtedy, gdy n jest nieparzyste i 2n+1 jest liczbą pierwszą.
Wsk. Przypadek, gdy 2n+1 jest liczbą złożoną jest łatwy (bo wtedy \(\displaystyle{ (2n+1)|(n!)^2}\)). W przypadku, gdy 2n+1 jest liczbę pierwszą można się podeprzeć twierdzeniem Wilsona.
Twierdzenie Wilsona mówi, że jeśli p jest liczbą pierwszą, to \(\displaystyle{ p|(p-1)!+1}\).
Żeby skorzystać z Twierdzenia Wilsona wystarczy zauważyć, że
\(\displaystyle{ (2n)!\equiv(-1)^n(n!)^2\mod(2n+1)}\)

=======================================================
a z czego wynika, ze
\(\displaystyle{ (2n)! \equiv (-1)^n (n!)^2 \mod (2n+1)}\)
Z tego, że dla \(\displaystyle{ k\in\{n+1,n+2,\ldots,2n\}}\) mamy
\(\displaystyle{ k=(2n+1)-[(2n+1)-k]\equiv-[(2n+1)-k]\mod(2n+1)}\)
czyli
\(\displaystyle{ k\equiv(-1)[(2n+1)-k]\mod(2n+1)}\)
Po pomnożeniu stronami n takich kongruencji (dla \(\displaystyle{ k\in\{n+1,n+2,\ldots,2n\}}\)) dostajemy

\(\displaystyle{ (n+1)(n+2)\cdots(2n)\equiv(-1)^nn!\mod(2n+1)}\)
a stąd mamy
\(\displaystyle{ (2n)!\equiv(-1)^n(n!)^2\mod(2n+1)}\)
Ostatnio zmieniony 15 wrz 2008, o 22:01 przez andkom, łącznie zmieniany 1 raz.

Awatar użytkownika
przemk20
Użytkownik
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

[Teoria liczb] Podzielnosc

Post autor: przemk20 » 27 paź 2007, o 17:29

a z czego wynika, ze
\(\displaystyle{ (2n)! \equiv (-1)^n (n!)^2 \mod (2n+1) \\}\)

ODPOWIEDZ