szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Mężczyzna
PostNapisane: 7 paź 2010, o 20:34 
Użytkownik

Posty: 5822
Lokalizacja: Kraków
Twierdzenie (wersja klasyczna)
Niech dane będą liczby m_1,...,m_n parami względnie pierwsze. I niech M=m_1...m_n oraz a_j są to dowolne reszty i niech b_j będą określone y=b_j jako rozwiązanie kongruencji
(*) y\frac{M}{m_j} \equiv 1 \ (mod \ m_j) dla j=1,...,n Wtedy ogólnym rozwiązaniem układu
\begin{cases} x \equiv a_1 \ (mod \ m_1) \\x \equiv a_2 \ (mod \ m_2)  \\...\\x \equiv a_{n-1} \ (mod \ m_{n-1}) \\x \equiv a_n \ (mod \ m_n) \end{cases}
jest x \equiv a_1b_1\frac{M}{m_1}+...+a_nb_n\frac{M}{m_n} \ (mod \ M)

Uwagi: Założenie iż liczby są parami względnie pierwsze jest istotne. Dzięki niemu liczby b_j istnieją gdyż m_ji \frac{M}{m_j} są względnie pierwsze i kongruencje pomocnicze (*) mają rozwiązanie y. Istnieje najmniejsza liczba naturalna x, będąca rozwiązaniem układu (i można ją wprost obliczyć).


Metoda graficzna
Przykład (n=2)
\begin{cases} x \equiv 10 \ (mod \ 6) \\x \equiv 17 \ (mod \ 5) \end{cases}

Rysuje się kwadrat o boku 30 (tj. m_1m_2), I na jego przekątnej ustawia kolejne liczby naturalne. Kwadrat dzieli się i rozcina na prostokąty 6 \times 5 (bo m_1=6, \ m_2=5), które następnie nakłada się na siebie uzyskując macierz M. Wyszukuje się liczby c_1 \in \{ 1,2,3,4,5,6 \} takiej że c_1 \equiv 10 \ (mod \ 6) oraz c_2 \in \{ 1,2,3,4,5 \} takiej że c_2 \equiv 17 \ (mod \ 5), tj. c_1=4 , \ c_2=2. Element leżący na przecięciu wiersza o numerze c_1 i kolumny o numerze c_2 daje w M rozwiązanie (M_{4,2}=22)
M=\left[\begin{array}{cccccc}1&7&13&19&25\\26&2&8&14&20\\21&27&3&9&15\\16&22&28&4&10\\11&17&23&29&5\\6&12&18&24&30\end{array}\right]

Uwagi:
Dzięki założeniu iż m_1 i m_2 są względnie pierwsze żadne dwa elementy nie nałożą się i cała macierz M zostanie wypełniona.


Przykład
\begin{cases} x \equiv 1 \ (mod \ 2) \\x \equiv 1 \ (mod \ 3)\\x \equiv 2 \ (mod \ 5)\\x \equiv 4 \ (mod \ 7)  \end{cases}

Rozwiązanie
Wystarczy rozwiązać kongruencje pomocnicze: b_1=1, \ b_2=1, \ b_3=3, \ b_4=4 a więc x \equiv 907 \equiv 67 \   (mod \ 210). Można też x obliczyć w w nieco inny sposób, tj. redukując ilość kongruencji (przez zastąpienie ich równoważnymi): w tym zadaniu mogłoby to wyglądać np. tak:
\begin{cases} x \equiv 1 \ (mod \ 6) \\x \equiv 32 \ (mod \ 35) \end{cases} stąd x=32+35m, i m \in 
\{0,1,2,3,4,5 \}. Dla m=0 \ x=32 tj. wynik błędny ale druga próba m=1, \ x=67 jest udana.


Twierdzenie chińskie o resztach (wersja uogólniona (algebra))
Załóżmy, że A_1, ...,A_n (n>1 ) są to ideały w pierścieniu przemiennym R z jedynką, takie że jeśli i \neq j to A_i+A_j=R Wtedy jeśli b_1,...,b_n \in R to istnieje b \in R takie, że: b \equiv b_j \ (mod \ A_j) dla j=1,...,n oraz b jest wyznaczone jednoznacznie modulo A_1 \cap ... \cap A_n

