Undirstöðusetning reikningslistarinnar

Úr Wikipediu, frjálsa alfræðiritinu

Undirstöðusetning reikningslistarinnar er setning í stærðfræði sem er mikið hagnýtt í talnafræði. Hún segir að allar náttúrlegar tölur stærri en einn megi rita sem margfeldi frumtalna á einn veg. Að rita tölu sem margfeldi frumtalna nefnist frumþáttun.

[breyta] Sönnun

[breyta] 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öð).

Við táknum margfeldi frumtalna p₁, p₂, ..., p_sþannig að n = p₁· ··· ·p_sog leyfum að s = 1þannig að n getur til dæmis verið n = 2. (a) Sýnum fyrst að rita megi n sem margfeldi frumtalna: Látum F(n)vera fullyrðinguna „ner 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, ..., nog sýnum að F(n+1)sé sönn. Ef n + 1er frumtala er F(n+1)sönn fullyrðing, annars er n+1margfeldi minni náttúrlegra talna sem við getum kallað uog v. Þá er 2 ≤ u ≤nog 2 ≤ v ≤n. Samkvæmt þrepunarforsendu eru bæði uog vmargfeldi frumtalna. Ritum þá u = p₁· ··· ·p_rog v = p_r+1· ··· ·p_s. Þá er n + 1 = k·j = p_r· ··· ·p_sog því er n + 1margfeldi frumtalna. Því er F(n+1)sönn fullyrðing og eins og átti að sýna er hægt að rita nsem margfeldi frumtalna. (b) Sýnum næst að ekki er hægt að rita nsem 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ð nsé 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ð nsem 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.