pathterminuspages/brkmnd.dk/aboutcontactabout me

Talteori

28-03-2016|Generelt Algebra

Her beskæftiger vi os med mængden ℤ.

Prop. 1

  1. Hvis A .subset setZ^{+}, eksisterer et m i A så m .le a, .forall a .isin A. m kaldes for minimum i A.
  2. Hvis a, b .isin setZ, a .ne 0, siger vi at a er en divisor i b hvis der eksisterer et tal k i ℤ så ak = b, og vi skriver a | b. Omvendt, hvis a ikke er divisor i b, skriver vi a ∤ b
  3. Hvis a, b .isin setZ .setminus {0}, findes et entydigt bestemt positivt heltalt, d, kaldet den største fælles divisor, så:
    1. d .divides a .and d .divides b - d er fælles divisor.
    2. e .divides a .and e .divides b .drarrow e .divides d - d er den størte fælles divisor.
    Den største fælles divisor noteres d = (a,b). Hvis (a,b) = 1, siger vi at a og b er indbyrdes primiske.
  4. Hvis a, b .isin setZ .setminus {0}, findes et entydigt bestemt heltal, l, kaldet det mindste fælles multiplum, så
    1. a .divides l .and b .divides l - l er et multiplum af både a og b.
    2. a .divides m .and b .divides m .drarrow l .divides m - l er det mindste multiplum af både a og b.
    Forbindelsen mellem den største fælles divisor, d, og det mindste fælles multiplum, l, er givet ved dl = ab.
  5. (Divisionsalgoritmen) Hvis a, b .isin setZ, b .ne 0, eksisterer entydigt bestemte q, r .isin setZa = qb + r, 0 .le r .lt |b|, hvor q er kvotionten og r er rest.

Til at regne den største fælles divisor mellem to tal kan vi benytte Euklids algoritme. Den fungerer ved at man fræser divisionsalgoritmen igennem igen og igen indtil resten r er 0. Sådan her:

a = q_{0}b + r_0 b = q_{1}r_0 + r_1 r_0 = q_{2}r_1 0 r_2 . . . r_{n - 2} = q_{n}r_{n - 1} + r_n r_{n - 1} = q_{n + 1}r_n

Hvor r_n er den mindste rest forskellig fra 0. Sådanne r eksisterer da |b| .gt |r_0| .gt |r_1| .gt ... .gt |r_n| er en serie af positive heltal, og resten r_{n + 1} = 0.

Jeg har lavet algoritmen, den kan prøves her:

En direkte konsekvens af Euklids Algoritme er, at hvis a, b .isin setZ .setminus {0}, eksisterer x, y .isin setZ(a,b) = ax + by hvor x og y findes ved at regne baglæns i Euklids algoritme. Hvis feks. a = 12398 og b = 126, indsætter vi og trykker baglæns og får:

2 = 26 - (1)[50 - (1)[126 - (2)[12398 - (98)(126)]]] 2 = (126 - (2)(50)) - 50 + 126 - (2)(50) 2 = (2)126 - (5)(50) 2 = (2)126 - (5)(12398 - (98)(126)) 2 = (-1)(5)(12398) + (492)(126)

Prop. 1 del 2

  1. Et heltal p kaldes et primtal hvis p > 1, og hvis den eneste positive divisor i p er 1.
    En egenskab ved primtal, p, er: p .divides ab .drarrow p .divides a .or p .divides b
  2. Aritmetikkens fundamentalsætning: Hvis n .isin, setZ n .gt 1, kan n på entydig vis skrives som et produkt af primtal, altså for p, k .isin setZ, k .ne 1 .drarrow k .ndivides p, %alpha .isin setN kan vi skrive
    n = p_1^{%alpha 1}p_2^{%alpha 2} .sdot ... .sdot p_s^{%alpha s}
    Denne faktorisering er unik hvilket betyder, at hvis vi også har:
  3. n = q_1^{%beta 1}q_2^{%beta 2} .sdot ... .sdot q_t^{%beta t}
    er t = n, og hvis faktoriseringen sættes i orden efter største først, mindste sidst,
    er qi = pi og αi = βi Lad nu a og b være en primtalsfaktorisering af to heltal. Da er (a,b) lig med produktet af de primtal a og b har tilfælles, hvor vi tager den mindste eksponent for hver faktor hvor vi tillader en eksponent at være 0 (for faktorer de ikke har tilfælles). Feks er:
    2730 = 5 .sdot 3 .sdot 2 .sdot 7 .sdot 13 240 = 5 .sdot 3 .sdot 2^4 (2730,240) = 5 .sdot 3 .sdot 2 = 30
    På samme måde, bare omvendt, er det største fælles multiplum lig med produktet af de fælles primtal, men med den største eksponent:
    s.f.m(2730,240) = 7 .sdot 5 .sdot 3 .sdot 2^4 .sdot 13 = 21840
    Hvis to tal, a og b, er heltal og ikke har en eneste fælles primfaktor, siger vi at de er indbyrdes primiske og skriver (a,b) = 1, feks: a = 2 .sdot 3^2 = 18, b = 7 .sdot 5 = 35.
  4. Eulers φ-funktion : Lad n .isin setZ^{+}, og lad φ(n) være antallet af positive heltal a ≤ n der er indbyrdes primiske med n. Feks. for n = 12 er 1, 5, 7, 11 indbyrdes primiske samt mindre end eller lig med 12. Så φ(12) = 4. 1, 2 opfylder φ for n = 3, så φ(3) = 2 osv.
    For primtal, p, gælder φ(p) = p - 1, og generelt for a ≥ 1 gælder:
    %phi(p^a) = p^a - p^{a - 1}(p - 1)
    Funktionen er multiplikativ forstået på den måde at:
    %phi(ab) = %phi(a)%phi(b), hvor (a,b) = 1
    og på den måde kan formlen generaliseres til et hvilket som helt helt tal n, , feks:
    %phi(202) = %phi(101 .sdot 2) = 101^{1 - 1}(101 - 1)2^{1 - 1}(2 - 1) = 100 .sdot 1 = 100
    som så er antallet af tal, a ≤ 202, for hvilke (a,202) = 1.