Równanie modulo

lelek3 · Post autor: **lelek3** » 21 lut 2011, o 14:43

Witam wszyztkich użytkowników forum:)

Mam do zaliczenia egzamin z matematyki dyskretnej a mianowincie z części dotyczącej modulo..Wykładowca dał nam do rozwiązania coś takiego:
17x+ 8y=111

i powiedzia l żebyśmy rozwiązali to metoda modulo. Czy wie ktoś jak to rozwiązać?

Z góry dziękuję za wszelką pomoc:)

PMichalak · Post autor: **PMichalak** » 21 lut 2011, o 15:18

Rozszerzony algorytm Euklidesa.

Crizz · Post autor: **Crizz** » 21 lut 2011, o 15:27

Najpierw sprawdzamy, czy równanie ma rozwiązanie. \(\displaystyle{ (17,8)=1}\) i \(\displaystyle{ 1|111}\), więc nie ma problemu.

Potem bierzemy tę z liczb przy \(\displaystyle{ x,y}\), która jest liczbą pierwszą, czyli \(\displaystyle{ 17}\) i zamieniamy całe równanie na kongruencję modulo \(\displaystyle{ 17}\):
\(\displaystyle{ 17x+8y \equiv111(mod 17)}\). Oczywiście \(\displaystyle{ 17x \equiv 0(mod17)}\), więc szukamy rozwiązania kongruencji \(\displaystyle{ 8y \equiv 111(mod 17)}\).

lelek3 · Post autor: **lelek3** » 21 lut 2011, o 20:37

Dziękuje bardzo za pomoc