Matematik/Diskret Matematik/Talteori

Från Wikibooks

Hoppa till: navigering, sök
Diskret Matematik

Introduktion | Kombinatorik | Mängder | Satslogik | Predikatlogik | Talteori
Formelsamling/Matematik | Matematik alla kurser





Talteori

Definition: Ett heltal a säges vara delbart med ett heltal b om det existerar ett tal k s.a. a = b \cdot k (vilket kompakt kan skrivas \exists k : a = b \cdot k). Detta skrives a | b. a delar b. b är en delare till a.

Definition: En äkta delare till ett tal a är ett positivt heltal d \notin \{1, p\} : d | a.

Notation: Den största gemensamma delaren till a och b betecknas (a,b).

Kongruenser

Definition: a \equiv b \pmod{n} definieras som n | (b − a).

Sats: Om a \equiv b \pmod{n}, c heltal, så

a + c \equiv b + c \pmod{n},
ac \equiv bc \pmod{n}.


Eulers \varphi-funktion

Definition: \varphi(n) är antalet positiva tal d \leq n : (d, n) = 1.

Definition: En funktion f som uppfyller (m, n) = 1 \Rightarrow f(mn)=f(m)f(n) säges vara multiplikativ.

Sats: \varphi är multiplikativ. Bevis: Bland talen 1, \ldots, m finns exakt \varphi(m) tal relativt prima till m, enligt definitionen av \varphi. Bland talen 1 + km, \ldots, m + km finns lika många, dvs \varphi(m), tal relativt prima till m, eftersom (m,t) = (m,t + km). Det följer att antalet tal relativt prima till m bland talen 1, \ldots, m, m+1, \ldots 2m, \ldots, (n-1)m + 1, \ldots, mn, dvs talen mindre än m, är m \cdot n.

Sats: p primtal. \varphi(p^\alpha) = p^\alpha - p^{\alpha - 1}. Bevis: De enda positiva talen mindre än pα som ej är relativt prima med pα är multipler kp av p. k kan anta pα − 1 olika värden då 0 < kp \leq p^\alpha. Det följer att \varphi(p^\alpha) = p^\alpha - p^{\alpha - 1}.

\varphi(n) = \varphi(p_0^{\alpha_0}\ldots p_n^{\alpha_n}) = \varphi(p_0^{\alpha_0})\ldots\varphi(p_n^{\alpha_n}) = p_0^{\alpha_0}\left(1 - {1\over p_0}\right) \ldots p_n^{\alpha_n}\left(1 - {1 \over p_n} \right) = p_0^{\alpha_0} \ldots p_n^{\alpha_n} \left(1 - {1\over p_0}\right) \ldots \left(1 - {1 \over p_n} \right) = n\prod _{i = 0} ^n \left(1 - {1\over p_i}\right).

Exempel på multiplikativa funktioner

τ(n) - antalet positiva delare till n. σ(n) - summan av de positiva delarna till n.

Möbius inversionformel

Definition: Låt f och g vara multiplikativa. f * g := \sum _{d|n} f(d)f\left({n \over d}\right).

Definition: Möbiusfunktionen definieras som \mu := \left\{ \begin{array}{c} 1 \Leftarrow n = 1 \\ (-1)^n \Leftarrow n = p_1\ldots p_n \\ 0 annars \end{array}\right..

Möbius inversionsformel: F = f * 1 \Rightarrow f = F * \mu.

Hämtad från "http://sv.wikibooks.org/wiki/Matematik/Diskret_Matematik/Talteori"