Równanie - "szybkie" odpowiadanie czy istnieje rozwiązanie

[wiedzmac]

Cześć,
Mam następujący problem, nieco informatyczny. Dane jest równanie \(\displaystyle{ ax + by = c}\), gdzie \(\displaystyle{ a,b,c,x,y \in \mathbb{N}}\).
Znamy \(\displaystyle{ a, b}\) i \(\displaystyle{ c}\) i dodatkowo wiemy, że \(\displaystyle{ c \leq 10 000}\), co pozwala nam ograniczyć względem \(\displaystyle{ c}\) inne liczby.
Pytamy się teraz czy takie równanie ma rozwiązanie \(\displaystyle{ (x,y)}\). Możemy przeglądać wszystkie możliwe wartości \(\displaystyle{ x}\) od \(\displaystyle{ 0}\) do \(\displaystyle{ 10 000}\) i na podstawie tego obliczać \(\displaystyle{ y}\) i sprawdzać czy jest naturalne i mieści się w naszym zakresie, ale jest to dość czasochłonne. Zastanawiam się zatem czy istnieje jakiś szybszy sposób, który pozwoli nam sprawdzić czy tak podane równanie ma rozwiązanie. Dodam, że nie interesuje mnie samo rozwiązanie, ale czy takowe istnieje.

Pozdrawiam,
Bartosz Bednarczyk

[Sylwek]

To wszystko podpada pod algorytm Euklidesa. Rozwiązanie całkowite istnieje dokładnie wtedy, gdy \(\displaystyle{ NWD(a,b)|c}\). Następnie za pomocą a.E. wyznaczasz ogólną postać rozwiązania w postaci parametrycznej, jak np. tutaj 288045.htm (poszukaj). Na koniec sprawdzasz np. czy dla najmniejszego dodatniego \(\displaystyle{ x}\) (z ciągu rozwiązań) odpowiadające mu \(\displaystyle{ y}\) też jest dodatnie (to wystarczy, bo gdy powiększysz \(\displaystyle{ x}\), to automatycznie pomniejszysz \(\displaystyle{ y}\), i vice versa). Potrzebnych operacji nie będzie wiele, coś rzędu \(\displaystyle{ \log_{\varphi}(c)}\).