Równanie modulo

bluerek · Post autor: **bluerek** » 30 sty 2010, o 15:14

Proszę o pomoc w zadaniu:

1. Rozwiązać równanie: \(\displaystyle{ 13 \cdot _{17} x + _{17} 6=3}\)

BettyBoo · Post autor: **BettyBoo** » 30 sty 2010, o 15:24

\(\displaystyle{ \ \Rightarrow \ 13x\equiv_{17}-3\ \Rightarrow x\equiv_{17}-3\cdot 13^{-1}}\)

Teraz wystarczy tylko znaleźć element odwrotny do 13 modulo 17 - albo go "zgadniesz" albo wykorzystujesz (odwrotny) algorytm Euklidesa.

Pozdrawiam.

bluerek · Post autor: **bluerek** » 30 sty 2010, o 18:32

jak mam skorzystać z tego twierdzenia?

BettyBoo · Post autor: **BettyBoo** » 30 sty 2010, o 20:38

Najpierw stosujesz algorytm Euklidesa dla 13 i 17 (algorytm ten służy do szukania NWD), a potem przedstawiasz znalezione NWD za pomocą kombinacji liniowej 13 i 17 (to jest odwrotny algorytm Euklidesa). U Ciebie to wygląda tak:

\(\displaystyle{ 17=13+4,\ 13=4\cdot 4+1\ \Rightarrow \ 1=13-4\cdot 4=13-4\cdot (17-13)=5\cdot 13-4\cdot 17}\)

więc z tej równości mamy, że elementem odwrotnym do 13 modulo 17 jest 5 (bo \(\displaystyle{ 1\equiv_{17}5\cdot 13-4\cdot 17\equiv_{17}5\cdot 13}\))

Wobec tego - wracając do oryginalnego zadania - masz

\(\displaystyle{ x\equiv_{17}-3\cdot 5\equiv_{17}-15\equiv_{17}2}\)

Pozdrawiam.

bluerek · Post autor: **bluerek** » 31 sty 2010, o 09:56

a tego, że \(\displaystyle{ 13=4 \cdot 4+1}\) to nie kumam. błąd po prostu??

BettyBoo · Post autor: **BettyBoo** » 31 sty 2010, o 11:14

Ano błąd, sorry.

\(\displaystyle{ 17=13+4,\ 13=3\cdot 4+1\ \Rightarrow \ 1=13-3\cdot 4=13-3\cdot (17-13)=4\cdot 13-3\cdot 17}\)

\(\displaystyle{ x\equiv_{17}-3\cdot 4\equiv_{17}-12\equiv_{17}5}\)

Pozdrawiam.