równanie z algorytmem Euklidesa

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
rhomcio
Użytkownik
Użytkownik
Posty: 45
Rejestracja: 29 lis 2007, o 12:25
Płeć: Mężczyzna
Lokalizacja: Gdańsk

równanie z algorytmem Euklidesa

Post autor: rhomcio »

Rozwiązać w liczbach naturalnych następujące równanie stosując algorytm Euklidesa
\(\displaystyle{ 13x+25y=265}\)

Prośba żeby ktoś sprawdził czy w ogóle dobrze myślę, bo to moje pierwsze zadanie w tym temacie:
\(\displaystyle{ 25=1*13+12}\)
\(\displaystyle{ 13=1*12+1}\)

\(\displaystyle{ 1=13-1*12=13-1*(25-1*13)=2*13-1*25}\)
Czyli rozwiązanie szczegółowe: \(\displaystyle{ x_{0} =2, y_{0}=-1}\)

W związku z tym rozwiązanie ogólne wychodzi mi:

\(\displaystyle{ x=2+25t}\)
\(\displaystyle{ y=-1-13t}\)

I teraz jak tu dokończyć to zadanie, aby znaleźć x i y naturalne spełniające początkowe równanie?
maise
Użytkownik
Użytkownik
Posty: 1327
Rejestracja: 25 maja 2008, o 15:36
Płeć: Kobieta
Podziękował: 5 razy
Pomógł: 335 razy

równanie z algorytmem Euklidesa

Post autor: maise »

to jest rozwiązanie równania:
\(\displaystyle{ 13x+25y=1}\)

mając: \(\displaystyle{ 1=2 \cdot 13-1 \cdot 25}\) musisz pomnożyć obie strony przez \(\displaystyle{ 265}\):
\(\displaystyle{ 265=2 \cdot 256 \cdot 13-1 \cdot 265 \cdot 25}\)

i otrzymujesz rozwiązanie:
\(\displaystyle{ x=2 \cdot 256+25t\\
y=-1 \cdot 256-13t\\
t \in Z}\)


skoro obie liczby mają być naturalne, to zakładasz, że:
\(\displaystyle{ x, y>0\\
\Rightarrow
\begin{cases}
2 \cdot 256+25t>0\\
-1 \cdot 256-13t>0
\end{cases}}\)
ODPOWIEDZ