Układ kongruencji

[xmukix]

jak znaleźć najmniejsze nieujemne rozwiązanie układu kongruencji?
\(\begin{cases}x=-7(mod14)\\ x=39(mod17) \end{cases}\)

[irena]

\(\{x\equiv-7\equiv7\ (mod14)\\x\equiv39\equiv5\ (mod17)\)

\(\{x=14n+7\\x=17m+5\)

\(\{17x=238n+119\\14x=238m+70\)

\(3x=238(n-m)+49\\3x\equiv49\equiv-189\ (mod238)\\x\equiv-63\ (mod238)\equiv175\ (mod238)\)

\(x=175+238n;\ \ n\in\ C\)

175

[KamilWit]

nie wiem czy Ci pomoże , ale :
\(\begin{cases}x=7(mod14)\\ x=5(mod17) \end{cases}\)
możemy zapisać te liczby w postaci
\(17 k +5 \\ 14 k + 7\)
\(k \in C\)
czyli
\(3k - 2\)
czyli
\(x = - 2 ( mod 3 )\)
i do jednego równania sprowadzasz swój problem.

[irena]

nie wiem czy Ci pomoże , ale :
\(\begin{cases}x=7(mod14)\\ x=5(mod17) \end{cases}\)
możemy zapisać te liczby w postaci
\(17 k +5 \\ 14 k + 7\)

To nieprawda, to nie ta sama wielokrotność.
Tutaj:
\(x=17k+5=14t+7\)

[KamilWit]

możliwe, ale wyszła z tego układu prawda .
przypadek hmm ?
że
\(x = - 2 ( mod 3 )\)
bo głównie o to mi chodziło
ale ogólnie, tak masz rację : D

[irena]

Nie wyszła prawda. Bo
\(-2\neq-7\ (mod14)\)
i
\(-2\neq39\ (mod17)\)

[KamilWit]

emm nie czaję ;x ?
skoro wynik to 175 + 238n
to dla 175
np.
\(175 \equiv -2 ( mod3) \equiv 1 (mod3)\)
hmm ?
chyba znowu przypadek : p ..
ale akurat co do najmniejszego rozwiązania wszystko co napisałem się zgadza : P ?

a może tak dla każdego przypadku będzie , gdy szukamy najmniejszego rozwiązania to :
\(\begin{cases}x \equiv7(mod14)\\ x \equiv 5(mod17) \end{cases}\)
i do tego \(x \equiv -2 ( mod3) \equiv 1 (mod3)\)
hmm ?

[irena]

Ale Twoja propozycja nie jest rozwiązaniem układu kongruencji!
Trzeba znaleźć taką liczbę, która w dzieleniu przez 14 daje resztę 7, a w dzieleniu przez 17 daje resztę 5.
Najmniejszą taką liczbą dodatnią jest 175.

[KamilWit]

nie ale dodatkowym warunkiem przez przypadek ( czy też nie hmm ? )
jest to, że liczba przy dzieleniu przez 3, daje resztę 1 : P .

[irena]

W dzieleniu przez 6 też daje resztę równą 1, ale co z tego? Nie bardzo rozumiem, o co Ci chodzi...