wie d in " x*d==1 mod c "ermitteln mit hilfe vom euklidischen algorithmus?(x und c sind fest)
-
hi
wie kann ich da euklid benutzen?
== soll kongruent bedeuten
beispielsweise für x= 35 und c=72
oder wie bekommt man sonst ein passendes d raus(nicht probieren
danke + mfg
error
edit: hat sich erledigt ... hab's gefunden ...
-
Es gibt da einen schönen Satz, der besagt, daß man aus 2 Zahlen ihren ggT kombinieren kann:
Zu x,c gibt es also a,b so daß: x*a+c*b = ggT(x,c).
Der erweiterte euklidische Algorithmus (google/wikipedia-Suchwort!) kann Dir zu gegebenem x,c dieses a und b bestimmen. Da Deine Zahlen teilfremd sind ist der ggT 1 und es steht noch da, daß x*a+c*b = 1 ist.
mod c gerechnet also x*a = 1.MfG Jester