Całkowite rozwiązanie równania. Mati - Polibuda: Dane jest równanie diofantyczne postaci: 504x + 462y = 42 Wyznacz rozwiązania całkowite równania. Proszę o rozpisanie krok po kroku jak uzyskać rozwiązanie (na pierwszy rzut oka widać że x=1, y=−1), z góry dziękuję

ICSP: 504x + 462y = 42 ⇔ 504x + 462y = 42 (mod 462) ⇔ 504x = 42 (mod 462) ⇔ 42x = 42 (mod 462) ⇔ x = 1 (mod 462) ⇔ x = 1 + 462k ; k ∊ C wstawiająć do wyjściowego równania 504 + 504*462k + 462y = 42 462y = −462 − 504 * 462k y = −1 − 504k ; k ∊C

PW: 504=12•42, 462=11•42 Ja bym sobie życie ułatwił 12x+11y=1.

Mati - Polibuda: w takim razie jeśli mam coś takiego: 504x + 462y = 13 nie ma rozwiązań całkowitych?

ICSP: równanie ax + by = c ma rozwiązanie wtedy gdy NWD(a,b) | c

Mati - Polibuda: Zatem 42 nie dzieli 13 Dziękuje bardzo

PW: 42(12x+11y)=13 Musiałaby istnieć dodatnia liczba całkowita k=12x+11y, taka że 42•k=13, co jest niemożliwe z oczywistych powodów (lewa strona większa od prawej).

Mati - Polibuda: @ICSP i @PW Dziękuję za info i pozdrawiam

teofrast: Metoda zaproponowana przez ICSP jest najbardziej elegancka. Niemniej, w praktycznych zastosowaniach można, znalazłszy jedno rozwiązanie szczególne ( x_o, y_o) wypisać od razu wszystkie rozwiązania równania ax + by = c, POD WARUNKIEM, że a i b nie mają dzielnika wspólnego : x = x_o ± bt y = y_o ± (−at) gdzie możemy wziąć jednocześnie w obydwu wierszach albo znaki dolne, albo górne. Własność tę łatwo udowodnić; czyni się to zazwyczaj w trakcie wykładu... Rozwiazanie szczególne nieraz trudniej znaleźć (np. przy bardzo dużych współczynnikach...); wtedy można np. skorzystać z teorii ułamków łańcuchowych . Aż dziwne, ale wszystko to było wykładane jeszcze w 1918 roku w kursie szkoły sredniej ( zob. np. M. Feldblum− « Algebra Elementarna», Łódź 1918...)

PW: Śmiem zaprotestować co do tej elegancji. Po pierwsze − czy pochwalimy ucznia, który zobaczywszy równanie 42x²−210x+84=0 weźmie do ręki młotek pod tytułem Δ i zacznie rąbać? Nie, raczej powiemy "mogłeś ułatwić sobie życie i najpierw podzielić przez 42". Po drugie rozwiązanie ICSP jest błędne. Kto nie wierzy, niech sprawdzi np. x=23, y=−25. Skoro było to łatwe do znalezienia rozwiązanie szczególne, to najprościej było zastosować sposób elementarny.