Föreläsningar i Talteori
1. Introduktion
2. Kongruensräkning
2.1. Delbarhet
2.1.1. Definition
- Heltal, delbarhet
- \({\mathbb{Z}}=\left\{{0,1,-1,2,-2,3,-3,\dots}\right\}\)
- \({\mathbb{N}}=\left\{{0,1,2,3,\dots}\right\}\)
- \({\mathbb{Z}_+}= \left\{{1,2,3,\dots}\right\}\)
Om inte annat sägs så \(a,b,c,x,y,r,s \in {\mathbb{Z}}\), men \(n,m \in {\mathbb{Z}_+}\).
\({a} \lvert {b}\) om finns \(c\) så att \(b=ac\).
\({3} \lvert {12}\) ty \(12=3*4\).
2.1.2. Elementary properties
- \({a} \lvert {0}\),
- \({0} \lvert {a} \quad \iff \quad a=0\),
- \({1} \lvert {a}\),
- \({a} \lvert {1} \quad \iff \quad a=\pm 1\),
- \({a} \lvert {b} \, \wedge \, {b} \lvert {a} \quad \iff \quad a = \pm b\)
- \({a} \lvert {b} \, \iff \, {-a} \lvert {b} \, \iff \, {a} \lvert {-b}\)
- \({a} \lvert {b} \wedge {a} \lvert {c} \quad \implies \quad {a} \lvert {(b+c)}\),
- \({a} \lvert {b} \implies \quad {a} \lvert {bc}\).
2.1.3. Partial order

