Układy kongruencji - 3 i więcej równań - czy można je rozwiązać w ten sposób?

Question

Witajcie! :)

Czy można układy kongruencji posiadające 3 i więcej równań rozwiązywać w taki sposób?

{x ≡ 0 (mod 13)
{x ≡ 4 mod 55)
x=13y
13y ≡ 4 (mod 55)
NWD(55,13)=?
i lecimy z obliczeniami.

Jeśli tak, to czy ktoś mógłby rozpisać to na następujących przykładach?
a)
{x ≡ 1 (mod 13)
{x ≡ 1 (mod 17)
{x ≡ 1 (mod 23)
b)
{x ≡ 2 (mod 3)
{x ≡ 3 (mod 5)
{x ≡ 2 (mod 7)

Answer 1

Moim zdaniem początek jest dobry, dalej nie wiem co tam to NWD wyrabia, oraz co oznacza i lecimy z obliczeniami. - jakimi?

Generalnie do rozwiązywania dużych układów może posłużyć chińskie twierdzenie o resztach, ale że tu układy są krótkie to jest prostszy sposób - w sumie trochę takie liczenie na palcach, który zakrawa o to co ty robiłeś (chociaż napisałeś tylko dwie linijki z których jedna nie ma dla mnie sensu).

Dla przykładu a) mamy wszędzie tę samą liczbę więc wystarczy ją wstawić za x i git, dla drugiego:

{x ≡ 2 (mod 3)
{x ≡ 3 (mod 5)
{x ≡ 2 (mod 7)

x ≡ 2 (mod 3) => x = 3i + 2 - wszystkie liczby tej postaci spełniają to równanie. Szukamy takiego i żeby liczba w tej postaci  spełniła drugie równanie
3i + 2 ≡ 3 (mod 5)          - robimy to po prostu podstawiając kolejne liczby za i
3*1 + 2 ≡ 0
3*2 + 2 ≡ 3   - znalazłem 
więc nasze i = 3. Mamy więc z dwóch pierwszych równań:

{3*2 + 2 ≡ 2 (mod 3)
{3*2 + 2 ≡ 3 (mod 5)
więc:
{8 ≡ 2 (mod 3)
{8 ≡ 3 (mod 5)
więc:
x ≡ 8 (mod 3*5)
więc 
x ≡ 8 (mod 15)
zostają nam dwa równania:

{x ≡ 8 (mod 15)
{x ≡ 2 (mod 7)

bierzemy któreś z nich - dowolnie i robimy tak jak przedtem, np dla pierwszego x = 15j + 8
15j + 8 ≡ 2 (mod 7)
15 * 1 + 8 ≡ 2
czyli j = 1

na końcu nasza liczba to 15*i+8 = 23
 

Mam nadzieję że załapałeś algorytm 

 

 

Comments

Rzucisz okiem na a), które robiłem sposobem, który podałeś?

---

Nie bo patrząc na 6,7 linijkę (jak dobrze liczę)
13i + 1 ≡ 1 (mod 17)
13i ≡ 0 (mod 17)
----------------------- dotąd było ok, lecz najmniejszym i które spełnia daną kongruencje nie jest 17, jest nim i = 0, bo:
13 * 0 ≡ 0 (mod 17)
0 ≡ 0 (mod 17)
tak samo dalej, więc x spełniającym dane równanie jest x = 1