twierdzenie chinskie o resztach

[konrad18m]

Mam pytanie, zrobiłem zadanie ale nie jestem przekonany co do jego słuszności ;/ oto ono:

znajdz najmniejsza liczbę naturalną, która przy dzieleniu przez liczby \(\displaystyle{ 3,5,7}\) daje odpowiednio reszty: \(\displaystyle{ 0,3,3}\)

\(\displaystyle{ \begin{cases}q=0 (mod 3)\\
q=3 (mod 5)\\
q=3 (mod 7) \end{cases}}\)

\(\displaystyle{ 0, 3, 6, 9 .....213\\
3, 8, 13, 18 ..... 213\\
3, 10, 17 ..... 213}\)

Dobrze to jest?

Robiłem to ręcznie ;/ jest moze na to jakis inny lepszy sposób niz twierdzenie chinskie o resztach?

Z góry dziękuje.

[eMaerthin]

nie zauważyłeś, że 3 wszędzie też się powtarza ... niepotrzebnie szukałeś tak daleko z chińskiego tw. o resztach jeśli rozwiązanie istnieje, to jedno z nich jest na pewno niemniejsze od 0 i mniejsze niż iloczyn tych liczb, względem których liczymy mod, czyli w Twoim przypadku jedno z rozwiązań jest w zbiorze \(\displaystyle{ \{0,1,2,...,3\cdot 5\cdot 7-1\}}\) = \(\displaystyle{ \{0,1,2,...,104\}}\)

Jak masz ogólny problem znalezienia liczby, która względem trzech innych daje określone reszty z dzielenia, możesz ten problem podzielić na dwa prostsze. Na przykładzie:
Znajdź liczbę, która spełnia:
\(\displaystyle{ x\equiv 0 \pmod{3}}\)
\(\displaystyle{ x\equiv 3 \pmod{5}}\)
\(\displaystyle{ x\equiv 3 \pmod{7}}\)
można rozłożyć na poniższe problemy:

Najpierw szukamy liczby \(\displaystyle{ y}\), która spełnia dwa z powyższych równań, czyli np.:
\(\displaystyle{ y\equiv 0 \pmod{3}}\)
\(\displaystyle{ y\equiv 3 \pmod{5}}\)
i tu wypisujemy liczby od 0 do \(\displaystyle{ 3\cdot 5-1=15-1=14}\) aż trafimy na dwie takie same:
0,3,5,9,12 - te które spełniają pierwszą równość modularną
3,8,12 - te które spełniają drugą równość modularną

powtórzyła się 3 więc rozwiązaniem powyższych dwóch równości modularnych jest \(\displaystyle{ y=3+3\cdot 5\cdot k}\) czyli \(\displaystyle{ y\equiv 3\pmod{15}}\). Do tak otrzymanego rozwiązania dołączamy trzecią równość modularną i otrzymujemy kolejny problem, którego rozwiązaniem jest rozwiązanie naszego zadania a oto ten problem:
\(\displaystyle{ x\equiv 3 \pmod{15}}\)
\(\displaystyle{ x\equiv 3 \pmod{7}}\)
i już widać, że skoro w obu kongruencjach występuje po prawej stronie 3, to najmniejszym rozwiązaniem jest właśnie \(\displaystyle{ x=3}\).

[kropka+]

Można to rozwiązać tak:
Szukamy liczby a podzielnej przez 3 czyli
\(\displaystyle{ a=3k}\) dającej reszty jak w zadaniu czyli:

\(\displaystyle{ \begin{cases} 3k=5l+3 \\ 3k=7m+3 \end{cases} \Rightarrow \begin{cases} 3k-3=5l \\ 3k-3=7m \end{cases}}\)

Wynika z tego, że \(\displaystyle{ 3k-3}\) dzieli się przez 35 (bo jest to NWW liczb 5 i 7) czyli:

\(\displaystyle{ 3k-3=35n \Rightarrow 3k=35n+3}\)

Podstawiamy kolejno n od 1 do ilu trzeba i wychodzi \(\displaystyle{ n=3
\Rightarrow 3k=108=a}\)

[eMaerthin]

Podstawiamy kolejno n od 1 do ilu trzeba i wychodzi \(\displaystyle{ n=3
\Rightarrow 3k=108=a}\)

Nic nie stoi na przeszkodzie by \(\displaystyle{ n=0}\) wtedy mamy mniejszą liczbę naturalną, a zadanie mówi o znalezieniu najmniejszej
\(\displaystyle{ n=0 \Rightarrow 3k=3=a}\)

[kropka+]

eMaerthin, \(\displaystyle{ a=3 \Rightarrow \frac{3}{5}=0 \ r.5 \wedge \frac{3}{7}=0 \ r.7}\)
czyli nie spełnia warunków podanych w treści zadania.

[abc666]

kropka+, mylisz się.
\(\displaystyle{ 3 : 5 =0\ r\ 3}\)
bo
\(\displaystyle{ 0\cdot 5+3 = 3}\)

[kropka+]

Rzeczywiście, małe zaćmienie umysłu.