Matematik
Euklid
Er der nogen der kan hjælpe mig lidt??
Vi har fået givet følgende metode:
sfd(13,8) = 1
Vi laver divison med rest nogle gange. først deler vi 13 med 8 og får:
13 = 1*8+5
sfd(13,8) = sfd(8,5)
Vi gentager
8 = 1*5+3
sfd(8,5) = sfd(5,3)
vi forstætter og finder:
5=1*3+2
3=1*2+1
2=2*1+0
Kan man bruge denne metode til at beregne sfd(m,n) for vilkårlige hele tal m og n?
Hvorfor stopper metoden efter endeligt mange skridt?
Og hvordan gør man rede for at den sidste rest forskellige fra 0, er den største fælles divisor?
Svar #1
10. maj 2010 af peter lind
Man kan bruge metoden generelt. En udvidet version er faktisk særdeles vigtig for RSA kodesystemet.
Hvis du bliver ved med at dele med resten, vil du uundgåelig på et eller andet tidspunkt få resten 0. Du har jo en strengt aftagende følge af rester og senest når resten er 1 vil tallet gå op. Det tal der til sidst går op i den foregående rest og altså har resten 0 er den fælles divisor.
Skriv et svar til: Euklid
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.