Kalkulator liniowych równań diofantycznych

Q: Jak rozwiązać liniowe równanie diofantyczne ręcznie?

Najpierw algorytmem Euklidesa oblicz g = gcd(a, b). Jeśli g nie dzieli c, rozwiązań całkowitych nie ma. W przeciwnym razie wykonaj rozszerzony algorytm Euklidesa, aby znaleźć współczynniki Bézouta spełniające g = sa + tb, pomnóż je przez c/g, otrzymując x_0 = s · c/g i y_0 = t · c/g, a następnie zapisz wszystkie rozwiązania jako x = x_0 + (b/g)t, y = y_0 - (a/g)t.

Q: Czy można używać ujemnych współczynników albo ujemnej prawej strony?

Tak, wszystkie trzy dane mogą być ujemne lub równe zeru — odrzucane są tylko ułamki i liczby dziesiętne. NWD zawsze liczy się z wartości bezwzględnych, więc jest dodatni. Wzory na rozwiązanie ogólne działają bez zmian również przy ujemnych a, b lub c; zmieniają się jedynie znaki kroków b/g i a/g we wzorach z parametrem.

Q: Jak najłatwiej stwierdzić, że rozwiązanie nie istnieje?

Sprawdź podzielność przez NWD: rozwiązania istnieją wtedy i tylko wtedy, gdy gcd(a,b) dzieli c. Szybki test parzystości wykrywa wiele szkolnych przypadków — jeśli a i b są parzyste, lewa strona jest zawsze parzysta, więc nieparzyste c czyni równanie nierozwiązywalnym. Podobnie 6x + 10y jest zawsze parzyste i zawsze przystaje wyłącznie do wielokrotności gcd(6,10)=2.

Q: Jak znaleźć tylko rozwiązania nieujemne lub dodatnie?

Rodzina parametryczna x = x_0 + (b/g)t, y = y_0 - (a/g)t daje liniowy warunek na t. Rozwiąż względem t nierówności x ≥ 0 i y ≥ 0, weź część wspólną (będzie to skończony przedział liczb całkowitych) i wypisz kolejne wartości. Jeśli przedział t wychodzi pusty, to nie istnieje rozwiązanie z obiema zmiennymi nieujemnymi.

Q: Dlaczego kalkulator podaje inne rozwiązanie szczególne niż mój podręcznik?

Rozwiązania szczególne nigdy nie są jednoznaczne — jeśli (x_0, y_0) działa, to (x_0 + b/g, y_0 - a/g) też. Obie odpowiedzi są poprawne, ponieważ przez parametr t generują identyczny, pełny zbiór rozwiązań. Ten kalkulator przesuwa x_0 do zwartego przedziału 0 ≤ x_0 < |b/g|, czego podręczniki mogą nie robić. Zawsze sprawdź wynik, podstawiając do ax + by.

Q: Co się dzieje, gdy a lub b równa się zero?

Równanie sprowadza się do jednej zmiennej. Jeśli b = 0, musi zachodzić a mid c; wtedy x = c/a jest ustalone, a y może być dowolną liczbą całkowitą — symetrycznie dla a = 0. Jeśli oba współczynniki są zerowe, równanie jest albo zawsze prawdziwe (c = 0, pasuje każda para), albo nigdy. Kalkulator obsługuje wprost wszystkie te przypadki szczególne.

Q: Czym to się różni od rozwiązywania zwykłego równania liniowego?

W liczbach rzeczywistych ax + by = c z niezerowym współczynnikiem zawsze ma rozwiązania — aż całą prostą. Wersja diofantyczna wymaga wyłącznie par liczb całkowitych, przez co równanie może być nierozwiązywalne (gdy gcd(a,b) nmid c) albo mieć zamiast continuum dyskretny, równomiernie rozłożony zbiór rozwiązań na tej prostej. Krok między kolejnymi rozwiązaniami to dokładnie (b/g, -a/g).

Zaktualizowano: 14 października 2026

