Undirstöðusetning reikningslistarinnar

Úr Wikipediu, frjálsa alfræðiritinu
Stökkva á: flakk, leita

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]

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

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ð p_1, p_2, \dots, p_{s-1}, p_sséu frumtölursvo margfeldi þeirra sé n = p_1p_2 \dots p_{s-1}p_sþar sem smá vera 1svo n=2. (a) Sýnum fyrst að rita megi n sem margfeldi frumtalna: Látum F(n)vera fullyrðingunaner 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 = p1· ··· ·prog v = pr+1· ··· ·ps. Þá er n + 1 = k·j = pr· ··· ·psog þ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ð 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:

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

p1 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 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) n-m=v_1 \cdot  \cdot\cdot\cdot  \cdot v_t \cdot q_1 \cdot  \cdot\cdot\cdot  \cdot q_s

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]

Heimildir[breyta]

  1. 1,0 1,1 Undirstöðusetning reikningslistarinnar á Hugtakasafni — Verkefni á vegum ÍSF
  2. 2,0 2,1 2,2 fundamental theorem of arithmetic á Stærðfræðiorðasafninu
  3. 3,0 3,1 3,2 fundamental theorem of arithmetic á 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.