Układ kongruencji

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
JAzz
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 11 gru 2008, o 15:08
Płeć: Mężczyzna
Lokalizacja: Leszno.Zielona Góra

Układ kongruencji

Post autor: JAzz » 24 cze 2010, o 19:50

Witam.
Wyznaczyć za pomocą tw.ch.o resztach. Przykład i to co ja do tej pory zrobiłem.

\(\displaystyle{ \begin{cases} x \equiv 7(mod 22) \\ x \equiv 18(mod 31) \end{cases}}\)



\(\displaystyle{ x = 22t + 7}\)

\(\displaystyle{ 22t + 7 \equiv 18(mod 32)}\)

\(\displaystyle{ 22t \equiv 11(mod 31)}\)

\(\displaystyle{ 2t \equiv 1(mod 31)}\)
Nie wiem jak wyznaczyć t. Proszę o pomoc.
Pozdrawiam.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

BettyBoo
Użytkownik
Użytkownik
Posty: 5356
Rejestracja: 10 kwie 2009, o 10:22
Płeć: Kobieta
Lokalizacja: Gliwice
Pomógł: 1380 razy

Układ kongruencji

Post autor: BettyBoo » 24 cze 2010, o 20:03

No fajnie, ale co te Twoje obliczenia mają wspólnego z chińskim twierdzeniem o resztach? Ty to obliczasz wprost, zwykłą metodą podstawiania.

Co do Twojego pytania - generalnie mamy tak, że

\(\displaystyle{ 2t \equiv 1(mod 31)\ \Leftrightarrow \ \exists k\in Z\quad 2t+31k=1}\)

Zatem rozwiązanie tej kongruencji jest równoważne z rozwiązaniem odpowiedniego równania diofantycznego (a na to są wzory).

Oczywiście, w Twoim przykładzie można zgadnąć to rozwiązanie (łatwo widać, jakiej postaci liczby pomnożone przez \(\displaystyle{ 2}\) dają liczbę postaci \(\displaystyle{ 31k+1}\))

\(\displaystyle{ t=16+31s,\ s\in Z}\).

Pozdrawiam.

ODPOWIEDZ