Aritmetikkens fundamentalteorem

[sEirik]

Jeg skal bevise aritmetikkens fundamentalteorem etter modellen i boka "Kalkulus" av Lindstrøm, altså oppgave 14 og 15 side 33. Det første beviset er greit, og det andre er nesten greit.

a) Alle naturlige tall større enn 1 kan skrives som et produkt av primtall.
(1) Vi antar at det finnes tall større enn 1 som ikke kan skrives som et produkt av primtall.
(2) Vi lar n være det minste slike tallet.
(3) Vi vet at n enten er primtall, eller ikke primtall. Men hvis n er et primtall, kan det skrives som produkt av primtall, nemlig n = n, og dette motsier (2). Derfor kan n ikke skrives som et primtall, og kan derfor deles på to naturlige tall a og b, slik at n = ab.
(4) Da er både a og b er mindre enn n.
(5) Siden n er det minste tallet som ikke kan skrives som produkt av primtall, må både a og b kunne skrives som produkt av primtall. Men siden n = ab, må n også kunne skrives som et produkt av primtall, dette motsier (2).
(6) Siden (5) motsier (2), og vi bare har gjort én antakelse (1), må (1) være feil.
(7) Altså kan alle naturlige tall større enn 1 kunne skrives som et produkt av primtall, og beviset er ferdig.

b) Primtallsfaktoriseringen av et naturlig tall større enn 1 er unik. (Det eneste som kan variere, er rekkefølgen av faktorene.)
(1) Vi antar at det finnes tall større enn 1 med mer enn én primtallsfaktorisering.
(2) Vi lar n være det minste slike tallet.
(3) Vi vet at [n]n[/i] ikke kan være et primtall, for da må n skrives som n = n, og har dermed kun én primtallsfaktorisering. Altså må n v ære kompositt.
(4) Vi lar n = p[sub]1[/sub]p[sub]2[/sub] ... p[sub]m[/sub] og n = q[sub]1[/sub]q[sub]2[/sub] ... q[sub]n[/sub] være to primtallsfaktoriseringer av n. Vi antar, uten tap av generalitet, at faktorene er ordnet i stigende rekkefølge.
(5) Anta at en av p-ene og en av q-ene er lik. Vi kaller denne faktoren a. Da må n/a være mindre enn n, og derfor ha unik primtallsfaktorisering. Men da kan n skrives som n = n * a/n, og da har n unik faktorisering, dette motsier (2). Derfor må antakelsen vi gjorde være ovenfor være feil, og det betyr at alle p-ene må være forskjellig fra alle q-ene.
(6) Sett b = p[sub]2[/sub]p[sub]3[/sub] ... p[sub]m[/sub]. Anta at q[sub]1[/sub] kan dele b. Men da har b to primtallsfaktoriseringer:
b = p[sub]2[/sub]p[sub]3[/sub] ... p[sub]m[/sub] og b = q[sub]1[/sub] * ( b / q[sub]1[/sub] ). Men dette er umulig, siden b < n, og n er det minste tallet med to primtallsfaktoriseringer. Derfor må antakelsen være feil, det betyr at q[sub]1[/sub] ikke deler b.
(7) Det skal nå vises at n - p[sub]1[/sub]q[sub]1[/sub] > 1. Men hvordan gjør vi det?
(8) Vi ser at n - p[sub]1[/sub]q[sub]1[/sub] har to primtallsfaktoriseringer: p[sub]1[/sub](p[sub]2[/sub]p[sub]3[/sub] ... p[sub]m[/sub] - q[sub]1[/sub]) og q[sub]1[/sub](q[sub]2[/sub]q[sub]3[/sub] ... q[sub]n[/sub] - p[sub]1[/sub]). Men dette kan ikke stemme, for n - p[sub]1[/sub]q[sub]1[/sub] < n, og n er det minste tallet med to primtallsfaktoriseringer. Vi har en selvmotsigelse, og vi er ferdig.

Men så var det å vise (7), da. Ser for meg at det egentlig er trivielt, men den mentale rullegardina er dratt ned ...

[Solar Plexsus]

Bevis for punkt 7: For det første er [tex]m>1[/tex] og [tex]n>1[/tex] ettersom [tex]n[/tex] ikke er et primtall. Dette i kombinasjon med at [tex]p_2 \,>\, p_1[/tex] og [tex]q_2 \,>\, q_1[/tex] innebærer at

[tex]n^2 \;>\; (p_1p_2) \cdot (q_1q_2) \;>\; (p_1q_1)^2, [/tex]

dvs. at

[tex](1) \;\;\; n \,>\, p_1q_1[/tex].

Hvis [tex]n \:-\: p_1q_1 \:=\: 1[/tex], må [tex]p_1|1[/tex] i.o.m. at [tex]p_1|n[/tex]. Denne motsigelsen og ulikheten (1) gir

[tex]n \:-\: p_1q_1 \;>\; 1.\;\;\;[/tex] q.e.d.

[Eksplisitt]

Hvordan vet man at p[sub]1[/sub](p[sub]2[/sub]p[sub]3[/sub] … p[sub]m[/sub] - q[sub]1[/sub]) og q[sub]1[/sub](q[sub]2[/sub]q[sub]3[/sub] … q[sub]n[/sub] - p[sub]1[/sub]) ikke kan faktoriseres på samme måte? Hvorfor kan ikke (p[sub]2[/sub]p[sub]3[/sub] … p[sub]m[/sub] - q[sub]1[/sub]) = q[sub]1[/sub]x og (q[sub]2[/sub]q[sub]3[/sub] … q[sub]n[/sub] - p[sub]1[/sub]) = p[sub]1[/sub]x?

[Eksplisitt]

Tror jeg løste det.

Dersom [tex]p_1(p_2p_3\dots p_m-q_1)[/tex] og [tex]q_1(q_2q_3\dots q_m-p_1)[/tex] kan faktoriseres på samme måte, så er

[tex]p_2\dots p_m-q_1=q_1x[/tex] og [tex]q_2q_3\dots q_m-p_1=p_1x[/tex]. Vi kan få et uttrykk for [tex]x=\frac{p_2\dots p_m}{q_1}-1[/tex], men siden [tex]x[/tex] må være et helt tall og [tex]q_1[/tex] ikke deler [tex]p_2p_3\dots p_m[/tex] så finnes ingen slik [tex]x[/tex]. Altså har [tex]N-p_1q_1[/tex] to ulike primtallsfaktoriseringer.

Kom gjerne med tilbakemeldinger på om det ser greit ut.