[Teoria liczb]Zwardoń 2009 - 7

[WolfusA]

Dana jest liczba pierwsza\(\displaystyle{ p > 2}\). Wyznaczyć najmniejszą liczbę całkowitą dodatnią \(\displaystyle{ n}\), dla której z każdego zbioru \(\displaystyle{ n}\) kwadratów liczb całkowitych niepodzielnych przez \(\displaystyle{ p}\) można wybrać niepusty podzbiór o iloczynie elementów dającym resztę \(\displaystyle{ 1}\) z dzielenia przez \(\displaystyle{ p}\).
Proszę o sprawdzenie rozwiązania:
Odpowiedź to \(\displaystyle{ \frac{p-1}{2}}\).
Dla \(\displaystyle{ p=3}\) teza zadania jest oczywista, bierzemy podzbiór jednoelementowy. Niech dalej \(\displaystyle{ p>3}\). Najpierw doza logiki: jeśli można wybrać żądany podzbiór dla dowolnych \(\displaystyle{ n}\) kwadratów liczb, to można to także zrobić dla dowolnych \(\displaystyle{ n+1}\) kwadratów liczb. Odwrotnie, jeśli nie można dla pewnych \(\displaystyle{ n}\) kwadratów liczb wybrać podzbioru, to nie można tego zrobić dla pewnych \(\displaystyle{ n-1}\) kwadratów liczb.
Wystarczy więc wykazać, że dla pewnego zbioru \(\displaystyle{ \frac{p-1}{2} -1}\)kwadratów liczb całkowitych teza nie zachodzi, zaś zachodzi dla \(\displaystyle{ \frac{p-1}{2}}\) dowolnych kwadratów liczb całkowitych.
Dowód pierwszego zdania: weźmy \(\displaystyle{ \frac{p-1}{2} -1}\) liczb \(\displaystyle{ 2^2}\). Skoro \(\displaystyle{ p|2^{p-1}-1}\), to nie może być \(\displaystyle{ p|2^{p-3}-1}\), bo oznaczałoby to \(\displaystyle{ p|3}\). Czyli \(\displaystyle{ 2^{2\cdot \left(\frac{p-1}{2} -1\right)}}\) jest niepodzielne przez \(\displaystyle{ p}\).
Dowód drugiego zdania: rozważmy zbiór \(\displaystyle{ \lbrace x_1^2,x_2^2,...,x_n^2\rbrace}\), gdzie \(\displaystyle{ x_i\in Z}\) i \(\displaystyle{ n=\frac{p-1}{2}}\). Załóżmy, że wybranie podzbioru zgodnego z warunkami zadania jest niemożliwe. Liczby \(\displaystyle{ x_1^2,(x_1x_2)^2,...,(x_1x_2\cdot...\cdot x_n)^2}\) nie dają reszty \(\displaystyle{ 0}\) ani \(\displaystyle{ 1}\) (odpowiednio z założenia zadania i założenia nie wprost) z dzielenia przez \(\displaystyle{ p}\). Dla \(\displaystyle{ p>2}\) mamy \(\displaystyle{ \frac{p-1}{2}-1}\) reszt kwadratowych modulo \(\displaystyle{ p}\) różnych od \(\displaystyle{ 0}\) i \(\displaystyle{ 1}\). Zatem na mocy zasady szufladkowej istnieją \(\displaystyle{ k,l\in Z\wedge 1\le k<l\le n}\) dla których \(\displaystyle{ p|(x_1...x_k)^2-(x_1...x_l)^2=(x_1...x_l)^2((x_{l+1}...x_k)^2-1)}\). Liczby \(\displaystyle{ x_i}\) są z założenia niepodzielne przez \(\displaystyle{ p}\), zatem \(\displaystyle{ p|(x_{l+1}...x_k)^2-1}\). Sprzeczność z założeniem nie wprost.

[niunix98]

Rozwiązanie jest poprawne:)