Wyznacz liczbę

[piti-n]

Prosze wyznaczyć liczbę naturalną \(\displaystyle{ x \in \mathbb N}\) która spełnia równania
\(\displaystyle{ x \approx 8 mod 13 \\
x \approx 9 mod 24}\)

ułożyłem do tego równanie.
\(\displaystyle{ 13a+8=24b+9}\)
Później rozwiązuję jak normalne równanie diofantyczne i coś nie wychodzi.

[adambak]

znak \(\displaystyle{ \approx}\) jest według mnie złym wyborem w tym przypadku..

tutaj wszystko świetnie wytłumaczone jest: ... C4.85zania.
idea jest prosta, warto dokładnie przeczytać..-- 22 maja 2012, o 00:28 --niby w Chińskim twierdzeniu o resztach jest trochę liczenia, ale tylko dwie kongruencje są tutaj, więc liczy się bardzo szybko..

[piti-n]

ok, to zrobiłem tak.

\(\displaystyle{ NWD(8,9)=1}\)
\(\displaystyle{ N=8 \cdot 9=72}\)
\(\displaystyle{ N _{1}= \frac{72}{8}}\)


\(\displaystyle{ NWD(8,9)=1=x \cdot 8+y \cdot 9}\)
\(\displaystyle{ x _{1}=1}\)


\(\displaystyle{ x=13 \cdot 1 \cdot 9=117= _{72}45}\)

[adambak]

no i jak widać, jest źle.. trzymając się oznaczeń ze strony którą podałem:

\(\displaystyle{ N=13\cdot 24 = 312}\)
\(\displaystyle{ N_1=24}\)
\(\displaystyle{ N_2=13}\)

\(\displaystyle{ a_1=8, \ a_2=9}\)

\(\displaystyle{ NWD(13,24)=-11\cdot 13 + 6\cdot 24}\)

\(\displaystyle{ x_1=6, \ x_2=-11}\)

wobec tego: \(\displaystyle{ 13\cdot (-11)\equiv_{24} 1}\) oraz \(\displaystyle{ 13\cdot 6\equiv_{13} 1}\)

czyli szukane rozwiązanie: \(\displaystyle{ x=9 \cdot (-11)\cdot 13 + 8\cdot 6 \cdot 24\equiv_{312}-135\equiv_{312} 177}\)

jak widać rozwiązanie \(\displaystyle{ x=177}\) spełnia zarówno \(\displaystyle{ x \mod{13}=8}\) jak i \(\displaystyle{ x\mod{24}=9}\). Oczywiście jest to najmniejsze naturalne rozwiązanie, jak chcemy więcej to dodajemy wielokrotność \(\displaystyle{ 312}\). Kluczem tutaj jest fakt, że \(\displaystyle{ a_i x_i N_i\equiv_{n_i} a_i\cdot 1=a_i}\), ponieważ \(\displaystyle{ N_i=\frac{N}{n_i}}\), a że moduły były względnie pierwsze to znajdujemy odwrotnośc modularną \(\displaystyle{ N_i}\) oraz oznaczamy ją jako \(\displaystyle{ x_i}\), dzięki czemu mamy: \(\displaystyle{ N_i x_i \equiv_{n_i} 1}\).

ale jak się teraz zastanawiam to jest to trochę przerost formy nad treścią. stosowanie Chińskiego o resztach dla układu dwóch kongruencji jest nieco śmieszne i napewno da się to zrobić lepiej (tak czy siak, trzeba to twierdzenie i ten sposób rozwiązania znać, bo bywa niezmiernie przydatny)..-- 22 maja 2012, o 12:52 --ok, no to można też rozwiązać to z tego co pisałeś w pierwszym poście:

\(\displaystyle{ 13a = 24b +1}\)
\(\displaystyle{ 13a-24b=1=NWD(13,24)}\) tak się szczęśliwie zdarzyło..

no to z rozszerzonego algorytmu Euklidesa szukamy i znajdujemy \(\displaystyle{ a,b}\) otrzymując:
\(\displaystyle{ 13\cdot (-11) + 24\cdot 6=1}\), czyli \(\displaystyle{ a=-11, \ b=-6}\)..

no to szukane rozwiązanie to: \(\displaystyle{ x=13a+8=24b+9=13\cdot(-11)+8=24\cdot(-6)+9=-135}\)
dodając do niego wielokrotności \(\displaystyle{ 312}\) będziemy otrzymywać kolejne rozwiązania spełniające układ tych dwóch kongruencji..