Undirstöðusetning reikningslistarinnar

Undirstöðusetning reikningslistarinnar,^[1]^[2]^[3] grunnsetning reikningslistarinnar^[2]^[3] eða frumþáttunarsetning^[2]^[3] 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.^[1] 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öð).

Þ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.

Sönnun:

Quod erat demonstrandum

Setningar, frumsendur og hugtök mikilvæg fyrir þessa sönnun: Stærðfræðileg þrepun, óbein sönnun, frumtölur

Tengt efni

Heimildir

↑ ^1,0 ^1,1 Undirstöðusetning reikningslistarinnar^{[óvirkur tengill]} á Hugtakasafni — Verkefni á vegum ÍSF
↑ ^2,0 ^2,1 ^2,2 fundamental theorem of arithmetic Geymt 5 mars 2016 í Wayback Machine á Stærðfræðiorðasafninu
↑ ^3,0 ^3,1 ^3,2 fundamental theorem of arithmetic^{[óvirkur tengill]} á Orðasafni íslenska stærðfræðifélagsins

Þessi stærðfræðigrein er stubbur. Þú getur hjálpað til með því að bæta við greinina.

[nykur-1] 1,0 ^1,1 Undirstöðusetning reikningslistarinnar^{[óvirkur tengill]} á Hugtakasafni — Verkefni á vegum ÍSF

[staerd-2] 2,0 ^2,1 ^2,2 fundamental theorem of arithmetic Geymt 5 mars 2016 í Wayback Machine á Stærðfræðiorðasafninu

[ordaskra-3] 3,0 ^3,1 ^3,2 fundamental theorem of arithmetic^{[óvirkur tengill]} á Orðasafni íslenska stærðfræðifélagsins

[1]

[2]

[3]