Trzy liczby
-
mol_ksiazkowy
- Użytkownik
- Posty: 13537
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3436 razy
- Pomógł: 812 razy
Trzy liczby
Dane są liczby naturalne \(\displaystyle{ n }\) i \(\displaystyle{ N}\). Udowodnić, że istnieje \(\displaystyle{ k}\) takie, że \(\displaystyle{ 2^k - n}\) ma co najmniej \(\displaystyle{ N}\) różnych dzielników pierwszych.
-
Brombal
- Użytkownik
- Posty: 594
- Rejestracja: 1 gru 2015, o 21:49
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 7 razy
- Pomógł: 46 razy
Re: Trzy liczby
Nie potrafię znaleźć \(\displaystyle{ k}\)
\(\displaystyle{ n=10}\) i \(\displaystyle{ N=1}\)
Dodano po 24 minutach 29 sekundach:
Właściwie to jest dla tego rozwiązanie \(\displaystyle{ k=0}\)
Poprawiam na
\(\displaystyle{ n=22}\) i\(\displaystyle{ N=1}\)
\(\displaystyle{ n=10}\) i \(\displaystyle{ N=1}\)
Dodano po 24 minutach 29 sekundach:
Właściwie to jest dla tego rozwiązanie \(\displaystyle{ k=0}\)
Poprawiam na
\(\displaystyle{ n=22}\) i\(\displaystyle{ N=1}\)
-
arek1357
Re: Trzy liczby
Generalnie w tym zadaniu mamy udowodnić, że zbiór dzielników pierwszych liczby:
\(\displaystyle{ 2^k-n}\) - rośnie do nieskończoności wraz ze wzrostem liczby \(\displaystyle{ k}\) i dla dowolnego \(\displaystyle{ n}\)
Generalnie według mnie chodzi tu o to aby wykazać, że zawsze znajdzie się taka liczba \(\displaystyle{ k}\) dla której układ równań:
\(\displaystyle{ 2^k=n \mod p_{1}}\)
\(\displaystyle{ 2^k=n \mod p_{2}}\)
............................................
\(\displaystyle{ 2^k=n \mod p_{s}}\)
bez względu na liczbę \(\displaystyle{ s}\) ma rozwiązanie... \(\displaystyle{ p_{i}}\) - parami różne liczby pierwsze...
weźmy np. pierwsze równanie:
\(\displaystyle{ 2^k=n \mod p_{1}}\)
Po zastanowieniu się równanie to będzie miało rozwiązanie jeżeli dwójka będzie generatorem grupy multiplikatywnej:
\(\displaystyle{ \ZZ^*_{p_{1}}}\)
Grupa ta będzie cykliczna jeżeli:
\(\displaystyle{ p_{1}-1=2p^c}\) , można przyjąć, że \(\displaystyle{ c=1}\)
Musimy zażądać aby dwójka była generatorem w każdej z tych grup:
\(\displaystyle{ \ZZ^*_{p_{i}}}\) a każda grupa multiplikatywna ma po:
\(\displaystyle{ 2p}\) - elementów , oczywiście \(\displaystyle{ p}\) są między sobą różne...
Oczywiście skoro:
\(\displaystyle{ 2^{k_{1}} =n \mod p_{1}}\)
\(\displaystyle{ 2^{k_{2}} =n \mod p_{2}}\)
...................................................
\(\displaystyle{ 2^{k_{s}} =n \mod p_{s}}\)
Pasuje zastanowić się czy można znaleźć jedno takie \(\displaystyle{ k}\) dla wszystkich...
\(\displaystyle{ k_{i}}\) jest jako najmniejsze ale można to rozszerzać
na:
\(\displaystyle{ l_{i}=k_{i}+x\left( p_{i}-1\right) }\)
teraz np. czy można poszukać takie \(\displaystyle{ l}\) dla np. dwóch: \(\displaystyle{ s=2}\)
\(\displaystyle{ l_{j}=k_{j}+y\left( p_{j}-1\right) }\)
Czyli czy może się zdarzyć, że:
\(\displaystyle{ l_{i}=l_{j} }\)
lub:
\(\displaystyle{ k_{i}+x\left( p_{i}-1\right)=k_{j}+y\left( p_{j}-1\right)}\)
Ale założyliśmy, że:
\(\displaystyle{ p_{i}-1=2p , p_{j}-1=2q}\)
czyli mamy równanie:
\(\displaystyle{ k_{i}+2px=k_{j}+2qy}\)
lub:
\(\displaystyle{ 2px-2qy=k_{j}-k_{i}}\)
czyli czy istnieją takie całkowite: \(\displaystyle{ x , y}\) , że powyższe równanie ma rozwiązanie
Wystarczy założyć, żeby:
\(\displaystyle{ 2| k_{j}-k_{i}}\) - wtedy to równanie diofantyczne liniowe będzie miało rozwiązanie a więc takie \(\displaystyle{ k}\) "wspólne" na pewno się znajdzie
i będzie:
\(\displaystyle{ 2^k=n \mod p_{1}}\)
\(\displaystyle{ 2^k=n \mod p_{2}}\)
Oczywiście ja tu napisałem przykładowo dla dwóch pierwszych ale łatwo to rozszerzyć dla dowolnej ilości liczb pierwszych, czyli:
\(\displaystyle{ N=s}\)
\(\displaystyle{ 2^k-n}\) - rośnie do nieskończoności wraz ze wzrostem liczby \(\displaystyle{ k}\) i dla dowolnego \(\displaystyle{ n}\)
Generalnie według mnie chodzi tu o to aby wykazać, że zawsze znajdzie się taka liczba \(\displaystyle{ k}\) dla której układ równań:
\(\displaystyle{ 2^k=n \mod p_{1}}\)
\(\displaystyle{ 2^k=n \mod p_{2}}\)
............................................
\(\displaystyle{ 2^k=n \mod p_{s}}\)
bez względu na liczbę \(\displaystyle{ s}\) ma rozwiązanie... \(\displaystyle{ p_{i}}\) - parami różne liczby pierwsze...
weźmy np. pierwsze równanie:
\(\displaystyle{ 2^k=n \mod p_{1}}\)
Po zastanowieniu się równanie to będzie miało rozwiązanie jeżeli dwójka będzie generatorem grupy multiplikatywnej:
\(\displaystyle{ \ZZ^*_{p_{1}}}\)
Grupa ta będzie cykliczna jeżeli:
\(\displaystyle{ p_{1}-1=2p^c}\) , można przyjąć, że \(\displaystyle{ c=1}\)
Musimy zażądać aby dwójka była generatorem w każdej z tych grup:
\(\displaystyle{ \ZZ^*_{p_{i}}}\) a każda grupa multiplikatywna ma po:
\(\displaystyle{ 2p}\) - elementów , oczywiście \(\displaystyle{ p}\) są między sobą różne...
Oczywiście skoro:
\(\displaystyle{ 2^{k_{1}} =n \mod p_{1}}\)
\(\displaystyle{ 2^{k_{2}} =n \mod p_{2}}\)
...................................................
\(\displaystyle{ 2^{k_{s}} =n \mod p_{s}}\)
Pasuje zastanowić się czy można znaleźć jedno takie \(\displaystyle{ k}\) dla wszystkich...
\(\displaystyle{ k_{i}}\) jest jako najmniejsze ale można to rozszerzać
na:
\(\displaystyle{ l_{i}=k_{i}+x\left( p_{i}-1\right) }\)
teraz np. czy można poszukać takie \(\displaystyle{ l}\) dla np. dwóch: \(\displaystyle{ s=2}\)
\(\displaystyle{ l_{j}=k_{j}+y\left( p_{j}-1\right) }\)
Czyli czy może się zdarzyć, że:
\(\displaystyle{ l_{i}=l_{j} }\)
lub:
\(\displaystyle{ k_{i}+x\left( p_{i}-1\right)=k_{j}+y\left( p_{j}-1\right)}\)
Ale założyliśmy, że:
\(\displaystyle{ p_{i}-1=2p , p_{j}-1=2q}\)
czyli mamy równanie:
\(\displaystyle{ k_{i}+2px=k_{j}+2qy}\)
lub:
\(\displaystyle{ 2px-2qy=k_{j}-k_{i}}\)
czyli czy istnieją takie całkowite: \(\displaystyle{ x , y}\) , że powyższe równanie ma rozwiązanie
Wystarczy założyć, żeby:
\(\displaystyle{ 2| k_{j}-k_{i}}\) - wtedy to równanie diofantyczne liniowe będzie miało rozwiązanie a więc takie \(\displaystyle{ k}\) "wspólne" na pewno się znajdzie
i będzie:
\(\displaystyle{ 2^k=n \mod p_{1}}\)
\(\displaystyle{ 2^k=n \mod p_{2}}\)
Oczywiście ja tu napisałem przykładowo dla dwóch pierwszych ale łatwo to rozszerzyć dla dowolnej ilości liczb pierwszych, czyli:
\(\displaystyle{ N=s}\)
-
Dasio11
- Moderator
- Posty: 10307
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 41 razy
- Pomógł: 2431 razy
Re: Trzy liczby
Brakuje Ci tylko dowodu, że dla dowolnego \(\displaystyle{ N}\) można znaleźć takie nieparzyste liczby pierwsze \(\displaystyle{ p_1, \ldots, p_N}\), że dwójka jest generatorem w każdym \(\displaystyle{ \mathbb{Z}_{p_i}^{\times}}\) oraz \(\displaystyle{ p_1-1, \ldots, p_N-1}\) są parami względnie pierwsze. Gdy pominie się warunek względnej pierwszości, jest to problem otwarty, szczególny przypadek hipotezy Artina - powodzenia.
-
arek1357
Re: Trzy liczby
Wiem wiedziałem o tym dlatego traktowałem to bardziej jako zadanie prowadzące do otwartej dyskusji, fajnie że ktoś to zauważył...
\(\displaystyle{ p_{i}-1, i=1,2,3...}\)
Nie będą względnie pierwsze bo dwójkę wszędzie tam wstawiłem...
\(\displaystyle{ p_{i}-1, i=1,2,3...}\)
Nie będą względnie pierwsze bo dwójkę wszędzie tam wstawiłem...
Ostatnio zmieniony 12 lis 2023, o 15:15 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.