Układ równań liniowych diofantycznych

[MrMorgan]

\(\displaystyle{ \begin{cases}3x+5y+7z=4 \\ 6x+15y+20z=7\end{cases}}\)

Jak się rozwiązuje tego typu układy w liczbach całkowitych? Ogarniam mniej więcej zasadę rozwiązywania takich równań, ale jak się postępuje z układami?

[Premislav]

Nie znam ogólnej metody. Można coś pododawać/poodejmować stronami tak, aby sprowadzić problem (przynajmniej częściowo) do liniowego równania diofantycznego z dwoma niewiadomymi, a to się pałuje rozszerzonym algorytmem Euklidesa. Przykładowo tutaj odejmując stronami od drugiego równania pierwsze równanie pomnożone przez \(\displaystyle{ 2}\), dostajemy
\(\displaystyle{ 5y+6z=-1}\), no i jak ktoś zna rozszerzony algorytm Euklidesa, to nietrudno stąd wywnioskować, że \(\displaystyle{ y=1+6t, \ z=-1-5t, \ t \in \ZZ}\), a potem można to podstawić do pierwszego równania i dalej kombinować.

[MrMorgan]

Czyli wszystkie rozwiązania tego układu równań są postaci \(\displaystyle{ x=-5u+12,y=37-18u,z=15u-31}\) gdzie \(\displaystyle{ u\in \mathbb{Z}}\)?

[Premislav]

Wygląda OK.

[MrMorgan]

OK, dzięki, a nie da się postąpić w tym stylu z dowolnym układem równań postaci \(\displaystyle{ \sum_{k=1}^{n}a_kx_k=b}\)? W sensie rozwiązujemy równanie diofantyczne ze względu na jakąś zmienną i podstawiamy parametryczną wartość tej zmiennej do pozostałych równań, potem wyliczamy z drugiego równania inną zmienną i jej wartość parametryczną podstawiamy do pozostałych równań itd. dopóki się da? To nie działa?

[Premislav]

Na oko może to działać, ale nie znam dowodu, że zawsze działa. W skrócie:

Kod: Zaznacz cały

https://www.youtube.com/watch?v=aA2lFSI2ZUk