Stærsti samdeilir

Stærsti samdeildirGreatest common divisor á nyk.is eða stærsti sameiginlegi deilir (skammstafað sem ssd) tveggja náttúrulegra talna er stærsta tala sem gengur upp í báðar tölurnar. Einfaldast er að finna stæsta samdeili með því að frumþátta báðar tölurnar, finna hvaða frumþættir eru sameiginlegir báðum tölunum og margfalda þá saman. Þá er stærsti samdeilir fundinn. Stærsti samdeilir náttúrulegu talnanna  og  er táknaður með , og ef stærsti samdeilir þeirra er  þ.e.  teljast tölurnar ósamþátta og eiga þær þá enga sameiginlega frumþætti.

 Dæmi 
Finnum .

Byrjum á að frumþátta:  og . 

Sameiginlegu frumþættirnir eru  og  en .

Þá er 

Þær tölur og aðeins þær tölur sem ganga upp í  ganga upp í báðar tölurnar  og . 

Minnsta samfeldi tveggja náttúrulegra talna er minnsta talan sem báðar tölurnar ganga upp í. Minnsta samfeldi náttúrulegu talnanna a og b er táknað með  Einfalt er að finna minnsta samfeldi. Tölurnar tvær eru raktar í frumþætti. Þá er búin til ný tala sem er margfeldi allra frumþátta úr tölunum tveimur, þó þannig að ef sami þáttur kemur fyrir í báðum tölum kemur hann aðeins einu sinni fyrir í nýju tölunni. Nýja talan er minnsta samfeldið.

Ef  og  eru náttúrulegar tölur þá gildir að margfeldi minnsta samfeldis og stærsta samdeilis er jafnt margfeldi  og , þ.e. .

Þetta verður augljóst þegar haft er í huga hvernig stærsti samdeilir og minnsta samfeldi eru búin til úr frumþáttum talnanna  og . Í  eru allir þættir talnanna tveggja, en þeir sem eru sameiginlegir koma bara einu sinni fyrir. Í  eru sameiginlegu frumþættirnir og margfeldi  og  inniheldur því alla frumþætti talnanna  og  og tvo af hverjum sameiginlegum þætti. Margfeldi  og  er því margfeldi allra frumþátta talnanna tveggja sem er það sama og margfeldi talnanna sjálfra.

 Heimild 
 Stærðfræðivefur Kennaraháskóla Íslands, Guðmundur Birgisson, júní 2001

 Tilvísanir 

Flokkur:Stærðfræði