Szukanie całkowitego rozwiązania r-nia liniowego

[joseph17]

Z góry przepraszam jeśli trafiłem w zły dział albo źle określiłem temat, ale dopiero tu zaczynam .

Mam taki dość, zdaje się, prosty problem z takim zadankiem. Otóż w jaki sposób sprawdzić czy istnieje para liczb całkowitych \(\displaystyle{ (x,y)}\) spełniająca równanie:

\(\displaystyle{ ax+by=c}\)

\(\displaystyle{ a,b,c}\) są dowolnymi liczbami całkowitymi różnymi od zera

Dodam, że chodzi mi tylko o to czy taka para istnieje czy nie, bez znajdowania konkretnych liczb. Jest mi to potrzebne do algorytmu, więc metoda prób i błędów raczej odpada.

Z góry dziękuję za pomoc.
Pozdrawiam.

[kuch2r]

Waruenk, który musi być spełniony
\(\displaystyle{ NWD(a,b)|c}\)

[rtshadow]

Czy, podobnie jak wyżej, dla równań w postaci:

\(\displaystyle{ a_{1}x+a_{2}y+...+a_{n}z=c}\)

rozwiązaniami są liczby całkowite dla współczynników spełniających warunek:

\(\displaystyle{ NWD(a_{1},a_{2},...,a_{n})|c}\)

Z góry dzięki za odpowiedź

[max]

Raczej zinterpretowałbym to tak:
Dla dowolnie ustalonych parametrów \(\displaystyle{ a_{1},\ldots, a_{n}, c\neq 0,}\) całkowitych takich, że co najmniej jedno \(\displaystyle{ a_{i}}\) jest niezerowe, równanie:
\(\displaystyle{ a_{1}x_{1} + \ldots + a_{n}x_{n} = c}\)
posiada rozwiązanie \(\displaystyle{ (x_{1},\ldots, x_{n}),}\) gdzie \(\displaystyle{ x_{i}}\) są całkowite, wtedy i tylko wtedy gdy \(\displaystyle{ \gcd(a_{1},\ldots, a_{n})| c}\)
Jest to prawda.

[macjan]

Tak tylko dodam, że do znajdowania rozwiązań używa się rozszerzonego algorytmu Euklidesa.