Podzielność wyrażenia z dwoma zmiennymi

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
matemix
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 10 cze 2008, o 19:38
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 12 razy
Pomógł: 1 raz

Podzielność wyrażenia z dwoma zmiennymi

Post autor: matemix »

Jak znaleźć naturalne potęgi x oraz y, takie, że otrzymamy najmniejszą możliwą (nieujemną) różnicę wyrażenia:

\(\displaystyle{ 2^{x+y}-w^{x}}\)

podzielną przez liczbę naturalną p. Przy czym w to dowolna liczba naturalna równa lub większa niż 1.

W szczególnym przypadku, gdy \(\displaystyle{ w=1}\) musimy znaleźć najmniejszą potęgę \(\displaystyle{ 2^{n}-1}\), taką, że \(\displaystyle{ p}\) dzieli tę liczbę bez reszty. W tym wypadku, chyba najlepszym znanym algorytmem znajdowania takiej potęgi \(\displaystyle{ n}\) jest redukcja Pohliga-Hellmana (która najlepiej sprawdzi się dla gładkich \(\displaystyle{ p}\)).

Pomijając jednak ten szczególny przypadek. Co z przypadkami \(\displaystyle{ w>1}\). Czy dla każdego p zawsze istnieje \(\displaystyle{ 2^{x+y}-w^{x}}\) podzielne przez p? Czy znajdowanie takich potęg to problem logarytmiczny? Jak w najszybszym czasie znajdować rozwiązania tego problemu?
ODPOWIEDZ