szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 18 lut 2009, o 16:33 
Użytkownik

Posty: 1
Witam,

Pytania odnośnie mojego problemu znajdują się na końcu postu, a wcześniej treść zadania:

Rozwiązać układ kongruencji:

\begin{cases} 4x\equiv3 \ (mod \ 5)\\3x\equiv2 \ (mod \ 10)  
\end{cases}


Układ nie ma rozwiązania, a doszedłem do tego w taki sposób:

ax\equiv b \ (mod \ m)

\begin{cases} 4x\equiv3 \ (mod \ 5) \ /*2 \\ 3x\equiv2 \ (mod \ 10)  
\end{cases}

Odejmuję jedno równanie od drugiego:

\begin{cases} 8x\equiv6 \ (mod \ 10)\\3x\equiv2 \ (mod \ 10) \ /-  
\end{cases}

Dzięki czemu otrzymuję jedno równanie:

5x\equiv4 \ (mod \ 10)


Jak widać NWD(5,10)\nmid4, co oznacza iż kongruencja nie ma rozwiązania.


(*) Niestety na egzaminie nieco bardziej skompilowałem sprawę. Do momentu wyliczenia jednego równania 5x\equiv4 \ (mod \ 10) dr prowadzący zajęcia nie miał zastrzeżeń. Dalej, zamiast po prostu napisać NWD(5,10)\nmid4, wykonałem takie operacje:

Skorzystałem z rozszerzonego algorytmu Euklidesa:

\begin{tabular}{ccccccc}
a & a\prime & q & s & s\prime & t & t\prime \\
10 & 5 & 2 & 1 & 0 & 0 & 1 \\
5 & 0 & \cdot & 0 & \cdot & 1 & \cdot \\
 &  &  & z\uparrow &  &  &  \\
\end{tabular}

Z czego dla sprawdzenia wychodzi:

5=0*10+1*5=5

Następnie podstawiam dane pod wzór (1): x\equiv (b*z) \ (mod \ m), z którego otrzymuję:

x\equiv 0 \ (mod \ 10)

Można zauważyć, że końcowe równanie nie jest równoważne z równaniami początkowymi, dlatego kongruencja nie ma rozwiązań.


Moje pytania:
1. Czy rozszerzony algorytm Euklidesa można stosować w przypadku, gdy liczby a oraz b nie są względnie pierwsze?
2. Gdzie mogę znaleźć dowodzenie prawdziwości wzoru (1)? Znalazłem taki wzór w pewnym schemacie rozwiązywania układu kongruencji. Sęk w tym, że w owych rozwiązaniach kongruencje zawsze miały rozwiązania. Stąd ostatnie pytanie:
3. Czy moje rozwiązanie od momentu (*) jest w ogóle prawidłowe, jeśli korzystałem z algorytmu Euklidesa i wzoru (1) dla liczb nie będących względnie pierwszymi? Czy zawsze taki sposób będzie poprawny? Jeśli tak, to jak mogę udowodnić ten tok rozumowania? Wykładowca nie widzi żadnego związku z zadaniem od momentu (*).
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 sprawdzenie rozwiązania-podzielnosc  Lame  3
 Układ kongruencji - zadanie 16  drago77  2
 Podzielnoś liczby czterocyfrowej - sprawdzenie rozwiązania  Aldo  1
 Dwa alternatywne rozwiązania, czy oba prawidłowe?  matinf  2
 układ kongruencji - zadanie 8  sylwuch  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl