Algorytm rozwiązywania równań diofantycznych.

mksie · Post autor: **mksie** » 29 mar 2009, o 11:19

witam Wszystkich ,
muszę napisać algorytm rozwiązujący każde równanie diofantyczne:
ax+by=c
warunki:
a i b są względnie pierwsze NWD(a,b)=1
c>b>a
chodzi o to, aby rozwiązać to równanie dla dowolnie dużych a,b i c (np.kilkuset-cyfrowych)
chciałem euklidesem, ale czas wykonania jest nieskończony...
jakieś sugestie ?

kuch2r · Post autor: **kuch2r** » 29 mar 2009, o 11:35

poszukaj sobie cos o metodzie Eulera rozwiązywania równań diofantycznych

mksie · Post autor: **mksie** » 29 mar 2009, o 12:06

No nie bardzo sobie to wyobrażam dla liczb kilkuset-cyfrowych.
Poza tym szukałem możliwości ze 2 dni i nie znalazłem.
Może to jakaś pułapka i nie da sie rozwiązać ?
Ale to też musiałbym wykazać...

p_pokora · Post autor: **p_pokora** » 29 mar 2009, o 12:54

Ja osobiście proponuje stworzenie algorytmu, który korzystałby z tzw. twierdzenia o redukcji. Twierdzenie brzmi następująco. Jeżeli równanie U posiada rozwiązanie w liczbach całkowitych, to równanie U zredukowane względem pierścienia Zp posiada rozwiązanie w Zp. Mniej więcej o to chodzi, że mając dowolne równanie postaci ax+by=c możesz je zredukować względem Zp. Działania są również w Zp. To twierdzenie jak widzisz jest tylko w jedną stronę. Twierdzenie odwrotne nie jest prawdziwe. Jest to związane z 10 problemem Hilberta. Poczytaj sobie. Ponadto warto zwrócić uwagę na twierdzenie Matijasiewicza, chyba jest w Mostowskim. Twierdzenie o redukcji i ta obudowa pozwoli Ci stworzyć program, który będzie potrafił stwierdzić przynajmniej które równania nie są diofantyczne. Reszta jakoś pójdzie;]. Warto również skorzystać z prostego warunku, że jeśli c dzieli b oraz c dzieli a to c dzieli x*a+y*b. To też może będzie pomocne. Twierdzenie o redukcji pojawia się u Białynickiego -Biruli w Książce Algebra tom 40 BM.
Pozdrawiam