Dzielenie Dominika: Liczba K jest najmniejsza liczba naturalna, ktora przy dzieleniu przez 3 daje reszte 1, przy dzieleniu przez 4 daje reszte 2, przy dzieleniu przez 5 daje reszte 3, przy dzieleniu przez 6 daje reszte 4, przy dzieleniu przez 7 daje reszte 5

Metis: Pełne polecenie?

adam: K=1678

Dominika: To pełne polecenie

adam: A to pełna odpowiedź: K=1678

Dominika: Odpowiedź to K= 418, jak to obliczyć ?

adam: Upss, to lepsza jesteś ode mnie.

Dominika: Po Prostu taka jest odpowiedź w książce

Adam: stosując chińskie twierdzenie o resztach mamy K=1 mod 3, K=0 mod 2, K=3 mod 5, K=5 mod 7 ma jedyne rozwiązanie 1≤K≤210 podstawiając K=3k+1 sprawdzamy najmniejsze rozwiązanie spełniające K=0 mod 2 etc. dostajemy K=208+k*210 teraz widzimy że 418 to najmniejsze rozwiązanie

Pytający: Mamy układ:

⎧	x ≡3 1
⎜	x ≡4 2
⎨	x ≡5 3
⎜	x ≡6 3
⎩	x ≡7 5

Zapis x ≡_a b oznacza, że x przystaje modulo a do b (reszta z dzielenia x przez a wynosi b, (x)mod(a)=b). Najprościej chyba będzie rozpatrywać pary równań:

⎧	x ≡3 1
⎩	x ≡4 2

Z pierwszego równania mamy: x=1+3*i Szukamy najmniejszego i, dla którego tak określony x spełnia drugie równanie: i=0, x=1, x ≡₄ 1 i=1, x=4, x ≡₄ 0 i=2, x=7, x ≡₄ 3 i=3, x=10, x ≡₄ 2 Zatem z tych równań otrzymujemy: x ≡_3*4 10 ⇒ x ≡₁₂ 10 Bierzemy kolejne równanie z pierwotnego układu równań:

⎧	x ≡12 10
⎩	x ≡5 3

x=10+12j j=0, x=10, x ≡₅ 0 j=1, x=22, x ≡₅ 2 j=2, x=34, x ≡₅ 4 j=3, x=46, x ≡₅ 1 j=4, x=58, x ≡₅ 3 x ≡_12*5 58 ⇒ x ≡₆₀ 58 Bierzemy kolejne równanie z pierwotnego układu równań:

⎧	x ≡60 58
⎩	x ≡6 4

x=58+60k k=0, x=58, x ≡₆ 4 x ≡_60*6 58 ⇒ x ≡₃₆₀ 58 Bierzemy kolejne równanie z pierwotnego układu równań:

⎧	x ≡360 58
⎩	x ≡7 5

x=58+360m m=0, x=58, x ≡₇ 2 m=1, x=418, x ≡₇ 5 x ≡_360*7 418 ⇒ x ≡₂₅₂₀ 418 ⇒ x=418+2520n Czyli ostatecznie K=418.

Dominika: Dziękuję bardzo, rozumiem

Pytający: Zrobiłem błąd: Jako że 60 i 6 nie są względnie pierwsze (NWD≠1), w przedostatniej parze równań powinienem był napisać: x ≡_NWW(60,6) 58 ⇒ x ≡₆₀ 58 I ostatnia para wygląda wtedy:

⎧	x ≡60 58
⎩	x ≡7 5

x=58+60m m=0, x=58, x ≡₇ 2 m=1, x ≡₇ 6 (dodajemy 60=7*8+4, więc reszta z dzielenia zwiększa się o 4mod7) m=2, x ≡₇ 3 ((6+4)mod7=3) m=3,x ≡₇ 0 m=4, x ≡₇ 4 m=5, x ≡₇ 1 m=6, x ≡₇ 5, x=418 x ≡_NWW(60,7) 418 ⇒ x ≡_60*7 418 ⇒ x ≡₄₂₀ 418 ⇒ x = 418 +420n