Witam, czy byłby ktoś w stanie rozwiązać takie zadania:
1)
Spośród wszystkich rozwiązań równania diofantycznego \(\displaystyle{ 346x + 298y = 688}\) wskaż to, w którym x jest najmniejszą dodatnią liczbą całkowitą.
2)
Rozwiązać w liczbach naturalnych układ
\(\displaystyle{ \begin{cases} NWD(x,y) = 37 \\ 5x + 7y = 1147 \end{cases}}\)
3)
Podać liczbę rozwiązań układu
\(\displaystyle{ \begin{cases} NWD(x, y) = 41 \\ 2x + 11y = 3567\end{cases}}\)
w liczbach naturalnych.
równanie diofantyczne, NWD, Algorytm Euklidesa
równanie diofantyczne, NWD, Algorytm Euklidesa
Ostatnio zmieniony 19 lut 2012, o 12:41 przez lukasz1804, łącznie zmieniany 1 raz.
Powód: Warto wszystkie wyrażenia matematyczne umieszczać między tagami[latex], [/latex]
Powód: Warto wszystkie wyrażenia matematyczne umieszczać między tagami
-
Potekk
- Użytkownik
- Posty: 110
- Rejestracja: 2 gru 2007, o 12:34
- Płeć: Mężczyzna
- Lokalizacja: Piastów
- Podziękował: 1 raz
- Pomógł: 35 razy
równanie diofantyczne, NWD, Algorytm Euklidesa
1)
\(\displaystyle{ NWD(346, 298) = 2 \\
173x + 149y = 344 \\
149 y = 344 - 173x}\)
więc mamy, że
\(\displaystyle{ 173x\equiv 344 \pmod{149}}\)
ponieważ
\(\displaystyle{ 173\equiv 24 \pmod{149}}\) i \(\displaystyle{ 344\equiv 46 \pmod{149}}\)
to równanie jest równoważne
\(\displaystyle{ 24x\equiv 46 \pmod{149}}\)
Ponieważ \(\displaystyle{ NWD(149, 24) = 1}\) to z rozszerzonego algorytmu Euklidesa szukamy takich \(\displaystyle{ a, b}\) że
\(\displaystyle{ 24a + 149b = 1}\)
Wychodzi, że \(\displaystyle{ a = -31}\) oraz \(\displaystyle{ b = 5}\)
Najmniejszym naturalnym rozwiązaniem \(\displaystyle{ x}\) jest \(\displaystyle{ x\equiv a*46 \equiv -31 * 46 \equiv 64 \pmod{149}}\)
więc \(\displaystyle{ y = 72}\)
Ponieważ 149 jest liczbą pierwszą to z twierdzenia Lagrange o kongruencjach dostajemy, że równanie
\(\displaystyle{ 173x\equiv 344 \pmod{149}}\) ma co najwyżej 1 rozwiązanie modulo 149 więc nie ma innych wyników
2)
\(\displaystyle{ x = 37a \\
y= 37b \\
5a + 7b = 31}\)
skoro to mają być liczby tylko naturalne to można to ręcznie zrobić dla
\(\displaystyle{ b=0,1,2,3,4}\) (bo dla 5 będzie już za dużo)
\(\displaystyle{ b = 3}\) \(\displaystyle{ a = 2}\)
\(\displaystyle{ x = 3*37}\) i \(\displaystyle{ 2 * 37}\)
3)
\(\displaystyle{ x = 41a \\
y = 41b \\
2a + 11 b= 87}\)
Jedyne możliwe \(\displaystyle{ b}\) to \(\displaystyle{ 0,1,2,3,4,5,6,7}\) i \(\displaystyle{ b}\) musi być nieparzyste więc \(\displaystyle{ |\{1,3,5,7\}| = 4}\)
\(\displaystyle{ NWD(346, 298) = 2 \\
173x + 149y = 344 \\
149 y = 344 - 173x}\)
więc mamy, że
\(\displaystyle{ 173x\equiv 344 \pmod{149}}\)
ponieważ
\(\displaystyle{ 173\equiv 24 \pmod{149}}\) i \(\displaystyle{ 344\equiv 46 \pmod{149}}\)
to równanie jest równoważne
\(\displaystyle{ 24x\equiv 46 \pmod{149}}\)
Ponieważ \(\displaystyle{ NWD(149, 24) = 1}\) to z rozszerzonego algorytmu Euklidesa szukamy takich \(\displaystyle{ a, b}\) że
\(\displaystyle{ 24a + 149b = 1}\)
Wychodzi, że \(\displaystyle{ a = -31}\) oraz \(\displaystyle{ b = 5}\)
Najmniejszym naturalnym rozwiązaniem \(\displaystyle{ x}\) jest \(\displaystyle{ x\equiv a*46 \equiv -31 * 46 \equiv 64 \pmod{149}}\)
więc \(\displaystyle{ y = 72}\)
Ponieważ 149 jest liczbą pierwszą to z twierdzenia Lagrange o kongruencjach dostajemy, że równanie
\(\displaystyle{ 173x\equiv 344 \pmod{149}}\) ma co najwyżej 1 rozwiązanie modulo 149 więc nie ma innych wyników
2)
\(\displaystyle{ x = 37a \\
y= 37b \\
5a + 7b = 31}\)
skoro to mają być liczby tylko naturalne to można to ręcznie zrobić dla
\(\displaystyle{ b=0,1,2,3,4}\) (bo dla 5 będzie już za dużo)
\(\displaystyle{ b = 3}\) \(\displaystyle{ a = 2}\)
\(\displaystyle{ x = 3*37}\) i \(\displaystyle{ 2 * 37}\)
3)
\(\displaystyle{ x = 41a \\
y = 41b \\
2a + 11 b= 87}\)
Jedyne możliwe \(\displaystyle{ b}\) to \(\displaystyle{ 0,1,2,3,4,5,6,7}\) i \(\displaystyle{ b}\) musi być nieparzyste więc \(\displaystyle{ |\{1,3,5,7\}| = 4}\)