Trzy liczby

[mol_ksiazkowy]

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]

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

[arek1357]

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

[Dasio11]

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]

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...