Jako wniosek uzyska się CRT (twierdzenie klasyczne) biorąc pierścień liczb całkowitych Z i zbiory A_j które tworzą wszystkie całkowite wielokrotności liczby j.


:arrow: Notka historyczna:
Twierdzenie chińskie o resztach (ang. skrót CRT) jest jednym ze starszych odkryć z teorii liczb. Opisane zostało w księdze Mathematical Treatise in Nine Sections (z 1247 r.) napisanej przez Qin Jiushao, choć znane było Chińczykom jeszcze wcześniej; pisze o nim też Fibonacci w swym dziele Liber Abaci, ok. 1202 r.
Sens jego brzmi: „Zawsze można znaleźć liczbę, która w dzieleniu przez zadany układ (parami względnie pierwszych liczb da zadany układ reszt.”
Praktyczne zastosowanie CRT wynika ze sposobu, dzięki możliwościom jakie dają komputery, zakodowania dużych liczb przez pewien układ warunków z użyciem liczb dużo mniejszych.W programie Mathematica, istnieje funkcja ChineseRemainder[\{r1, r2, ...\}, \{m1,  m2, ...\}], której wynikiem jest najmniejsza liczba x, taka że x \equiv r_i \ (mod \ m_i) dla i=1,..,n.


Zadania do pracy własnej:
(Uwaga: Prosze nie pisac tu rozwiazań :D)
:arrow:
1. (Czech-Slovak, 1994r.) Wykazać, że istnieje rosnący ciąg liczb naturalnych a_n mający tę własność iż przy dowolnym k \geq 0 w ciągu b_n=k+a_n jest tylko skończona ilość wyrazów które są liczbami pierwszymi
2. Niech n będzie dowolną liczbą całkowitą większą od zera. Wykaż że istnieje n kolejnych dodatnich liczb całkowitych, które nie są potęgami liczb naturalnych o wykładniku większym od 1.
3. Znajdź najmniejszą liczbę naturalną n, taką, że liczby:
\sqrt[5]{\frac{n}{143}},\sqrt[7]{\frac{n}{77}}, \sqrt[11]{\frac{n}{65}}, \sqrt[13]{\frac{n}{35}} są całkowite.
4. Reszta przy dzieleniu liczby całkowitej m przez 23 wynosi 22 , zaś reszta przy dzieleniu m przez 17 to 13. Oblicz resztę przy dzieleniu liczby m przez 391. Znajdź możliwie najmniejszą liczbę o tej własności
5. Dla dowolnie ustalonej liczby naturalnej obliczyć ile jest liczb całkowitych x z przedziału <1,n> takich, że x^3-x jest podzielne przez n
6. Niech a i n to będą liczby naturalne takie iż 1+a^2 dzieli się przez n. Wykazać, że istnieje liczba naturalna b, taka iż 1+b^2 dzieli się przez n(n^2+1)
7*. (USA, 1997r.) Wykaż, że dla dowolnej liczby naturalnej n istnieje jeden jedyny wielomian Q o współczynnikach ze zbioru \{0,1,...,9 \} taki, że
Q(-2)=Q(-5)=n
8*. Bez pomocy komputera znajdź x takie, że:
\begin{cases} x \equiv 1 \ (mod \ 2) \\x \equiv 4 \ (mod \ 5) \\x \equiv 2 \ (mod \ 7) 
\\x \equiv 6 \ (mod \ 19)\\x \equiv 33 \ (mod \ 83)  \end{cases}
9. Wyznacz najmniejszą możliwie czwórkę kolejnych liczb naturalnych, które dzielą się bez reszty kolejno przez 3,5,7,11
10. Korzystając z CRT rozwiąż kongruencję
19x \equiv 1 \ (mod \ 140)
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 twierdzenie chinskie o resztach - zadanie 2  konrad18m  6
 Twierdzenie Picka, a wzrost grupy wolnej abelowej.  xiikzodz  0
 Twierdzenie Pickarda i równanie liniowe  Tomciojag  0
 twierdzenie Kroneckera-Capelli'ego  student mibm14  4
 Twierdzenie sinusów i cosinusów -zadania  kola50  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl