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?
równanie z algorytmem Euklidesa
-
- 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
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}}\)
\(\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}}\)