Multiplikativni inverz - postupak

Multiplikativni inverz - postupak 26.04.2009. u 15:10 · pre 213 meseci #1

Zelim da pronadjem multiplikativni inverz broja $a=50$ u $\mathbb{Z}_{137}$ odnosno da $(a \cdot a^{-1} \equiv 1 \pmod{ 137})$
Preko Euklidovog algoritma sam utvrdio da je GCD(50,137)=1, tako da uslovi za pronalazenje $a^{-1}$ postoje.

Prema resenju koje imam $a^{-1}=63$ .

E sad, kroz koji god online kalkulator inverza sam propustio ove brojeve uvek kao inverz dobijem broj 74.
Napisao sam i jednostavan C program koji iterativno prolazi kroz sve mogucnosti dok ne dobije ostatak 1 i takodje sam dobio rezultat 74.

Da li neko moze da napise formalan postupak kako se dolazi do resenja?

Re: Multiplikativni inverz - postupak 26.04.2009. u 16:17 · pre 213 meseci #2

U rešenju je greška.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: Multiplikativni inverz - postupak 26.04.2009. u 16:50 · pre 213 meseci #3

OK. Da li neko moze da napise kako "na papiru" doci do tacnog resenja za ovaj primer, kompajler ne smem da nosim na ispit :)?
Deo sa pronalazenjem GCD mi je jasan, posle je potrebno odraditi neki reverzan proces, ali taj deo nije bas najbolje objasnjen.

Re: Multiplikativni inverz - postupak 04.05.2009. u 23:08 · pre 213 meseci #4

Citat:

plotter: OK. Da li neko moze da napise kako "na papiru" doci do tacnog resenja za ovaj primer, kompajler ne smem da nosim na ispit :)?
Deo sa pronalazenjem GCD mi je jasan, posle je potrebno odraditi neki reverzan proces, ali taj deo nije bas najbolje objasnjen.

$\input amstex \def\akko{\;\Longleftrightarrow\;} \def\pomod#1{\equiv\limits_{#1}} $$\aligned 50\,a^{-1}\pomod{137}1&\akko 50\,a^{-1}=137\,k+1=100\,k+37\,k+1\akko\cr \akko 37\,k+1\pomod{50}0&\akko 37\,k+1=50\,\mu=37\,\mu+13\,\mu\akko\cr \akko 13\,\mu-1\pomod{37}0&\akko 13\,\mu-1=37\,\nu=26\,\nu+11\,\nu\akko\cr \akko 11\,\nu+1\pomod{13}0&\akko 11\,\nu+1=13\,\rho=11\,\rho+2\,\rho\akko\cr \akko 2\,\rho-1\pomod{11}0&\akko 2\,\rho-1=11\,\tau=10\,\tau+\tau\akko\cr \akko \tau+1\pomod{2}0&\akko \tau=2\,\theta-1\akko 2\,\rho-1=22\,\theta-11\akko\cr \akko \rho=11\,\theta-5&\akko 11\,\nu+1=11\cdot13\,\theta-65\akko\nu=13\,\theta-6\akko\cr \akko 13\,\mu-1=37\cdot13\theta-222&\akko\mu=37\,\theta-17\akko 37\,k+1=50\cdot37\,\theta-850\akko\cr \akko k=50\,\theta-23&\akko 50\,a^{-1}-1=137\cdot50\,\theta-3151\akko\fbox{$a^{-1}=137\,\theta-63$} \endaligned$$$

Dakle, sva celobrojna rešenja su oblika $\hbox{$\Bigl\{137\,\theta-63\Bigm|\theta\in{\bold Z}\Bigr\}$}$ , pa se za, recimo, $\hbox{$\theta=1$}$ lako dobija $\hbox{$a^{-1}=137-63=74$}$ . Inače, i $\hbox{$-63$}$ se smatra inverzom od $\hbox{$50$}$ , jer je $\hbox{$50\cdot(-63)=-3150=-3014-136\equiv\limits_{137}-136$}$ , pa je $\hbox{$-136=137\,k+1$}$ za $\hbox{$k=-1$}$ , i na kraju $\hbox{$-136\equiv_{137}1$}$ .

Re: Multiplikativni inverz - postupak 31.05.2009. u 16:05 · pre 212 meseci #5

Malo kasnim sa odgovorom ali ne zameri, hvala, ovo je bilo od velike pomoci.
Pozdrav

Re: Multiplikativni inverz - postupak 31.05.2009. u 22:25 · pre 212 meseci #6

Nema problema, zašto bih zamerio?

I ja sam razbijao glavu sa ovim dok nisam provalio. Niko od profesora i asistenata nije hteo (ili nije umeo) da mi ovo lepo, natenane, objasni.

Kao što rekoh, sindrom „ispod časti“ na delu.

Forum kao aplikacija na telefonu

Srodne teme