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: .