ilość rozwiązań kongruencji

[leszczu450]

Cześć!

Rozwiązuje sobie zwykłe kongruencje nie do końca wiem ile i czy w ogóle będą rozwiązania. Prosiłbym Was o pomoc bo to chyba podstawa żebym wiedział od czego to zależy czy rozwiązanie istnieje czy też nie : )

Jeśli chodzi o moją wiedzę to wydaje mi się, że jest tak:

Jeśli mamy : \(\displaystyle{ ax \equiv b (\mod c )}\)
To przede wszystkim, żeby istniało jakiekolwiek rozwiązanie to \(\displaystyle{ NWD(a,c) | b}\).
Jeśli nie zachodzi ta podzielność to o rozwiązaniu chyba nie ma co gadać(tak wywnioskowałem na podstawie wyliczonych przykładów).
Dalej, jeśli to \(\displaystyle{ NWD}\) nie równa się \(\displaystyle{ 1}\), ale nadal dzieli nam \(\displaystyle{ b}\) to rozwiązań jest skończona ilość, nie przekraczająca liczby modulo.
I już na koniec, jeśli \(\displaystyle{ NWD=1}\) i dzieli \(\displaystyle{ b}\) to mamy nieskończenie wiele rozwiązań z okresem równym modułowi.

Dobrze myślę? Proszę Was o pomoc i z góry dziękuję : )

[yorgin]

Jak NWD nie dzieli, to faktycznie nic nie wyjdzie.

Jeśli NWD wychodzi \(\displaystyle{ 1}\) i dzieli \(\displaystyle{ b}\), to wychodzi jak napisałeś.

Ostatni przypadek, przykład wraz z rozwiązaniem:

\(\displaystyle{ 2x\equiv 4\mod 6\\
2x-4=6k\\
x=3k+2}\)

A więc wychodzi nieskończenie wiele rozwiązań. Zupełnie nie rozumiem, dlaczego ograniczasz się tylko do liczb nie większych od modułu.

[leszczu450]

Rozwiązując taki przykład na zajęciach:
\(\displaystyle{ 10x \equiv 15 (\mod 35)}\)
prowadzący powiedział nam, że jest tutaj pięć rozwiązań. I wypisane jest nawet w skrypcie z odpowiedziami: \(\displaystyle{ 5, 12, 19, 26, 33}\).

[yorgin]

Ale dlaczego ograniczamy się tylko do takich liczb?

\(\displaystyle{ 40}\) też jest rozwiązaniem tej kongruencji.

W ogólności każda liczba postaci \(\displaystyle{ x=5+7k}\) jest jej rozwiązaniem.

[leszczu450]

yorgin, wpisz w googlach: bobiński grzegorz mat dyskretna.
Zobacz zadanie 34d. I zjedź na dół i zobacz odpowiedź. Mam nadzieję, że to nie jest łamanie zasad regulaminu to co teraz pisze : ) Jeśli tak to : Mea Culpa!

[yorgin]

Odsyłanie do wykładów zewnętrznych nie wydaje mi się być łamaniem regulaminu.

Wklej link do pliku, ja odnajduję tylko i tak posiadany już przeze mnie wykład oraz zbiór do matematyki dyskretnej II, gdzie o kongruencjach nic nie ma.

[leszczu450]

yorgin, ups, no masz rację. Nie jest tak łatwo dostępny. Wiesz co, przepisze Ci ten komentarz i tyle : )

-- 2 kwi 2013, o 13:55 --

Ponieważ \(\displaystyle{ (10,35)=5|15}\) , więc kongruencja posiada rozwiązanie. Mamy \(\displaystyle{ 5}\) rozwiązań modulo \(\displaystyle{ 35}\). Jedno z nich otrzymujemy rozwiązując kongruencję : \(\displaystyle{ 2x \equiv 3 (\mod 35)}\). Skąd dostajemy, że \(\displaystyle{ x \equiv 19 (\mod 35)}\). Pozostałe rozwiązania otrzymujemy dodając wielokrotności \(\displaystyle{ 7}\). A więc ostatniecznie mamy: \(\displaystyle{ x \equiv 5, 12, 19, 26, 33 (\mod 35)}\).

Słowo w słowo ze skryptu : )