Begränsad till \({\mathbb{Z}_+}\) så är delbarhet en partialordning, med ett unikt minimalt element 1.
2 Del av Hasse diagram
Id est,
- \({a} \lvert {a}\),
- \({a} \lvert {b} \, \wedge \, {b} \lvert {c} \quad \implies \quad {a} \lvert {c}\),
- \({a} \lvert {b} \, \wedge \, {b} \lvert {a} \quad \implies \quad a=b\).
2.1.4. Primtal
\(n \in {\mathbb{Z}_+}\) är ett primtal om
- \(n > 1\),
- \({m} \lvert {n} \, \implies \, m \in \left\{{1,n}\right\}\)
(positiva delare)
Primtalen börjar \[2,3,5,7,11,13,17,19,23,29,31,\dots\]
2.1.5. Divisionsalgoritmen
- Divisionsalgoritmen
\(a,b \in {\mathbb{Z}}\), \(b \neq 0\). Då finns unika \(k,r\), kvot och rest, så att
- \(a= kb + r\),
- \(0 \le r < \lvert b \rvert\).
\(-27 = (-6)*5 + 3\).
- Bevis, existens
Antag för enkelhets skull att \(a,b >0\). Fixera \(b\), induktion över \(a\), basfall \(a
- Bevis, unikhet
Om \[a=k_1b+r_1 =k_2b+r_2, \quad 0 \le r_1,r_2 < b\] så \[0= a-a = (k_1-k_2)b + r_1-r_2\] varför \[(k_1-k_2)b = r_2-r_1\] \(\lvert RHS \rvert < b\), så \(\lvert LHS \rvert < b\), alltså \(k_1=k_2\). Men då är \(r_1=r_2\).
\(a=23\),\(b=5\). \[\begin{aligned} 23 &= 5+ (23-5) = 5 + 18
&= 5+ 5 + (18-5) = 2*5+ 13
&= 2*5 + 5+ (13-5) = 3*5+ 8
&= 3*5 + 5+ (8-5) = 4*5+ 3\end{aligned}\] \(k=4\), \(r=3\).
2.1.6. Största gemensamma delare
- Definition
- Största gemensamma delare
\(a,b \in {\mathbb{Z}}\). Den största gemensamma delaren till \(a\) och \(b\), \(c=\gcd(a,b)\), definieras genom
- \({c} \lvert {a} \, \wedge \, {c} \lvert {b}\),
- If \({d} \lvert {a} \, \wedge \, {d} \lvert {b}\), then \(d \le c\).
Om vi håller oss till \({\mathbb{Z}_+}\) kan det sista villkoret ersättas med
- Om \({d} \lvert {a} \, \wedge \, {d} \lvert {b}\), så \({d} \lvert {c}\).
- Största gemensamma delare
- Bezout
- Bezouts sats
Låt \(d=\gcd(a,b)\). Då finns (ej unika) \(x,y \in {\mathbb{Z}}\) så att \[ax + by = d.\]
Proof. \(S=\left\{\,{ax+by}\,\vrule\,{x,y \in {\mathbb{Z}}}\,\right\}\), \(d= \min S \cap {\mathbb{Z}_+}\). Om \(t \in S\), så \(t=kd+r\), \(0 \le r < d\). Alltså \(r=t-kd \in S \cap {\mathbb{N}}\). Minimialitet av \(d\), \(r < d\) ger \(r=0\). Så \({d} \lvert {t}\).
Men \(a,b \in S\), så \({d} \lvert {a}\), \({d} \lvert {b}\), och om \(\ell\) är en annan gemensamm delare så \(a= \ell u\), \(b= \ell v\), och \[d= ax+by = \ell u x + \ell v y = \ell(ux + vy)\] varför \({\ell} \lvert {d}\). Det följer att \(d\) är den största gemensamma delaren. ◻
- Étienne Bézout
- Bezouts sats
- Euklides algoritm
- Extended Euclidean Algorithm
- Extended Euclidean algorithm, exempel
\[\begin{split} 27 &= 3*7 + 6 \\ 7 &= 1*6 + 1 \\ 6 &= 6*1 + 0 \end{split} \qquad \begin{split} 6 &= 1*27 - 3*7 \\ 1 &= 7 - 1*6 \\ & = 7 -(27 - 3*7)\\ &= (-1)*27 + 4*7 \end{split}\]
- Xgcd
Algorithm
- Initialisering: Sätt \(x = 1, y = 0, r = 0, s = 1\).
- Terminering?: Om \(b = 0\), sättt \(d = a\) och terminera.
- Kvot och rest: Divisionsalg ger \(a = qb + c\) med \(0 \le c < b\).
- Shift: Sätt \((a, b, r, s, x, y) = (b, c, x - qr, y - qs, r, s)\) och gå till steg 2.
- Slut: \(\gcd(a,b)=d = rx + sy\)
- Extended Euclidean algorithm, exempel
2.1.7. Unique factorization into primes
- Some Lemmas
\(\gcd(an,bn)=\lvert n \rvert \gcd(a,b)\).
Bevis Antag \(a,b,n \in {\mathbb{Z}_+}\). Induktion över \(a+b\). Bas: \(a=b=1\), \(\gcd(a,b)=1\), \(\gcd(an,bn)=n\), OK.
Ind. steg: \(a+b >2\), \(a \ge b\). \[a = kb +r, \quad 0 \le r < b\] Eftersom \(a \ge b\), \(k>0\).
Då \[\begin{split} \gcd(a,b)& =\gcd(b,r) \\ \gcd(an,bn)& =\gcd(bn,rn) \end{split}\] ty \[an = kbn + rn, \quad 0 \le rn < bn.\] Men \[b+r = b+ (a-kb) = a-b(k-1) \le a < a+b,\] så ind. hyp. ger \[n\gcd(b,r) = \gcd(bn,rn).\] Men \(LHS=n\gcd(a,b)\), \(RHS=\gcd(an,bn)\).
Om \({a} \lvert {bc}\) och \(\gcd(a,b)=1\) så \({a} \lvert {c}\).
Proof. \[1=ax+by,\] så \[c=axc + byc.\] Eftersom \({a} \lvert {RHS}\), \({a} \lvert {c}\). ◻
- En viktig primtalsegenskap
\(p\) prime, \({p} \lvert {ab}\). Då \({p} \lvert {a}\) eller \({p} \lvert {b}\).
Proof. Om \({p} \not \lvert {a}\) så \(\gcd(p,a)=1\). Tidigare lemmat ger nu att \({p} \lvert {b}\). ◻
- Euklides igen
- Oändligt många primtal
Varje \(n \in {\mathbb{Z}_+}\) kan skrivas som en produkt av primtal. Det finns oändligt många primtal.
Proof. \(1\) är tomma produkten. Ind över \(n\). Om \(n\) primtal, OK. Annars, \(n=ab\), \(a,b < n\). Så \(a,b\) produkt av primetal. Sätt ihop.
Antag \(p_1,p_2,\dots,p_s\) lista på alla kända primtal. Sätt \[N=p_1p_2 \cdots p_s +1,\] då är \(N=kp_i + 1\) för alla kända primtal, så inget känt primtal delar \(N\). Men \(N\) är en produkt av primtal, så antingen är det självt ett (okänt) primtal, eller så är det en produkt av okända primtal. ◻
\[\begin{split} 2*3*5+1&= 31 \onslide<2->\\ 2*3*5*7+1 & =211 \onslide<3->\\ 2*3*5*7*11*13+1 &= 59*509 \end{split}\]
- Oändligt många primtal
- Aritmetikens fundamentalsats
- Aritmetikens fundamentalsats
Varje \(n \in {\mathbb{Z}_+}\) kan unikt (upp till omording av faktorer) skrivas \[n = p_1 p_2 \cdots p_s, \qquad p_i \text{ prime }.\]
Proof. Existns, Euklides. Unikhet: antag \[n = p_1 p_2 \cdots p_s = q_1 q_2 \cdot q_r.\] Eftersom \({p_1} \lvert {n}\), har vi att \({p_1} \lvert {q_1q_2 \cdots q_r}\), vilket mha tidigare lemma ger \({p_1} \lvert {q_j}\) något \(q_j\), alltså \(p_1=q_j\). Kancellera och fortsätt. ◻
- Aritmetikens fundamentalsats
- Exponentvektorer
- Exponentvektorer
- Numrera primtalen i växande ordning, \(p_1=2\),\(p_2=3\),\(p_3=5\), et cetera.
- Då \(n=\prod_{j=1}^\infty p_j^{a_j}\), med bara ändligt många \(a_j\) noll-skiljda.
- Låt \(v(n)=(a_1,a_2,a_3,\dots)\) vara denna heltalsföljd.
- Då \(v(nm)=v(n)+v(m)\).
- Ordna komponentvis, då \({n} \lvert {m} \iff v(n) \le v(m)\).
- Vi har \(v(\gcd(n,m))= \min(v(n),v(m))\).
\[\begin{split} \gcd(100,130) &= \gcd(2^2*5^2,2*5*13) \\ &= 2^{\min(2,1)}*5^{\min(2,1)}*13^{\min(0,1)} \\ &= 2^1*5^1*13^0 \\ &= 10 \end{split}\]
- Exponentvektorer
- Minsta gemensamma multipel
- \(a,b \in {\mathbb{Z}}\)
- \(m=\operatorname*{lcm}(a,b)\) minsta gemensamma multipel om
- \(m=ax=by\) (gemensam multipel)
- Om \(n\) gemensam multipel till \(a,b\) så \({m} \lvert {n}\)
- \(a,b \in {\mathbb{Z}_+}\), \(c,d \in {\mathbb{Z}}\)
- \(\operatorname*{lcm}(\prod_{j}p_j^{a_j}, \prod_{j}p_j^{b_j}) = \prod_j p_j^{\max(a_j,b_j)}\)
- \(ab=\gcd(a,b)\operatorname*{lcm}(a,b)\)
- Om \({a} \lvert {c}\) och \({b} \lvert {c}\) så \({\operatorname*{lcm}(a,b)} \lvert {c}\)
- Om \(c \equiv d \mod a\) och \(c \equiv d \mod b\) så \(c \equiv d \mod \operatorname*{lcm}(a,b)\)
2.1.8. Mer om primtal
- Eratosthenes såll
- Primtal i arithmetisk progression
- Varje heltal har rest 0,1,2, or 3, when divided by 4
- Bortsett från 2 så är alla primtal udda
- Så primetal \(>2\) är antingen på formen \(4n+1\) eller \(4n+3\)
- \(4n+3=4(n+1)-1=4m-1\).
Det finns oändligt många primtal på formen \(4m-1\).
- Bevis
Proof. Låt \(q_1,\dots,q_r\) vara de kända primtalen, sätt \[N=4q_1q_2 \cdots q_r -1\] Då \(N\) udda, ej delbar med någon \(q_j\). Primtalsfaktorisera \(N\): \[N=u_1u_2 \cdots u_s\] Om alla \(u_i=4m_i+1\) så \[N=(4m_1+1)(4m_2+1) \cdots (4m_s+1) = 4m+1,\] en motsägelse!. Så någon \(u_j=4m_j-1\), \({u_j} \lvert {N}\) så \(u_j \not \in \left\{{q_1,\dots,q_r}\right\}\), alltså tidigare okänd. ◻
\(a,b \in {\mathbb{Z}}\), \(\gcd(a,b)=1\). Då innehåller \(a{\mathbb{Z}}+b\) oändligt många primtal.
Uppenbarligen så har \(6{\mathbb{Z}}+ 3\) bara ett primtal, 3, så villkoret nödvändigt.
- Dirichlet