Undirstöðusetning reikningslistarinnar

Undirstöðusetning reikningslistarinnar,Undirstöðusetning reikningslistarinnar á Hugtakasafni —
Verkefni á vegum ÍSFfundamental theorem of arithmetic  á Stærðfræðiorðasafninufundamental theorem of arithmetic á Orðasafni íslenska stærðfræðifélagsins 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öð).

Það er gefið að  séu frumtölur svo margfeldi þeirra sé  þar sem  má vera  svo .

(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 = p1· ··· ·pr og v = pr+1· ··· ·ps.  Þá er n + 1 = k·j = pr· ··· ·ps 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:

Við getum þá raðað þáttunum þannig að p1≤ ··· ≤ pr og q1≤ ··· ≤ qs.  Við fullyrðum að p1= q1 en gerum ráð fyrir til mótsagnar að svo sé ekki og að p1 ≤ q1.  Þá er:

p1 gengur bæði upp í n og m og því einnig upp í n - m:
(I) 
Þar sem u1· ··· ·uh er margfeldi frumtalna.  Einnig er n - m = (q1 - p1) · q1· ··· ·q1 og rita má (q1 - p1) = v1· ··· ·vt.  En þar með er:
(II) 
Talan p1 gengur ekki upp í (q1 - p1) þar sem q1 er frumtala.  Þá er (I) og (II) tveir mismunandi rithættir á n - m  sem er í mótsögn við þrepunarforsendu.  Þar með er p1 = q1 og einnig r=s fyrir  p1· ··· ·pr = q2· ··· ·qsog pk = qk fyrir k = 2, ..., r.

 Tengt efni 
 Fullstytt brot
 Frumþáttun

 Heimildir 

Flokkur:Talnafræði

de:Primfaktorzerlegung#Fundamentalsatz der Arithmetik