Układ równań - dowód

[Elayne]

Dla lepszego zrozumienia przedstawię to na przykladzie.
Załóżmy, że mamy daną liczbę \(\displaystyle{ f}\) np: \(\displaystyle{ 30331}\) i chcemy rozłożyć ją na czynniki pierwsze. Na początku potrzebny nam będzie pierwiastek kwadratowy z \(\displaystyle{ f=30331}\) zaokrąglony w górę do najbliższej liczby całkowitej: \(\displaystyle{ kw=175}\). Następnie wyznaczamy współrzędne wierzchołka paraboli \(\displaystyle{ W=(p,q)}\).
\(\displaystyle{ q=f-kw^2=30331-175^2=-294}\)
\(\displaystyle{ p}\) = liczymy pierwiastek kwadratowy z -q, zaokrąglamy w górę i zmieniamy znak na minus = \(\displaystyle{ -18}\)
Tak więc \(\displaystyle{ W=(-18,-294)}\).
Podstawiamy te dane pod postać kanoniczną funkcji kwadratowej:
\(\displaystyle{ f(x)=a(x-p)^2+q}\) [a zawsze równa się jeden]
\(\displaystyle{ f(x)=(x+18)^2-294=x^2+36x+30}\)
Teraz ustalimy położenie na osi OX punktu \(\displaystyle{ A=(Ax,Ay)}\) przez który przechodzi pęk prostych danych równaniem: \(\displaystyle{ y=2*Ax*k-2*k*x}\) gdzie \(\displaystyle{ k}\) jest dowolną liczbą całkowitą.
\(\displaystyle{ Ax=kw+p=175-18=157}\)
\(\displaystyle{ Ay=0}\)
Tak więc mamy:
\(\displaystyle{ A=(157,0)}\)
\(\displaystyle{ y=314k-2kx}\)

Mamy dwa równania:
\(\displaystyle{ f(x)=x^2+36x+30}\)
\(\displaystyle{ y=314k-2kx}\)

Dla \(\displaystyle{ f(x)=y}\) gdzie \(\displaystyle{ x}\) i \(\displaystyle{ y}\) są liczbami całkowitymi oraz \(\displaystyle{ 0<x<Ax-1}\) mamy dwa rozwiązania:
\(\displaystyle{ 1) x=108, k=159}\)
\(\displaystyle{ 2) x=150, k=1995}\)
Nie czuję się na siłach by opisać sposób rozwiązania tych równań, jest to w miarę proste do zrobienia nawet dla dużych liczb ale opisanie tego jest dosyć zawiłe. Można to też rozwiązać za pomocą programów matematycznych, ale tutaj mamy ograniczenie w wielkości liczb dla jakich jest realne policzyć to - np. w Mathematice powinno zadziałać coś takiego:

Kod: Zaznacz cały

f = 30331  (* rozkładana liczba *)
kw = IntegerPart[Sqrt[f]] + 1; (* pierwiastek z f, zaokrąglenie do góry *)
q = f - kw^2; (* współrzędna q wierzchołka paraboli *)
p = -IntegerPart[Sqrt[-q]] - 1 ; (* współrzędna p wierzchołka paraboli, zaokrąglenie do góry *)
y = 1*(x - p)^2 + q; (* postać kanoniczna funkcji *)
Ax = kw + p (* współrzędna x punktu A *)
Ay = 0 ;(* współrzędna y punktu A *)
m = -2*k*x + 2*Ax*k ;(* równanie pęku prostych *)
Solve[y == m && 0 < x && x < (Ax - 1), {x,k}, Integers] (* rozwiązanie: Ax-x *)

Liczba \(\displaystyle{ 30331}\) ma dwa dzielniki nietrywialne mniejsze od jej pierwiastka kwadratowego, są to:
\(\displaystyle{ 1) 49 (Ax-x=157-108=49)}\)
\(\displaystyle{ 2) 7 (Ax-x=157-150=7)}\)
Gdyby rozkłada liczba była liczba pierwszą to równania nie mają rozwiązań oprócz rozwiązania trywialnego \(\displaystyle{ (x=Ax-1)}\).