Rozwiązuje liniowe równanie diofantyczne ax + by = c w liczbach całkowitych. Wpisz współczynniki a, b i c, aby sprawdzić, czy rozwiązania istnieją, otrzymać jedno rozwiązanie szczególne oraz pełną rodzinę x = x₀ + (b/g)t, y = y₀ − (a/g)t.

Rozwiąż ax + by = c w liczbach całkowitych

Wzór na liniowe równanie diofantyczne

Wzór

\[ ax + by = c, \qquad a, b, c \in \mathbb{Z} \] \[ g = \gcd(a, b) \] \[ \text{Rozwiązania całkowite istnieją} \iff g \mid c \] \[ x = x_0 + \frac{b}{g}\,t, \qquad y = y_0 - \frac{a}{g}\,t, \qquad t \in \mathbb{Z} \]

gdzie:

\(a\), \(b\) — całkowite współczynniki przy \(x\) i \(y\)
\(c\) — całkowita prawa strona równania
\(g = \gcd(a, b)\) — największy wspólny dzielnik współczynników
\((x_0, y_0)\) — jedno rozwiązanie szczególne, wyznaczone z tożsamości Bézouta \(g = s\,a + t\,b\) przez pomnożenie przez \(c/g\)
\(t\) — dowolny parametr całkowity, który generuje wszystkie rozwiązania

Równanie ma rozwiązania całkowite dokładnie wtedy, gdy \(\gcd(a,b)\) dzieli \(c\). Jeśli tak, jest ich nieskończenie wiele: wychodząc od jednego rozwiązania \((x_0, y_0)\), każde inne otrzymamy, dodając \(b/g\) do \(x\) i odejmując \(a/g\) od \(y\) tę samą liczbę razy \(t\).

Liniowe równanie diofantyczne – przykład obliczenia

Przykład: rozwiąż \(12x + 18y = 30\) w liczbach całkowitych (wartości domyślne kalkulatora).

\[ \gcd(12, 18): \quad 18 = 1 \cdot 12 + 6, \quad 12 = 2 \cdot 6 + 0 \implies \gcd(12, 18) = 6 \]

\[ 6 \mid 30 \implies \text{rozwiązania istnieją} \]

\[ \text{Bézout: } 6 = (-1) \cdot 12 + 1 \cdot 18, \qquad \frac{c}{g} = \frac{30}{6} = 5 \]

\[ x_0 = -1 \cdot 5 = -5, \qquad y_0 = 1 \cdot 5 = 5 \]

\[ 12 \cdot (-5) + 18 \cdot 5 = -60 + 90 = 30 \;\checkmark \]

Przesuwając \(x_0\) do przedziału \(0 \le x < |b/g| = 3\), otrzymujemy równoważne rozwiązanie szczególne \((1, 1)\), ponieważ \(12 \cdot 1 + 18 \cdot 1 = 30\).

Wynik: wszystkimi rozwiązaniami całkowitymi są \(x = 1 + 3t\), \(y = 1 - 2t\) dla dowolnej liczby całkowitej \(t\); na przykład \((1, 1)\), \((4, -1)\), \((-2, 3)\).

Jak korzystać z kalkulatora

Wpisz całkowity współczynnik przy \(x\) w pole Współczynnik przy x (a).
Wpisz całkowity współczynnik przy \(y\) w pole Współczynnik przy y (b).
Wpisz prawą stronę w pole Prawa strona (c).
Odczytaj bloki wyników: Czy istnieją rozwiązania całkowite? mówi, czy \(\gcd(a,b)\) dzieli \(c\); Jedno rozwiązanie (x₀, y₀) podaje sprawdzone rozwiązanie szczególne; Rozwiązanie ogólne w liczbach całkowitych podaje pełną rodzinę z parametrem \(t\); Kroki rozwiązania pokazują algorytm Euklidesa, współczynniki Bézouta i tok rozumowania.

Wszystkie trzy dane muszą być liczbami całkowitymi (dodatnimi, ujemnymi lub zerem). Jeśli wpiszesz wartość niecałkowitą, kalkulator poprosi o liczbę całkowitą, ponieważ równania diofantyczne z definicji rozwiązuje się wyłącznie w liczbach całkowitych.

