szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna
PostNapisane: 25 lis 2018, o 23:14 
Użytkownik
Avatar użytkownika

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

Posty: 44
Lokalizacja: Warszawa
Rozwiązanie jest poprawne:)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 [Teoria liczb]Zwardoń 2009 - 7  WolfusA  0
 [Teoria liczb]Zwardoń 2009 - 7 - zadanie 2  WolfusA  0
 [Teoria liczb] Suma odwrotności dzielników liczby naturalnej  Sun Tsu  2
 [Teoria liczb] Równanie z piętnastą potęgą  niepokonanytornister  6
 [Równanie] Wykaż, że istnieje nieskończenie wiele liczb.  Zahion  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl