Matematik
Euclid's udvidede GCD formel
27. juni 2003 af
catch 22 (Slettet)
Hej alle!!
Jeg har et spørgsmål som er ved at drive mig til vandvid .... Jeg sidder i øjeblikket og leger med modulær aritmetik, og er kommet til Euclid's udvidede formel. Og her sidder jeg uhjælpeligt fast ....
Eksempel:
(X*3) mod 460 = 1 bliver til
X = 460/3 = -153 + 460 = 307
(307*3) mod 460 = 1 (det passer)
men følgende formel er:
(X*3) mod 35 = 1
X = 35/3 = 11.6 = -11 + 35 = 24
(24*3) mod 35 = 2
Så vidt jeg har læst mig til SKAL X og Y være prim-tal før euclids udvidede formel skal virke. Hvis jeg runder 11.6 op til 12 så bliver ligningen (23*3) mod 35 = 34 ??
Kan nogen give mig en forklaring på dette ?? Eventuelt give mig et udførligt eksempel på ligningen (X*3) mod 35 = 1.Jeg forstår åbenbart ikke Euclid's udvidede formel ;)
Jeg har et spørgsmål som er ved at drive mig til vandvid .... Jeg sidder i øjeblikket og leger med modulær aritmetik, og er kommet til Euclid's udvidede formel. Og her sidder jeg uhjælpeligt fast ....
Eksempel:
(X*3) mod 460 = 1 bliver til
X = 460/3 = -153 + 460 = 307
(307*3) mod 460 = 1 (det passer)
men følgende formel er:
(X*3) mod 35 = 1
X = 35/3 = 11.6 = -11 + 35 = 24
(24*3) mod 35 = 2
Så vidt jeg har læst mig til SKAL X og Y være prim-tal før euclids udvidede formel skal virke. Hvis jeg runder 11.6 op til 12 så bliver ligningen (23*3) mod 35 = 34 ??
Kan nogen give mig en forklaring på dette ?? Eventuelt give mig et udførligt eksempel på ligningen (X*3) mod 35 = 1.Jeg forstår åbenbart ikke Euclid's udvidede formel ;)
Svar #1
27. juni 2003 af 404error (Slettet)
Euklids udvidede algoritme anvendes til bestemmelse af største fælles divisor for to heltal a,b som linearkombination af disse tal. Hvad er det, du vil lave med ovenstående? Løser du lineære kongruenser eller..?
Skriv et svar til: Euclid's udvidede GCD formel
Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk?
Klik her for at oprette en bruger.