Czym jest liniowe równanie diofantyczne?

Równanie diofantyczne to równanie, którego rozwiązania muszą być liczbami całkowitymi. Liniowe równanie diofantyczne \(ax + by = c\) to najprostszy przypadek: szukamy wszystkich par liczb całkowitych \((x, y)\), które spełniają je dokładnie — bez ułamków i liczb dziesiętnych. Takie równania pojawiają się naturalnie wszędzie tam, gdzie wielkości są niepodzielne — monety o ustalonych nominałach, kartony z towarem, ludzie czy kafelki.

Kluczowy jest warunek rozwiązywalności: \(ax + by\) jest zawsze wielokrotnością \(\gcd(a, b)\), więc także \(c\) musi być wielokrotnością \(\gcd(a, b)\). Na przykład \(6x + 10y\) jest zawsze parzyste, więc równanie \(6x + 10y = 7\) nie ma rozwiązań całkowitych, choćby nie wiem jak szukać. Gdy warunek jest spełniony, tożsamość Bézouta gwarantuje co najmniej jedno rozwiązanie, które rozszerzony algorytm Euklidesa znajduje szybko.

Interpretacja wyniku: jeśli rozwiązania istnieją, jest ich nieskończenie wiele i tworzą ciąg arytmetyczny. Rozwiązanie ogólne \(x = x_0 + (b/g)t\), \(y = y_0 - (a/g)t\) wylicza je wszystkie — każdy krok parametru \(t\) zwiększa \(x\) o \(b/g\) i zmniejsza \(y\) o \(a/g\), przy czym \(ax + by\) pozostaje niezmienne. Jeśli potrzebujesz rozwiązań z konkretnego przedziału (np. nieujemnych), podstaw kilka wartości \(t\) i zostaw te, które pasują.

Założenia, ograniczenia i wskazówki

Wyłącznie liczby całkowite. Współczynniki muszą być liczbami całkowitymi; równania nie rozwiążemy na liczbach wymiernych ani rzeczywistych. W liczbach rzeczywistych \(ax + by = c\) zawsze ma rozwiązania, gdy \(a\) lub \(b\) jest niezerowe — to właśnie ograniczenie do liczb całkowitych czyni problem ciekawym.
Ograniczenia wielkości. Obliczenia wykonywane są standardową arytmetyką, więc trzymaj współczynniki w bezpiecznym zakresie liczb całkowitych (mniej więcej do 15 cyfr), aby uniknąć problemów z precyzją.
Przypadki szczególne są obsługiwane. Jeśli \(a = b = 0\), równanie jest albo zawsze prawdziwe (\(c = 0\), pasuje każda para), albo nigdy. Jeśli dokładnie jeden współczynnik jest zerowy, równanie ma jedną zmienną i kalkulator rozwiązuje je wprost.
Każde rozwiązanie szczególne jest dobre. Para \((x_0, y_0)\) nie jest jednoznaczna — kalkulator przesuwa ją do zwartej postaci z \(0 \le x_0 < |b/g|\), ale każdy wybór generuje przez parametr \(t\) ten sam pełny zbiór rozwiązań.
Sprawdzanie wyniku. Zawsze weryfikuj przez podstawienie: oblicz \(a x_0 + b y_0\) i upewnij się, że wyszło \(c\). Kalkulator wykonuje ten test za Ciebie w wyniku.

Jeśli w Twoim zadaniu występują od razu dwa równania liniowe, układ typu \(ax + by = c\), \(dx + ey = f\) rozwiązuje się metodą eliminacji, a nie przez podzielność przez NWD. Rozumowanie diofantyczne stoi też u podstaw tematów takich jak proporcjonalność prosta, gdzie dwie wielkości całkowite rosną w stałej proporcji, i jest klasycznym narzędziem w zadaniach konkursowych oraz teorii liczb.

Najczęściej zadawane pytania

Jak rozwiązać liniowe równanie diofantyczne ręcznie?