Na koniec miałbym pytanie: czy można dowieść że dla dowolnej liczby całkowitej nieparzystej liczba rozwiązań tak utworzonych równań odpowiada liczbie dzielników danej liczby całkowitej nieparzystej mniejszych od jej pierwiastka kwadratowego przez które dzieli się bez reszty?

[torus]

Popatrzmy od końca. Załóżmy, że liczby całkowite \(\displaystyle{ x,k}\) tworzą rozwiązanie równania \(\displaystyle{ f(x)=y}\). Oznaczmy \(\displaystyle{ d=Ax-x}\). Mamy:

\(\displaystyle{ (x-p)^2+q=2dk \Rightarrow k=\frac{(x-p)^2+q}{2d}}\)

Zajmijmy się licznikiem. Mamy: \(\displaystyle{ Ax=kw+p}\) i \(\displaystyle{ q=f-kw^2}\). Stąd licznik jest równy \(\displaystyle{ (x-Ax+kw)^2+f-kw^2=(kw-d)^2+f-kw^2=d^2-2kw\cdot d+f}\). Zatem:

\(\displaystyle{ k=\frac{d}{2}-kw+\frac{f}{2d}}\)

Zakładamy, że \(\displaystyle{ f}\) jest liczbą nieparzystą. Ponieważ \(\displaystyle{ k\in\mathbb{Z}}\), to \(\displaystyle{ d}\) też musi być liczbą nieparzystą oraz być dzielnikiem liczby \(\displaystyle{ f}\). Z założenia o \(\displaystyle{ x}\) wynika, że \(\displaystyle{ 1<Ax-x<Ax}\). Czyli wszystko jest OK.

Dla liczb parzystych ten sposób nie działa. Mam jeszcze dwie uwagi:

Załóżmy, że mamy daną liczbę (...) i chcemy rozłożyć ją na czynniki pierwsze.

Opisana metoda znajduje dowolne dzielniki, więc zostaje jeszcze trochę pracy.

Nie czuję się na siłach by opisać sposób rozwiązania tych równań, jest to w miarę proste do zrobienia nawet dla dużych liczb ale opisanie tego jest dosyć zawiłe.

I tu może być problem, tj. żeby ta metoda cokolwiek wnosiła, musiałby istnieć sposób znajdowania rozwiązań tego równania który byłby łatwiejszy niż znajdowanie dzielników danej liczby innymi sposobami. I dobrze, żeby dało się to opisać i przełożyć na program.

[Elayne]

Dla liczb parzystych jest inny układ równań, dlatego napisałem że chodzi o liczby całkowite nieparzyste. Tak na marginesie dla części liczb całkowitych parzystych ten układ równań jest częściowo prawdziwy. Ewentualnie możemy podzielić liczbę parzystą przez jakaś liczbę tak by otrzymać liczbę całkowitą nieparzystą i wtedy można skorzystać z tego. Jak wspomniałem są znajdowane czynniki danej liczby poniżej jej pierwiastka kwadratowego jeśli są takie.

Co do sposobu rozwiązania tego układu równań, to widzę takie plusy:
- jest możliwość niezależnego podziału obliczeń na kilka komputerów; wystarczy podzielić liczby na grupy, przydzielić grupy do poszczególnych komputerów i wtedy obliczenia wykonywane na jednym komputerze nie są dublowane na innym i nie wpływają w żaden sposób na obliczenia wykonywane na innym komputerze;
- ogólnie ujmując metoda rozwiązania układu równań polega na operowaniu według pewnego schematu więc można to przełożyć na program - układ równań jest też zrobiony według pewnego schematu;
- jeśli liczba f składa się z mniej niż z tysiąca cyfr to obliczenia są wykonywane maksymalnie na czterocyfrowych liczbach - pomijam tu sprawdzenie wyniku końcowego (rozwiązanie układu równań);
- szybkość znalezienia czynników danej liczby zależy od "budowy" liczby;
//Edycja
Chyba jednak spróbuję to wyjaśnić, W tej metodzie ważne jest jaka cyfra jest na jakiej pozycji w obrębie liczby i rozbiciu liczby przynajmniej na osiem grup. Układ równań służy do ustalenia i sprawdzenia wyniku. Gdyby przygotować dane dla cyfry to można zrezygnować z liczenia i skupić się na operacjach logicznych. Liczba pierwsza jest sklejona z przynajmniej dwóch rożnych części a liczba złożona stanowi jedną całość. Weźmy na przykład liczby od \(\displaystyle{ 100}\) do \(\displaystyle{ 102}\). Liczba \(\displaystyle{ 100}\) na trzeciej pozycji od prawej mamy jedynkę, możemy to rozpisać tak:

