Rozwiązać układy kongruencji

[madziula1784]

\(\displaystyle{ \begin{cases} x=2\left( mod 5\right) \\ x=8\left( mod 11\right) \end{cases}}\)

[Vax]

Albo od razu z Chińskiego twierdzenia o resztach, a jeżeli nie znasz, to można podstawiać, z 1 mamy \(\displaystyle{ x=5a+2}\) wstawiamy do 2: \(\displaystyle{ 5a+2 \equiv 8\pmod{11} \Leftrightarrow 5a\equiv 6\pmod{11}/\cdot 9 \Rightarrow a \equiv 10\pmod{11} \Leftrightarrow a = 11b+10}\) czyli:

\(\displaystyle{ x = 5(11b+10)+2 = 55b+52}\)

Pozdrawiam.

[madziula1784]

Dzięki;)-- 16 maja 2011, o 20:20 --mam pytanie jeszcze skąd się wzieło a=10(mod11)?

[Xitami]

ja zapytałbym raczej skąd się wzięło 9
\(\displaystyle{ 5a=6\ (\mod 11) / \cdot 9\\
5\cdot 9a=6\cdot 9\ (\mod 11)\\
5\cdot 9=1\ (\mod 11)\\
6\cdot 9=10\ (\mod 11)}\)
więc
\(\displaystyle{ a=10\ (\mod 11)}\)

[IloveAlgebra]

ja zapytałbym raczej skąd się wzięło 9

Skąd się wzięło 9?
Rozumiem że potrzebujemy jakiejś ładnej liczby, ale skąd wiadomo jakiej?

[Vax]

Mamy kongruencje \(\displaystyle{ 5a \equiv 6\pmod {11}}\)

Chcemy tą kongruencje pomnożyć przez taką liczbę, żeby przy naszej niewiadomej stała 1, czyli inaczej mówiąc mamy znaleźć takie x, aby \(\displaystyle{ 5\cdot x \equiv 1 \pmod{11}}\) oczywiście \(\displaystyle{ (5,11)=1}\) więc taki x na pewno istnieje, mówiąc inaczej mamy znaleźć element odwrotny do 5 modulo 11, tutaj już możemy się posłużyć rozszerzonym algorytmem Euklidesa, co było wielokrotnie pokazywane na forum, np tutaj:

39038.htm?hilit=rozszerzonego%20algorytmu%20euklidesa

Tak dostajemy \(\displaystyle{ x\equiv 9\pmod{11}}\), a następnie mnożymy przez to naszą kongruencje i dostajemy \(\displaystyle{ a\equiv 10\pmod{11}}\)

Pozdrawiam.

[IloveAlgebra]

Po wyznaczeniu rozszerzonym algorytmem Euklidesa wychodzi, że \(\displaystyle{ 1=11-5*2}\). Czy mógłbyś napisać jak teraz to przekształcić w \(\displaystyle{ x\equiv 9\pmod{11}}\)? Jedyne co mi przychodzi do głowy to zapisać wynik alg Euklidesa jako \(\displaystyle{ x\equiv -10\pmod{11}}\) Jakoś nie mogę pojąć jak się mają równania do kongruencji

[Psiaczek]

Po wyznaczeniu rozszerzonym algorytmem Euklidesa wychodzi, że \(\displaystyle{ 1=11-5*2}\). Czy mógłbyś napisać jak teraz to przekształcić w \(\displaystyle{ x\equiv 9\pmod{11}}\)? Jedyne co mi przychodzi do głowy to zapisać wynik alg Euklidesa jako \(\displaystyle{ x\equiv -10\pmod{11}}\) Jakoś nie mogę pojąć jak się mają równania do kongruencji

Współczynnik przy piątce wyszedł ci minus dwa, jeśli wyjdzie ujemny to dodajesz jedenastkę do tych minus dwóch i uzyskujesz dziewiątkę o której była mowa

[IloveAlgebra]

Jedenastkę do -2? Jakże? \(\displaystyle{ 1=11+5*9}\).

Widzę takie coś, że z \(\displaystyle{ 5x\equiv1(mod 11)}\) jest \(\displaystyle{ 5x+11y=1}\), a z Euklidesa \(\displaystyle{ 5*(-2)+11*1=1}\),ale wniosków z tego nie widzę.