Primtallsfaktorisering

Aritmetikkens fundamentalsetning

Ethvert tall større enn en kan skrives som et entydig produkt av primtall\footnote{Rekkefølgen til tallene har ingen betydning, slik at faktoriseringer med de samme faktorene i ulik rekkefølge er entydig}

Kan to primtallsfaktoriseringer av samme tall kan være ulike?

Anta at vi har to primtallsfaktoriseringer slik at

    \begin{align*} ab\cdot \ldots \cdot c = pq\cdot \ldots \cdot r \end{align*}

Da må

    \begin{align*} a|pq\cdot \ldots \cdot r \end{align*}

og a er lik en av primfaktorene p,q,\ldots, r.

Anta at a = p. Vi forkorter med a og p og fortsetter på samme måte med neste primfaktor b.

Til slutt ender vi med bare 1 på en av sidene i likningen. Da kan det heller ikke stå igjen primfaktorer på den andre siden, siden de i så fall måtte være faktorer i 1.

Faktoriseringene er derfor like.

Når faktorer og produkt går opp i samme tall

Dersom to innbyrdes primiske tall går opp i et tredje tall, så vil også produktet av de to tallene gå opp i det tredje tallet.

delbarhet

Faktorisering av a^n-1

år a>1 og k og n er positive tall, gjelder følgende:
Hvis k går opp i n, vil (a^k-1) gå opp i (a^n-1).

Faktoriseringen er

    \begin{align*} (a^n-1)=(a^k-1)(a^{n-k}+a^{n-2k}+\ldots+a^k+1) \end{align*}

Eksempel

Finn primtallsfaktorene til 7^{12} -1
Faktoriser