stæ.is

Fyrir tvær heilar tölur $n$ og $m$ er náttúruleg tala $k$ sögð vera samfeldi talnanna $n$ og $m$ ef þær ganga báðar upp í $k$. Minnsta náttúrulega talan sem tvær heiltölur $n$ og $m$ ganga upp í er þá kölluð minnsta samfeldi talnanna $n$ og $m$ og er hún táknuð með $msf(n,m)$.

Til þess að finna minnsta samfeldi talna $n$ og $m$ er byrjað á að frumþátta þær.

Við notum óbeina sönnun, þ.e. gerum ráð fyrir að aðeins séu til endanlega margar frumtölur og leiðum það til mótsagnar.

Gerum nú ráð fyrir að til séu endanlega margar frumtölur $p_{1}, \ldots, p_{n}$ og látum $p$ vera margfeldi þeirra allra að einum viðbættum, þ.e. $p = p_{1} \cdot p_{2} \cdot \ldots$ $\cdot p_{n-1} \cdot p_{n} + 1$.

Undirstöðusetning reikningslistarinnar segir að sérhverja náttúrulega tölu $n$ megi skrifa á nákvæmlega einn hátt sem margfeldi af frumtölum. Nánar tiltekið gildir fyrir sérhverja náttúrulega tölu $n$ að til eru ótvírætt ákvarðaðar frumtölur $p_{1}, \ldots ,p_{k}$ og náttúrulegar tölur $a_{1}, \ldots ,a_{k}$ þannig að:

\[n = {p_{1}}^{a_{1}} \cdot {p_{2}}^{a_{2}} \cdot \ldots \cdot {p_{k-1}}^{a_{k-1}} \cdot {p_{k}}^{a_{k}} \quad \text{þar sem $p_{i} \lt p_{j}$ þegar $i \lt j$}.