Matte Diskret - De hela talen
Största gemensamma delare
Beräkna största gemensamma delaren med Euklides algoritm
Den största gemensamma delaren (SGD) är av intresse för oss när vi t.ex. ska förkorta bråk då man måste hitta gemensamma faktorer för både täljare och nämnare. Med hjälp av Euklides algoritm kan vi bestämma den största gemensamma delaren till två tal. Algoritmen utgörs av en serie heltalsdivisioner som fortsätter fram tills dess att vi får en rest som är lika med noll.
Låt säga att vi ska bestämma största gemensamma delaren till talen 14 884 och 728, detta skrivs då som SGD(14 884, 728) och vi beräknar det genom att ställa upp talen enligt följande:
Först delar vi 14 884 med 728:
Eftersom serien utgörs av heltalsdivisioner så kommer vi att skriva då 20 är närmaste heltal. Om vi multiplicerar 728 med 20 får vi 14 560. Det fattas alltså 324 upp till 14 884. 324 blir divisionens rest.
Uppställningen blir således:
Divisionen av 14 884 har alltså gett kvoten 20 med resten 324. Det tal som vi använder för att dela med kallas divisor. I divisionen ovan är det 728 som är divisorn. Det tal som delas med divisorn kallas dividend, ovan är detta 14 884. I divisionsseriens fortsättning kommer divisorn och dividend att hela tiden ändras eftersom:
- divisorn är resten från föregående division
- dividend är divisorn från föregående division
Vi fortsätter:
| Nästa steg är att 728 blir den nya dividenden och resten 324 blir den nya divisorn. Vi slår in 728/324 på grafräknaren och får ca 2,2. Kvoten blir allstå heltalet 2. För att få ut resten skriver vi in . Resten blir 80. |
|
| Här upprepar vi samma som ovan. 324 blir den som ska delas med resten från föregående uppställning dvs. 80. Vi får heltalet 4 och beräknar därefter resten: |
|
| Återigen gör vi samma sak. Divisorn 80 från föregående tal delas med resten (4) från föregående tal. Divisionen går jämnt ut, vi får ett heltal, 20, och ingen rest. Här slutar alltså algoritmen. |
Vilken är det nu då som är den största gemensamma delaren för talen 14 884 och 728? Jo, det är den sista icke försvinnanden resten dvs. den sista resten som inte är 0. Vi tittar alltså på den näst sista resten som är talet 4. Talet 4 är alltså den största gemensamma delaren till talet 14 884 och 728.
Bestäm största gemensamma delaren till talen 5 018 och 3 242.
Vi börjar med att dela det större talet med det mindre talet:
Då våra divisioner endast ska ha heltalskvoter så blir kvoten 1. Notera att det inte handlar om avrundning till närmsta heltal, isf hade vi skrivit 2 istället. 2 gånger 3 242 blir ju mer än 5018, så därför måste vi avrunda nedåt.
Nu ska vi ta reda på hur mycket rest det blir:
Första uppställningen blir således:
| Precis som jag beskrev ovan så tar vi nu divisorn i föregående tal (3 242) och delar den med resten i föregående tal (1 776). Det blir ca 1,8 alltså är heltalskvoten återigen 1. Beräkna sedan resten genom att knappa in på grafräknaren. |
|
| Här upprepar vi samma som ovan. 1776 blir den som ska delas med resten från föregående uppställning dvs. 1466. Vi får heltalet 1 och beräknar därefter resten: |
|
| Återigen gör vi samma sak. Divisorn 1466 från föregående tal delas med resten (310) från föregående tal. Heltalskvoten blir 4 och resten blir |
|
| Divisorn 310 från föregående tal delas med resten (226) från föregående tal. Heltalskvoten blir 1 och resten blir |
|
| Divisorn 226 från föregående tal delas med resten (84) från föregående tal. Heltalskvoten blir 2 och resten blir |
|
| Divisorn 84 från föregående tal delas med resten (58) från föregående tal. Heltalskvoten blir 1 och resten blir |
|
| Divisorn 58 från föregående tal delas med resten (26) från föregående tal. Heltalskvoten blir 2 och resten blir |
|
| Divisorn 26 från föregående tal delas med resten (6) från föregående tal. Heltalskvoten blir 4 och resten blir |
|
| Divisorn 6 från föregående tal delas med resten (2) från föregående tal. Heltalskvoten blir 3 och resten blir . Divisionen går jämnt ut, vi får ett heltal, 3, och ingen rest. Här slutar alltså algoritmen. |
Vi kan alltså konstatera att den sista icke försvinnande resten är 2.
Svar: SGD(5 018, 3 242) = 2
Bestämma SGD med grafräknaren
Denna övning finner du under grafräknarsektionen. För att läsa vidare om hur man gör, klicka här.