Föreläsningar i Talteori

1. Introduktion

2. Kongruensräkning

2.1. Delbarhet

2.1.1. Definition

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

divisorlattice7.png
Illustration 1 Heltalen under delbarhet

Begränsad till \({\mathbb{Z}_+}\) så är delbarhet en partialordning, med ett unikt minimalt element 1.

2 Del av Hasse diagram

Id est,

  1. \({a} \lvert {a}\),
  2. \({a} \lvert {b} \, \wedge \, {b} \lvert {c} \quad \implies \quad {a} \lvert {c}\),
  3. \({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

  1. 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\).

  2. Bevis, existens

    Antag för enkelhets skull att \(a,b >0\). Fixera \(b\), induktion över \(a\), basfall \(a

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

  1. Definition
    1. Största gemensamma delare

      \(a,b \in {\mathbb{Z}}\). Den största gemensamma delaren till \(a\) och \(b\), \(c=\gcd(a,b)\), definieras genom

      1. \({c} \lvert {a} \, \wedge \, {c} \lvert {b}\),
      2. 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

      1. Om \({d} \lvert {a} \, \wedge \, {d} \lvert {b}\), så \({d} \lvert {c}\).
  2. Bezout
    1. 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. ◻

    2. Étienne Bézout
  3. Euklides algoritm
    1. Fundamentalt lemma

      Om \(a = kb +r\) så \(\gcd(a,b)=\gcd(b,r)\).

      Proof. Om \({c} \lvert {a}\), \({c} \lvert {b}\) så \({c} \lvert {r}\).

      Om \({c} \lvert {b}\), \({c} \lvert {r}\) så \({c} \lvert {a}\). ◻

  4. Extended Euclidean Algorithm
    1. 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}\]

    2. Xgcd

      Algorithm

      1. Initialisering: Sätt \(x = 1, y = 0, r = 0, s = 1\).
      2. Terminering?: Om \(b = 0\), sättt \(d = a\) och terminera.
      3. Kvot och rest: Divisionsalg ger \(a = qb + c\) med \(0 \le c < b\).
      4. Shift: Sätt \((a, b, r, s, x, y) = (b, c, x - qr, y - qs, r, s)\) och gå till steg 2.
      5. Slut: \(\gcd(a,b)=d = rx + sy\)

2.1.7. Unique factorization into primes

  1. 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}\). ◻

  2. 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}\). ◻

  3. Euklides igen
    1. 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}\]

  4. Aritmetikens fundamentalsats
    1. 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. ◻

  5. Exponentvektorer
    1. 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}\]

  6. Minsta gemensamma multipel
    • \(a,b \in {\mathbb{Z}}\)
    • \(m=\operatorname*{lcm}(a,b)\) minsta gemensamma multipel om
      1. \(m=ax=by\) (gemensam multipel)
      2. 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

  1. Eratosthenes såll
    1. Eratosthenes såll

      Algorithm

      2

      1. Givet \(N\), hitta alla primtal \(\le N\)
      2. \(X=[2,N]\), \(i=1\), \(P=\emptyset\)
      3. \(p_i=\min(X)\).
      4. Ta bort multipler av \(p_i\) från \(X\)
      5. \(P=P \cup \left\{{p_i}\right\}\)
      6. Om \(p_i \ge \sqrt{N}\), terminera, annars \(i=i+1\), goto 3.
      sieveE.jpg
  2. 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\).

    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.

    2. Dirichlet

3. Aritmetiska funktioner

4. Hensel-lyft

5. Primitiva rötter

6. Kvadratiska residyer

7. Kvadratisk reciprocitet

8. Kedjebråk

9. Icke-linjära diofantiska ekvationer

10. Gaussiska heltal

11. Övrigt