Skip to Content

Ef $n$ og $m$ eru tvær heilar tölur þá er náttúruleg tala $k$ sögð vera samdeilir $n$ og $m$ ef $k$ gengur upp í þeim báðum. Stærsta talan sem gengur upp í tveim tölum $n$ og $m$ er síðan sögð vera stærsti samdeilir talnanna og er hún táknuð með $ssd(n,m)$. Tvær tölur $n$ og $m$ eru sagðar vera ósamþátta ef $ssd(n,m) = 1$.

Til þess að finna stærsta samdeili talna $n$ og $m$ er byrjað á að frumþátta þær. Ef $p_{1},\ldots,p_{k}$ eru þeir frumþættir sem tilheyra bæði $n$ og $m$, og $a_{1},\ldots,a_{k}$ og $b_{1},\ldots,b_{k}$ eru margfeldni þeirra í $n$ og $m$, þá er stærsti samdeilir þeirra:

\[ssd(n,m) = {p_{1}}^{c_{1}} \cdot {p_{2}}^{c_{2}} \cdot \ldots \cdot {p_{k-1}}^{c_{k-1}} \cdot {p_{k}}^{c_{k}} \quad \text{þar sem $c_{i}$ er minni talan af $a_{i}$ og $b_{i}$}.\]

Dæmi:   Tölurnar 2250 og 525 frumþáttast sem $2250 = 2 \cdot 3^2 \cdot 5^3$ og $525 = 3 \cdot 5^2 \cdot 7$. Þar með er $ssd(2250,525) = 3 \cdot 5^2 = 75$.