Rozwiązać kongruencje

[ebasse]

Witam, mam problem w rozwiązaniu układu kongruencji.
Proszę o pomoc, ewentualne wskazówki. Cokolwiek co naprowadzi i pomoże to zrozumieć. Z góry dziekuję

\(\displaystyle{ 5x\equiv3\pmod{11} \\
6x\equiv4\pmod{34}}\)

[soulman64]

\(\displaystyle{ x \in (0,11\rangle}\), bo jest modulo \(\displaystyle{ 11}\) czyli zawiera sie do \(\displaystyle{ 11}\) włacznie
\(\displaystyle{ 5 \cdot 1=5}\) modulo \(\displaystyle{ 11}\) przystaje do \(\displaystyle{ 3}\)
\(\displaystyle{ 5 \cdot 2=10}\) reszta \(\displaystyle{ 1}\)
\(\displaystyle{ 5 \cdot 3=15\ \ \ \frac{15}{11}}\) daje reszte \(\displaystyle{ 3}\)
\(\displaystyle{ 5 \cdot 4=20}\) reszta z dzielenia przez \(\displaystyle{ 11\text{ to } 8}\)

\(\displaystyle{ 5 \cdot 5=25 \text{ reszta to } 3 \\
5 \cdot 6=30 \text{ reszta } 8 \\
5 \cdot 7=35 \text{ reszta } 2 \\
5 \cdot 8=40 \text{ reszta } 7 \\
5 \cdot 9=45 \text{ reszta } 1 \\
5 \cdot 10=50 \text{ reszta } 6 \\
5 \cdot 11=55 \text{ reszta } 0}\)

czyli \(\displaystyle{ 5x}\)przystaje do \(\displaystyle{ 3\pmod{11}}\) tylko w trzech przypadkach gdy \(\displaystyle{ x=3 \vee x=5 \vee x=1}\)

teraz wystarczy sprawdzić z \(\displaystyle{ \pmod{34}}\) tez cyfry

\(\displaystyle{ 6 \cdot 3=24 \pmod {34} \text{ to będzie } 10\\
6 \cdot 1=6 \pmod {34} \text{ to będzie } 28\\
6 \cdot 5=30 \text{ czyli przystaje do }4}\)

Odp. \(\displaystyle{ x=5}\)

[Qń]

Oczywiście powyższe rozwiązanie jest błędne - można robić w ten sposób, czyli na piechotę, ale pod warunkiem, że nie robi się tylu błędów merytorycznych i rachunkowych.

Na piechotę - sprawdzamy ręcznie, że rozwiązaniem pierwszej kongruencji w zbiorze \(\displaystyle{ \{0,1,\ldots ,10\}}\) jest tylko \(\displaystyle{ 5}\), więc wiemy, że \(\displaystyle{ x=11k+5}\). Wstawiając to drugiej kongruencji dostajemy kolejno:
\(\displaystyle{ 6(11k+5)\equiv4\pmod{34}\\
66k\equiv -26\pmod{34}\\
33k\equiv -13\pmod{17}\\
-k\equiv -13\pmod{17}\\
k\equiv 13\pmod{17}}\)
czyli \(\displaystyle{ k=17l+13}\), czyli:
\(\displaystyle{ x=11(17l+13)+5=187l+148}\)
więc jedynym rozwiązaniem w przedziale \(\displaystyle{ [0, 11cdot 17)}\) jest \(\displaystyle{ x=148}\)

Nie na piechotę można tak - zaczynamy od podzielenia drugiej kongruencji stronami przez dwa:
\(\displaystyle{ \begin{cases}5x\equiv3\pmod{11} \\ 3x\equiv2\pmod{17}\end{cases}}\)
Znajdujemy teraz odwrotność piątki modulo \(\displaystyle{ 11}\) i odwrotność trójki modulo \(\displaystyle{ 17}\), tzn. takie liczby \(\displaystyle{ a,b}\), że \(\displaystyle{ 5a\equiv 1\pmod{11}, 3b\equiv 1\pmod{17}}\) (można to zrobić przy użyciu rozszerzonego algorytmu Euklidesa lub "zgadując"). Są to \(\displaystyle{ a=9,b=6}\). Mnożymy więć pierwszą kongruencję przez \(\displaystyle{ 9}\), a drugą przez \(\displaystyle{ 6}\):
\(\displaystyle{ \begin{cases}x\equiv5\pmod{11} \\ x\equiv12\pmod{17}\end{cases}}\)
Teraz znajdujemy rozwiązania kongruencji:
\(\displaystyle{ \begin{cases}x_1\equiv1\pmod{11} \\ x_1\equiv0\pmod{17}\end{cases}}\)
\(\displaystyle{ \begin{cases}x_2\equiv0\pmod{11} \\ x_2\equiv1\pmod{17}\end{cases}}\)
W pierwszym przypadku \(\displaystyle{ x_1=17k}\), czyli \(\displaystyle{ 17k\equiv1\pmod{11}}\), czyli \(\displaystyle{ 6k\equiv1\pmod{11}}\), czyli \(\displaystyle{ k=2}\), czyli \(\displaystyle{ x_1=34}\)
W drugim wypadku \(\displaystyle{ x_2=11k}\), czyli \(\displaystyle{ 11k\equiv1\pmod{17}}\), czyli \(\displaystyle{ k=14}\), czyli \(\displaystyle{ x_2=154}\)
Na końcu obliczamy
\(\displaystyle{ x=5x_1+12x_2\mod (11\cdot 17)= 148}\)

Q.

[ebasse]

Na piechotę - sprawdzamy ręcznie, że rozwiązaniem pierwszej kongruencji w zbiorze \(\displaystyle{ \{0,1,\ldots ,10\}}\) jest tylko \(\displaystyle{ 5}\), więc wiemy, że \(\displaystyle{ x=11k+5}\). Wstawiając to drugiej kongruencji dostajemy kolejno:
\(\displaystyle{ 6(11k+5)\equiv4\pmod{34}\\
66k\equiv -26\pmod{34}\\
33k\equiv -13\pmod{17}\\
-k\equiv -13\pmod{17}\\
k\equiv 13\pmod{17}}\)
czyli \(\displaystyle{ k=17l+13}\), czyli:
\(\displaystyle{ x=11(17l+13)+5=187l+148}\)
więc jedynym rozwiązaniem w przedziale \(\displaystyle{ [0, 11cdot 17)}\) jest \(\displaystyle{ x=148}\)

Czy mógłbyś to tak po kolei wytłumaczyć, skąd biorą się poszczególne linijki?

Np.
\(\displaystyle{ x=11k+5 \\
k\equiv 13\pmod{17} \\
-k\equiv -13\pmod{17}\\}\)