Tallteoretiske funksjoner

Dette innlegget har allerede blitt vist 1792 ganger!

Kort forklart er en tallteoretisk funksjon en funksjon som ser på egenskapene til input. For å sette opp formlene under definerer vi n = a1k1*a2k2*…*arkr

Τ (Tau): T(n) er antall positive divisorer d til n sik at 0 < d ≤ n.
Eksempel: 12 har de positive divisorene 1,2,3,4,6,12.
Vi kan regne ut T(n) ved å multiplisere sammen summen av hver koefesient og 1. (Π(ki+1))

σ (Sigma): σ(n) er summen av de positive divisorene til n
Eksempel: 12 har de positive divisorene 1,2,3,4,6,12. Summen av disse er 28 – σ(12) = 28
Vi kan regne ut σ(n) ved å multiplisere sammen følgende uttrykk (piki+1 – 1)/(pi-1) for alle i fra 0 til r.

φ (Phi): φ(n) er antallet naturlige tall som er relativt primiske til n og ikke større enn n
Eksempel: 1,5,7,11 er relativt primiske til 12, φ(12) = 4.
Generelt kan vi regne ut phi ved å multiplisere følgende uttrykk (piki – piki-1) for alle i fra 0 til r.
Spessielt, når det gjelder primtall vil φ(p) = p-1

Disse funksjonene er multiplikative. Det vil si at de σ(nm) = σ(n) * σ(m) dersom m og n er relativt primiske (gcd(n,m) = 1)

I tillegg har vi litt ekstra informasjon rundt φ funksjonen.

Teorem: La n være et naturlig tall, da er summen av antall relativit primiske tall til hver divisor av n lik n (n = Σφ(d) for alle d ∈ n slik at d n)

Teorem: La n være > 1, summen av alle tallene som er relativt primiske til n og mindre enn n = ½φ(n)*n