Undirstöðusetning reikningslistarinnar

Undirstöðusetning reikningslistarinnar, grunnsetning reikningslistarinnar eða frumþáttunarsetning er setning í stærðfræði sem er mikið hagnýtt í talnafræði. Setningin segir að rita megi allar náttúrulegar tölur sem eru stærri en einn sem margfeldi frumtalna á nákvæmlega einn hátt. Að rita tölu sem margfeldi frumtalna nefnist frumþáttun.

Sönnun

Sönnun að hætti Ernst Zermelo

Hverja náttúrlega tölu n stærri en 1 má rita sem margfeldi frumtalna á einn og aðeins einn hátt (óháð röð). Snið:Sönnun

Það er gefið að $p_1,p_2,\dots ,p_{s-1},p_s$ séu frumtölur svo margfeldi þeirra sé $n=p_1{p}_2\dots p_{s-1}{p}_s$ þar sem $s$ má vera $1$ svo $n=2$.

(a) Sýnum fyrst að rita megi n sem margfeldi frumtalna: Látum F(n) vera fullyrðinguna „n er margfeldi frumtalna“. Þetta er augljóst fyrir F(2) því 2 er frumtala. Gerum ráð fyrir að F(k) sé rétt fyrir allar tölur k = 2, ..., n og sýnum að F(n+1) sé sönn. Ef n + 1 er frumtala er F(n+1) sönn fullyrðing, annars er n+1 margfeldi minni náttúrlegra talna sem við getum kallað u og v. Þá er 2 ≤ u ≤n og 2 ≤ v ≤n. Samkvæmt þrepunarforsendu eru bæði u og v margfeldi frumtalna. Ritum þá u = p₁· ··· ·p_r og v = p_r+1· ··· ·p_s. Þá er n + 1 = k·j = p_r· ··· ·p_s og því er n + 1 margfeldi frumtalna. Því er F(n+1) sönn fullyrðing og eins og átti að sýna er hægt að rita n sem margfeldi frumtalna.

(b) Sýnum næst að ekki er hægt að rita n sem margfeldi frumtalna nema á einn máta óháð röð: Þetta er augljóst fyrir n = 2 þar sem 2 er stök frumtala. Gerum þá ráð fyrir að n sé stærri en 2 og að fullyrðingin sé rétt fyrir allar tölur minni en n. Gerum svo ráð fyrir að við höfum ritað n sem margfeldi frumtalna á tvo vegu:

$n=p_1\cdot \cdot \cdot \cdot \cdot p_r=q_1\cdot \cdot \cdot \cdot \cdot q_s$

Við getum þá raðað þáttunum þannig að p₁≤ ··· ≤ p_r og q₁≤ ··· ≤ q_s. Við fullyrðum að p₁= q₁ en gerum ráð fyrir til mótsagnar að svo sé ekki og að p₁ ≤ q₁. Þá er:

$m:=p_1\cdot q_2\cdot \cdot \cdot \cdot \cdot q_s<n$

p₁ gengur bæði upp í n og m og því einnig upp í n - m:

(I) $n-m=p_1\cdot u_1\cdot \cdot \cdot \cdot \cdot u_h$

Þar sem u₁· ··· ·u_h er margfeldi frumtalna. Einnig er n - m = (q₁ - p₁) · q₁· ··· ·q₁ og rita má (q₁ - p₁) = v₁· ··· ·v_t. En þar með er:

(II) $n-m=v_1\cdot \cdot \cdot \cdot \cdot v_t\cdot q_1\cdot \cdot \cdot \cdot \cdot q_s$

Talan p₁ gengur ekki upp í (q₁ - p₁) þar sem q₁ er frumtala. Þá er (I) og (II) tveir mismunandi rithættir á n - m sem er í mótsögn við þrepunarforsendu. Þar með er p₁ = q₁ og einnig r=s fyrir p₁· ··· ·p_r = q₂· ··· ·q_sog p_k = q_k fyrir k = 2, ..., r. Snið:QED

Tengt efni

• Fullstytt brot
• Frumþáttun