\(\displaystyle{ 1 \cdot 100}\)

\(\displaystyle{ 2 \cdot 50}\)

\(\displaystyle{ 4 \cdot 25}\)

\(\displaystyle{ 5 \cdot 20}\)

Gdy zamienimy ostatnią liczbę na jeden to otrzymamy liczbę pierwszą gdyż nie ma części wspólnej z resztą cyfr - \(\displaystyle{ 1 \cdot 100}\) jest za duże dla tej pozycji. Natomiast gdy zamienimy ostatnią cyfrę na dwa to zostanie \(\displaystyle{ 1 \cdot 2}\) dołączone do \(\displaystyle{ 2 \cdot 50}\) i otrzymamy \(\displaystyle{ 2 \cdot 51}\). I na tym jest oparty pomysł. W arkusze kalkulacyjnym dla małych liczb to się sprawdza. Dla większych liczb arkusz kalkulacyjny się nie sprawdza i stąd pomysł by przenieść obliczenia do javascriptu. Znalazłem kilka bibliotek które mogą się przydać np.

Kod: Zaznacz cały

http://www-cs-students.stanford.edu/~tjw/jsbn/

. Pytanie zasadnicze jest takie czy przyjęte założenia są poprawne.


Chciałbym zwrócić uwagę na pewien fakt, który przedstawię w metodzie naiwnej. Załóżmy że \(\displaystyle{ f=29331331}\), to:

\(\displaystyle{ kw=5416}\)

\(\displaystyle{ q=-1725}\)

\(\displaystyle{ p=-42}\)

\(\displaystyle{ W=(-42,-1725)}\)

\(\displaystyle{ f(x)=(x+42)^2-1725=x^2+84x+39}\)

\(\displaystyle{ Ax=5374}\)

\(\displaystyle{ y=10748k-2kx}\)

Tak więc mamy takie dwa równania:
\(\displaystyle{ f(x)=x^2+84x+39}\)
\(\displaystyle{ y=10748k-2kx}\)

Przyjmijmy że znane jest k:
jeśli \(\displaystyle{ k=1}\) wtedy \(\displaystyle{ x=69,06}\)
jeśli \(\displaystyle{ k=2}\) wtedy \(\displaystyle{ x=108,95}\) itd.
Wykonaliśmy dwa obliczenia i w tym momencie mamy pewność że liczba \(\displaystyle{ 29331331}\) nie dzieli się przez żadną liczbę z zakresu \(\displaystyle{ 5374 ... 5265}\). Dwa obliczenia i \(\displaystyle{ 109}\) sprawdzonych liczb. Gdybyśmy kontynuowali dalej tak obliczenia to dopiero dla \(\displaystyle{ k=250}\) znajdujemy rozwiązanie: \(\displaystyle{ x=1373}\).
\(\displaystyle{ Ax-x=5374-1373=4001}\) - otrzymaliśmy liczbę pierwszą. Sprawdźmy czy są inne dzielniki: \(\displaystyle{ \frac{29331331}{4001} =7331}\) - ta liczba też jest liczbą pierwszą, dlatego możemy zakończyć dalsze sprawdzanie gdyż mamy jedyne rozwiązanie układu równań.