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 `* /