Matematik/Diskret matematik/Talteori

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