Hoppa till innehållet

Matematik/Diskret matematik/Talteori

Från Wikibooks
Diskret matematik

Introduktion | Kombinatorik | Mängder | Logik (Satslogik/Predikatlogik) | Talteori
Formelsamling/Matematik | Matematikportalen





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 .

Möbius inversionformel

Definition: Låt och vara multiplikativa. .

Definition: Möbiusfunktionen definieras som .

Möbius inversionsformel: .