• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

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

VPS Starter Arubacloud
0 głosów
2,589 wizyt
pytanie zadane 20 czerwca 2018 w Matematyka, fizyka, logika przez tiesto.ulic Obywatel (1,010 p.)
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)

1 odpowiedź

+1 głos
odpowiedź 22 czerwca 2018 przez k222 Nałogowiec (30,150 p.)
wybrane 27 czerwca 2018 przez tiesto.ulic
 
Najlepsza

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 laugh
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 wink

 

 

komentarz 22 czerwca 2018 przez tiesto.ulic Obywatel (1,010 p.)

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

1
komentarz 22 czerwca 2018 przez k222 Nałogowiec (30,150 p.)
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

Podobne pytania

0 głosów
1 odpowiedź 357 wizyt
0 głosów
0 odpowiedzi 309 wizyt
0 głosów
1 odpowiedź 525 wizyt

92,454 zapytań

141,263 odpowiedzi

319,099 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...