Undirstöðusetning reikningslistarinnar

Úr Wikipediu, frjálsa alfræðiritinu

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[breyta | breyta frumkóða]

Sönnun að hætti Ernst Zermelo[breyta | breyta frumkóða]

Undirstöðusetning reikningslistarinnar

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ðingunan 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.

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[breyta | breyta frumkóða]

Heimildir[breyta | breyta frumkóða]

  1. 1,0 1,1 Undirstöðusetning reikningslistarinnar[óvirkur tengill] á Hugtakasafni — Verkefni á vegum ÍSF
  2. 2,0 2,1 2,2 fundamental theorem of arithmetic Geymt 5 mars 2016 í Wayback Machine á Stærðfræðiorðasafninu
  3. 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.