[Teoria liczb] Podzielnosc

[przemk20]

znajdz wszystkie liczby naturalne \(\displaystyle{ n}\) dla ktorych zachodzi podzielnosc:
\(\displaystyle{ (2n+1) \ | \ (n!)^2 - 1}\)

[andkom]

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)}\)

[przemk20]

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