Istnienie zbioru
-
mol_ksiazkowy
- Użytkownik
- Posty: 11409
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3155 razy
- Pomógł: 748 razy
Istnienie zbioru
Udowodnić, że jeśli \(\displaystyle{ S}\) jest podzbiorem zbioru liczb pierwszych \(\displaystyle{ S \subset P}\), takim że jeśli \(\displaystyle{ a, b \in S}\), to \(\displaystyle{ ab+4 \in S}\) to \(\displaystyle{ S = \emptyset}\).
Ostatnio zmieniony 16 kwie 2020, o 14:51 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Interpunkcja.
Powód: Interpunkcja.
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Istnienie zbioru
Nie wprost. Niech do zbioru \(\displaystyle{ S}\) należą dwie różne liczby pierwsze \(\displaystyle{ p,q}\), przy czym \(\displaystyle{ p>q}\).
Rozważmy ciąg rekurencyjny określony następująco:
\(\displaystyle{ a_{1}=pq+4, \ a_{n+1}=qa_{n}+4}\)
Ponieważ \(\displaystyle{ p,q\in S, }\) to indukcyjnie łatwo dowodzimy, że dla każdego \(\displaystyle{ n\in \NN^{+}}\) jest \(\displaystyle{ a_{n}\in S}\), co zostawiam jako ćwiczenie dla Czytelnika.
Ponadto również indukcyjnie dowodzimy, że \(\displaystyle{ a_{n}\equiv 4\sum_{k=0}^{n-1}q^{k}\pmod{p}}\)
Dla \(\displaystyle{ n=1}\) jest to jasne, wszak \(\displaystyle{ a_{1}=pq+4\equiv 4\pmod{p}}\)
W kroku indukcyjnym przypuśćmy, że dla pewnego \(\displaystyle{ n\in\NN^{+}}\) jest
\(\displaystyle{ a_{n}\equiv 4\sum_{k=0}^{n-1}q^{k}\pmod{p}}\). Wtenczas mamy
\(\displaystyle{ a_{n+1}=qa_{n}+4\equiv 4+q\cdot 4\sum_{k=0}^{n-1}q^{k}\pmod{p}}\)
i pozostaje skonstatować, że \(\displaystyle{ 4+q\cdot 4\sum_{k=0}^{n-1}q^{k}=4\sum_{k=0}^{n}q^{k}}\), co kończy dowód indukcyjny.
Teraz odnotujmy, że \(\displaystyle{ \sum_{k=0}^{n-1}q^{k}=\frac{q^{n}-1}{q-1}}\) oraz \(\displaystyle{ \NWD(p, q-1)=1}\), wszak liczba \(\displaystyle{ p}\) jest pierwsza i większa niż \(\displaystyle{ q}\). Ponadto \(\displaystyle{ \NWD(p,q)=1}\), zatem z małego twierdzenia Fermata mamy \(\displaystyle{ q^{p-1}\equiv 1\pmod{p}}\). Z tych faktów już łatwo wynika, że \(\displaystyle{ p|a_{p}}\), ponadto \(\displaystyle{ a_{p}>p}\), wszak ciąg \(\displaystyle{ (a_{n})}\) jest w oczywisty sposób rosnący. Ale to jest sprzeczność, gdyż \(\displaystyle{ a_{p}\in S, \ S\subset \PP}\), tj. powinno być \(\displaystyle{ a_{p}\in \PP}\).
Pozostaje kwestia, jak ten warunek traktować dla singletonów, w zależności od interpretacji zbiory \(\displaystyle{ S}\) jako singletony liczby pierwszej działają (jeśli uznamy, że \(\displaystyle{ a,b}\) w warunku muszą być różne – wtedy po prostu nieprawdziwe jest zdanie o istnieniu różnych liczb pierwszych należących do \(\displaystyle{ S}\), więc warunek jest spełniony dla każdej z zera par) i tezę trzeba poprawić, bądź nie działają (jeśli można wziąć \(\displaystyle{ a=b}\)).
Dodano po 20 minutach 43 sekundach:
Ojeju, przepraszam, powinno być \(\displaystyle{ p|a_{p-1}}\), wszak z udowodnionego indukcyjnie lematu mamy
\(\displaystyle{ a_{p-1}\equiv 4\sum_{k=0}^{p-2}q^{k}\pmod{p}}\), zaś \(\displaystyle{ \sum_{k=0}^{p-2}q^{k}=\frac{q^{p-1}-1}{q-1}}\) i to \(\displaystyle{ q^{p-1}-1\equiv 0\pmod{p}}\), nie zaś \(\displaystyle{ q^{p}-1}\).
Moja nieuwaga, ale reszty rozwiązania to nie zmienia.
Rozważmy ciąg rekurencyjny określony następująco:
\(\displaystyle{ a_{1}=pq+4, \ a_{n+1}=qa_{n}+4}\)
Ponieważ \(\displaystyle{ p,q\in S, }\) to indukcyjnie łatwo dowodzimy, że dla każdego \(\displaystyle{ n\in \NN^{+}}\) jest \(\displaystyle{ a_{n}\in S}\), co zostawiam jako ćwiczenie dla Czytelnika.
Ponadto również indukcyjnie dowodzimy, że \(\displaystyle{ a_{n}\equiv 4\sum_{k=0}^{n-1}q^{k}\pmod{p}}\)
Dla \(\displaystyle{ n=1}\) jest to jasne, wszak \(\displaystyle{ a_{1}=pq+4\equiv 4\pmod{p}}\)
W kroku indukcyjnym przypuśćmy, że dla pewnego \(\displaystyle{ n\in\NN^{+}}\) jest
\(\displaystyle{ a_{n}\equiv 4\sum_{k=0}^{n-1}q^{k}\pmod{p}}\). Wtenczas mamy
\(\displaystyle{ a_{n+1}=qa_{n}+4\equiv 4+q\cdot 4\sum_{k=0}^{n-1}q^{k}\pmod{p}}\)
i pozostaje skonstatować, że \(\displaystyle{ 4+q\cdot 4\sum_{k=0}^{n-1}q^{k}=4\sum_{k=0}^{n}q^{k}}\), co kończy dowód indukcyjny.
Teraz odnotujmy, że \(\displaystyle{ \sum_{k=0}^{n-1}q^{k}=\frac{q^{n}-1}{q-1}}\) oraz \(\displaystyle{ \NWD(p, q-1)=1}\), wszak liczba \(\displaystyle{ p}\) jest pierwsza i większa niż \(\displaystyle{ q}\). Ponadto \(\displaystyle{ \NWD(p,q)=1}\), zatem z małego twierdzenia Fermata mamy \(\displaystyle{ q^{p-1}\equiv 1\pmod{p}}\). Z tych faktów już łatwo wynika, że \(\displaystyle{ p|a_{p}}\), ponadto \(\displaystyle{ a_{p}>p}\), wszak ciąg \(\displaystyle{ (a_{n})}\) jest w oczywisty sposób rosnący. Ale to jest sprzeczność, gdyż \(\displaystyle{ a_{p}\in S, \ S\subset \PP}\), tj. powinno być \(\displaystyle{ a_{p}\in \PP}\).
Pozostaje kwestia, jak ten warunek traktować dla singletonów, w zależności od interpretacji zbiory \(\displaystyle{ S}\) jako singletony liczby pierwszej działają (jeśli uznamy, że \(\displaystyle{ a,b}\) w warunku muszą być różne – wtedy po prostu nieprawdziwe jest zdanie o istnieniu różnych liczb pierwszych należących do \(\displaystyle{ S}\), więc warunek jest spełniony dla każdej z zera par) i tezę trzeba poprawić, bądź nie działają (jeśli można wziąć \(\displaystyle{ a=b}\)).
Dodano po 20 minutach 43 sekundach:
Ojeju, przepraszam, powinno być \(\displaystyle{ p|a_{p-1}}\), wszak z udowodnionego indukcyjnie lematu mamy
\(\displaystyle{ a_{p-1}\equiv 4\sum_{k=0}^{p-2}q^{k}\pmod{p}}\), zaś \(\displaystyle{ \sum_{k=0}^{p-2}q^{k}=\frac{q^{p-1}-1}{q-1}}\) i to \(\displaystyle{ q^{p-1}-1\equiv 0\pmod{p}}\), nie zaś \(\displaystyle{ q^{p}-1}\).
Moja nieuwaga, ale reszty rozwiązania to nie zmienia.