Najpierw algorytmem Euklidesa oblicz \(g = \gcd(a, b)\). Jeśli \(g\) nie dzieli \(c\), rozwiązań całkowitych nie ma. W przeciwnym razie wykonaj rozszerzony algorytm Euklidesa, aby znaleźć współczynniki Bézouta spełniające \(g = sa + tb\), pomnóż je przez \(c/g\), otrzymując \(x_0 = s \cdot c/g\) i \(y_0 = t \cdot c/g\), a następnie zapisz wszystkie rozwiązania jako \(x = x_0 + (b/g)t\), \(y = y_0 - (a/g)t\).

Czy można używać ujemnych współczynników albo ujemnej prawej strony?

Tak, wszystkie trzy dane mogą być ujemne lub równe zeru — odrzucane są tylko ułamki i liczby dziesiętne. NWD zawsze liczy się z wartości bezwzględnych, więc jest dodatni. Wzory na rozwiązanie ogólne działają bez zmian również przy ujemnych \(a\), \(b\) lub \(c\); zmieniają się jedynie znaki kroków \(b/g\) i \(a/g\) we wzorach z parametrem.

Jak najłatwiej stwierdzić, że rozwiązanie nie istnieje?

Sprawdź podzielność przez NWD: rozwiązania istnieją wtedy i tylko wtedy, gdy \(\gcd(a,b)\) dzieli \(c\). Szybki test parzystości wykrywa wiele szkolnych przypadków — jeśli \(a\) i \(b\) są parzyste, lewa strona jest zawsze parzysta, więc nieparzyste \(c\) czyni równanie nierozwiązywalnym. Podobnie \(6x + 10y\) jest zawsze parzyste i zawsze przystaje wyłącznie do wielokrotności \(\gcd(6,10)=2\).

Jak znaleźć tylko rozwiązania nieujemne lub dodatnie?

Rodzina parametryczna \(x = x_0 + (b/g)t\), \(y = y_0 - (a/g)t\) daje liniowy warunek na \(t\). Rozwiąż względem \(t\) nierówności \(x \ge 0\) i \(y \ge 0\), weź część wspólną (będzie to skończony przedział liczb całkowitych) i wypisz kolejne wartości. Jeśli przedział \(t\) wychodzi pusty, to nie istnieje rozwiązanie z obiema zmiennymi nieujemnymi.

Dlaczego kalkulator podaje inne rozwiązanie szczególne niż mój podręcznik?

Rozwiązania szczególne nigdy nie są jednoznaczne — jeśli \((x_0, y_0)\) działa, to \((x_0 + b/g,\; y_0 - a/g)\) też. Obie odpowiedzi są poprawne, ponieważ przez parametr \(t\) generują identyczny, pełny zbiór rozwiązań. Ten kalkulator przesuwa \(x_0\) do zwartego przedziału \(0 \le x_0 < |b/g|\), czego podręczniki mogą nie robić. Zawsze sprawdź wynik, podstawiając do \(ax + by\).

Co się dzieje, gdy a lub b równa się zero?

Równanie sprowadza się do jednej zmiennej. Jeśli \(b = 0\), musi zachodzić \(a \mid c\); wtedy \(x = c/a\) jest ustalone, a \(y\) może być dowolną liczbą całkowitą — symetrycznie dla \(a = 0\). Jeśli oba współczynniki są zerowe, równanie jest albo zawsze prawdziwe (\(c = 0\), pasuje każda para), albo nigdy. Kalkulator obsługuje wprost wszystkie te przypadki szczególne.

Czym to się różni od rozwiązywania zwykłego równania liniowego?

W liczbach rzeczywistych \(ax + by = c\) z niezerowym współczynnikiem zawsze ma rozwiązania — aż całą prostą. Wersja diofantyczna wymaga wyłącznie par liczb całkowitych, przez co równanie może być nierozwiązywalne (gdy \(\gcd(a,b) \nmid c\)) albo mieć zamiast continuum dyskretny, równomiernie rozłożony zbiór rozwiązań na tej prostej. Krok między kolejnymi rozwiązaniami to dokładnie \((b/g, -a/g)\).