Talteori
Definition: Ett heltal
säges vara delbart med ett heltal
om det existerar ett tal
s.a.
(vilket kompakt kan skrivas
). Detta skrives
. a delar b. b är en delare till a.
Definition: En äkta delare till ett tal
är ett positivt heltal
.
Notation: Den största gemensamma delaren till
och
betecknas
.
Kongruenser
Definition:
definieras som
.
Sats: Om
,
heltal, så
,
.
Eulers
-funktion
Definition:
är antalet positiva tal
.
Definition: En funktion
som uppfyller
säges vara multiplikativ.
Sats:
är multiplikativ.
Bevis: Bland talen
finns exakt
tal relativt prima till
, enligt definitionen av
.
Bland talen
finns lika många, dvs
, tal relativt prima till
, eftersom
. Det följer att antalet tal relativt prima till
bland talen
, dvs talen mindre än
, är
.
Sats:
primtal.
. Bevis: De enda positiva talen mindre än
som ej är relativt prima med
är multipler
av
.
kan anta
olika värden då
. Det följer att
.
.
Exempel på multiplikativa funktioner
- antalet positiva delare till
.
- summan av de positiva delarna till
.
Definition: Låt
och
vara multiplikativa.
.
Definition: Möbiusfunktionen definieras som
.
Möbius inversionsformel:
.