tw chińskie nt reszt;

Archiwum kompendium.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11264
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3141 razy
Pomógł: 747 razy

tw chińskie nt reszt;

Post autor: mol_ksiazkowy »

Tw (chińskie o resztach)
Jeśli liczby sj są parami względnie pierwsze, zas rj są dowolne ale całkowite...... - grają one rolę reszt, podczas gdy sj są niekiedy zwane okresami - , zaś m jest iloczynem wszystkich sj , to istnieje wówczas d okładnie jedna l. naturalna x, ; którą co ważne, można efektywnie wyznaczyć...; i taka, że \(\displaystyle{ 1 q x q m}\) i ze dla j=1,...,n zachodzi poniższy ukłąd n kongruencji.......
\(\displaystyle{ x\equiv r_j \ (mod \ s_j)}\)
*


A wiec np jak ponizej pokazane dla s1 i s2 względnie pierwszych, zawsze znajdziemy liczbę, która w dzieleniu przez s1 i s2 daje z góry ustalone reszty r1 i r2, i liczba ta jest nie większa niż s1s2. Tu akurat łatwo zgadnąc, ze x=13, ale jak by to można sobie prosto obliczyć......? ....tj intersuje nas jakas ogólna reguła a nie zgadywanie..........

Przykład
s1=2 s2=7 r1=1 r2=6
m=14 n=2
tj. \(\displaystyle{ x \equiv 1 \ (mod \ 2)}\)
\(\displaystyle{ x \equiv 6 \ (mod \ 7)}\)


Metoda pierwsza

Układamy w dwóch rzędach po 14 kwadratów. Każdemu odpowiada kolejna liczba naturalna. Podzieliliśmy sobie kwadraty z pierwszego rzędu na 7 szufladek po dwa w każdej. I analogicznie kwadraty z drugiego rzędu są podzielone na 2 szufladki po siedem kwadratów w każdej. Teraz widzimy, że tylko kwadrat o numerze x =13 leży w obu szufladkach na miejscach r1=1 [w pierwszym rzędzie] i r2=6 [w drugim].

Drugi sposób jest taki:
Rysujemy szachownicę 14x14 (bo s1s2=14), wpisując kolejne liczby naturalne 1..14 na przekątnej. Szachownica jest podzielona na 14 rozłącznych prostokątów 2x7. Teraz nakładamy je na siebie i w wyniku otrzymujemy matrycę [macierz],która jest pokazana poniżej. Teraz wybieramy wiersz \(\displaystyle{ i \{1,2\}}\) \(\displaystyle{ i \equiv \ 1 \ (mod \ 2)}\) oraz kolumnę \(\displaystyle{ j \{1,...,7\}}\): \(\displaystyle{ j \equiv 6 \ (mod \ 7)}\).
Mamy i=1, j=6. W przecięciu wiersza o numerze i z kolumną o numerze j odczytujemy rozwiązanie
x = 13.

zob, rys.
Uwaga: w ostatnim rys
mamy ilustracje dla
\(\displaystyle{ x \equiv 1 \ (mod \ 2)}\):
\(\displaystyle{ x \equiv 1 \ (mod \ 3)}\):
\(\displaystyle{ j \equiv 4 \ (mod \ 5)}\):
tj x=19



Metoda, którą podał Euler jest taka: [dla ustalenia uwagi niech n=4 ]. Szukamy liczby \(\displaystyle{ x = A_1r_1 + A_2r_2 + A_3r_3 + A_4r_4 + ns_1s_2s_3s_4}\) , przy czym liczba Aj przy dzieleniu przez sj daje resztę 1, oraz jest podzielna przez pozostałe sk, zaś n jest liczbą całkowitą.

Przykład:
s1=3, s2=5, s3=7, s4=11, reszty: r1=1, r2=2, r3=3, r4=1. Wtedy x = A +2B + 3C + D + 1155n. Wyliczamy A=385, B=231, C=330, D=210. Podstawiając x = 385 + 462 + 990 + 210 + 1155n = 2047 + 1155n. A ponieważ ma być x < 1156, musi być n = -1, tj. x = 892.


Zadania
1. Na forum matemtyka.pl jest pewna liczba userów. Gdy ustawić ich po pięciu to zostaje jeden, a gdy się ich ustawi po jedenastu, to zostanie siedmiu. Ilu co najmniej jest ich tam ....?
2. Wyznacz liczbę x, której istnienie orzeka twierdzenie chińskie o resztach, gdy s1=2, s2=3, s3=7, r1=0, r2=2, r3=3
3. Znajdź x metodą Eulera, gdy s1=2, s2=3, s3=5, s4=7, s5=11, rj = j dla j = 1, ..., 5

* Starożytni Chińczycy rozwazali rózne zjawiska okresowe..., tygodnie, lata, kwadry księzyca etc...zadali oni proste pytanie: co się stanie, jesli zaczniemy badać dwa ...lub wiecej takie cykle jednocześnie..?Jest to interesujące szczególnie gdy oba przejawiaja sie z róznymi czestościami...... Wtedy powstaje bardzo ciekawy obraz...takie sa "korzenie" tegoż twierdzenia..


rys.
Awatar użytkownika
Mariusz M
Użytkownik
Użytkownik
Posty: 6903
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E
Podziękował: 2 razy
Pomógł: 1246 razy

tw chińskie nt reszt;

Post autor: Mariusz M »

\(\displaystyle{ \begin{cases}x=m_{1} \mod p_{1}\\x=m_{2} \mod p_{2} \end{cases}}\)

Moduły muszą być parami względnie pierwsze
Wybieramy dwie kongruencje i sprawdzamy powyższy warunek NWD(p1,p2)=1
Na podstawie rozszerzonego algorytmu Euklidesa obliczamy liczby a i b
takie że
\(\displaystyle{ a*p_{1}+b*p_{2}=NWD(p_{1},p_{2})}\)
czyli
\(\displaystyle{ a*p_{1}+b*p_{2}=1}\)

\(\displaystyle{ x=(a*p_{1}*m_{2}+b*p_{2}*m_{1}) \mod (p_{1}*p_{2})}\)

Jeżeli mamy więcej kongruencji to biorąc dowolną parę kongruencji zredukujemy ilość kongruencji o jeden
(z dwóch kongruencji dostaniemy jedną kongruencję)


Algorytm Euklidesa

NWD(a,0)=a;
NWD(b,a)=NWD(a,b)
NWD(a,b)=NWD(a mod b,b)

np

x=48
y=18

x=12
y=18

x=12
y=6

x=0
y=6

NWD(48,18)=6

Współczynniki

6=18-12
6=18-(48-2*18)
6=-48+3*18

Współczynniki
a=-1
b=3
Zablokowany