Snart eksamen i matematikk. Greier å finne SFF ved hjelp av Euklids algoritme, men syns det er vanskelig å forklare på en god måte hvorfor den virker. Noen som kan hjelpe meg ?
Hvorfor virker Euklids algortime?
Moderators: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
-
Gjest123321
Heisann!
Snart eksamen i matematikk. Greier å finne SFF ved hjelp av Euklids algoritme, men syns det er vanskelig å forklare på en god måte hvorfor den virker. Noen som kan hjelpe meg ?
Snart eksamen i matematikk. Greier å finne SFF ved hjelp av Euklids algoritme, men syns det er vanskelig å forklare på en god måte hvorfor den virker. Noen som kan hjelpe meg ?
-
repsils
For å finne største felles faktor, er det å finne gcd (greatest common divisor), største tall to tall deles på.
Så vi har to tall og skal finne største felles faktor. Tar det største tallet og setter på venstre siden og sjekker så kvar mange ganger det andre tallet går opp i det fyrste. Dette runder vi nedover til helltall og skriver resten på... altså
a_1 = a_2 + rest
Så tall 679 og 896 gir
896 = 679 * 1 + 217
Etter dette tar vi det tallet etter "=" og setter på venstre siden, og sjekker så kvar mange ganger resten går opp i dette talet. Så vi får:
679 = 217 * 3 + 28
forsetter slikt videre...
217 = 28 * 7 + 21
28 = 21 * 1 + 7
21 = 7 * 3 + 0
nå har vi komt til rest = 0, og da har vi at den største felles faktoren var resten før vi fekk null. Altså 7.
Største felles faktor av 896 og 679 = gcd (896,679) = 7
Er vertfal slik den funger. Håper dette hjelper deg litt.
Så vi har to tall og skal finne største felles faktor. Tar det største tallet og setter på venstre siden og sjekker så kvar mange ganger det andre tallet går opp i det fyrste. Dette runder vi nedover til helltall og skriver resten på... altså
a_1 = a_2 + rest
Så tall 679 og 896 gir
896 = 679 * 1 + 217
Etter dette tar vi det tallet etter "=" og setter på venstre siden, og sjekker så kvar mange ganger resten går opp i dette talet. Så vi får:
679 = 217 * 3 + 28
forsetter slikt videre...
217 = 28 * 7 + 21
28 = 21 * 1 + 7
21 = 7 * 3 + 0
nå har vi komt til rest = 0, og da har vi at den største felles faktoren var resten før vi fekk null. Altså 7.
Største felles faktor av 896 og 679 = gcd (896,679) = 7
Er vertfal slik den funger. Håper dette hjelper deg litt.
-
Gjest23423
Tusen takk. Men problemet er ikke at jeg ikke greier å bruke den. Men sliter med å begrunne på en god måte hvorfor den virker?repsils wrote:For å finne største felles faktor, er det å finne gcd (greatest common divisor), største tall to tall deles på.
Så vi har to tall og skal finne største felles faktor. Tar det største tallet og setter på venstre siden og sjekker så kvar mange ganger det andre tallet går opp i det fyrste. Dette runder vi nedover til helltall og skriver resten på... altså
a_1 = a_2 + rest
Så tall 679 og 896 gir
896 = 679 * 1 + 217
Etter dette tar vi det tallet etter "=" og setter på venstre siden, og sjekker så kvar mange ganger resten går opp i dette talet. Så vi får:
679 = 217 * 3 + 28
forsetter slikt videre...
217 = 28 * 7 + 21
28 = 21 * 1 + 7
21 = 7 * 3 + 0
nå har vi komt til rest = 0, og da har vi at den største felles faktoren var resten før vi fekk null. Altså 7.
Største felles faktor av 896 og 679 = gcd (896,679) = 7
Er vertfal slik den funger. Håper dette hjelper deg litt.
-
repsils
ja, har aldri satt meg inn kvifor den funger :p. Nokon google søk vil nok gi svar, men hadde vore kjekt viss nokon andre i forumet kunne forklart det. Får håpe nokon andre ser det