Posted By: medvidek (Nezapomen na radost) on 'CZscience'
Title:     Re: Modularni aritmetika - pokracovani
Date:      Tue Apr 25 17:37:04 2000

Protoze jsem se upsal, davam sem opravenou verzi. A mirne rozsirenou, bo ted 
mam vic casu. 

pokud nsd(a,n) = c, pak existuji cela cisla b,y takova, ze plati c=b*a+y*n.
Ta veta dava navod, jak je spocitat. Je to easy, ale nechce se mi to obecne 
psat, uz jsem to sem asi pred trema lety psal a zabralo mi to hodinu.

To b v te rovnici c=b*a+y*n je presne to b, ktere hleda snake. Proc?

Uvazime jeste jednou rovnici c=x*a+y*n. Obe strany vezmeme modulo n.
Cili clen s n na prave strane vypadne a dostaneme. c (mod n) = b*a (mod n).
Cislo c je mensi jak n (protoze je to nsd (a,n), takze na leve strane muzeme
mod n klidne vynechat. Dopstaneme c = b*a mod n. No a z predpokladu mame
c = 1.

Snad je to ted jasnejsi.

                 medvidek
                                                            .,.
"Co kdybychom jednou na ukazku odhalili svoji tvar,     /~ (   )
 odlozili masku vedle na polstar.                    .*~ o       )
 Kolik by tu zbylo z nas vysusenych mumii?"          o           )
             Slavek Janousek                         `*         /