Algebra og talteori

Matematikken undersøger strukturer. Algebra er teorien for regnereglernes strukturer.

I dette afsnit benytter vi kvantorerne ∀ og ∃.

Emner

Største fælles divisor   sfd

Ved største fælles divisor for to hele tal a og b (a og b ≠ 0) forstår vi det største hele tal, der går op i både a og b.

Euklid Euklid tillægges æren for en elegant algoritme til beregning af sfd(a, b).
    Euklids algoritme sfd(a, b)
    Indlæs a og b
    Sæt a' = a og b' = b
    Sålænge b' > 0 gør
    Slut sålænge
    Udskriv a'

Algoritmen bygger på, at hvis et tal går op i både a og b, går det også op i a mod b og b mod a. Da desuden 0 ≤ a mod b < |b| og 0 ≤ b mod a < |a|, vil Euklids algoritme standse med talparret (a', 0). De fælles divisorer i a og b går også op i a', så sfd(a, b) = a'.

Vi ser på mængden af heltallige linearkombinationer over a og b

Det er klart, at både a mod b og b mod a og dermed sfd(a, b) er elementer i L(a, b).
Tænker vi os, at der findes et element i L(a, b) med egenskaben 0 < m· a + n· b < sfd(a, b), har vi ved division med sfd(a, b)

Er sfd(a, b) = 1, kaldes a og b indbyrdes primiske. I dette tilfælde findes altså to hele tal m og n, så

[ Hovedmenu ] [ Ordliste ]

Komposition i en mængde

Vi ser på en mængde M organiseret af en komposition (regneregel) ⊕. D.v.s. for to elementer a og b i M kan man danne elementet a ⊕ b, som (også) ligger i M.

Man siger, at strukturen (M, ⊕) er stabil.

    Særlige betegnelser
  1. ∀ a, b ∈ M : a ⊕ b = b ⊕ a   (kommutativ komposition)
  2. ∀ a, b, c ∈ M : a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c   (associativ komposition)
  3. ∃! e ∀ a ∈ M : a ⊕ e = e ⊕ a = a   (e er neutralt element for kompositionen)
  4. ∀ a ∃! a–1 ∈ M : a ⊕ a–1 = a–1 ⊕ a = e   (a–1 og a er hinandens inverse)

Kommutativ komposition

⊕ kaldes kommutativ (Abelsk), hvis

Associativ komposition

⊕ kaldes associativ, hvis

Neutralt element

e er et neutralt element i (M, ⊕) hvis

[ Hovedmenu ] [ Ordliste ]

Gruppe

En assosiativt organiseret mængde med neutralt element, hvor alle elementer har inverse, kaldes en gruppe.

    (M, ⊕) er en gruppe, hvis og kun hvis
  1. ∀ a, b, c ∈ M : a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c   (associativ komposition)
  2. ∃ e ∀ a ∈ M : a ⊕ e = e ⊕ a = a   (e er neutralt element for kompositionen)
  3. ∀ a ∃ a–1 ∈ M : a ⊕ a–1 = a–1 ⊕ a = e   (a–1 og a er hinandens inverse)

Er kompositionen desuden kommutativ, kaldes gruppen kommutativ eller abelsk.

En gruppes neutrale element e er entydigt bestemt fordi, hvis e' (også) er neutral, er e' = e' ⊕ e = e .

a inverse a–1 er entydigt bestemt fordi, hvis a' (også) er invers til a, er a' = a' ⊕ e = a' ⊕ (a ⊕ a–1) = (a' ⊕ a) ⊕ a–1 = e ⊕ a–1 = a–1 .

Ligningen   a ⊕ x = b

En grund til at grupper er interessante er, at ligningen a ⊕ x = b har en entydig løsning:

På tilsvarende måde ses, at ligningen x ⊕ a = b har den entydige løsning x = b ⊕ a–1 .

Restklasser

Vi ser på heltals - division i de hele tals mængde Z. Skal a divideres med n, gælder det om at finde de hele tal q og r, hvor 0 ≤ r < |n| så

hvor r er den principale rest ved divisionen. Ind i mellem skriver man

Går divisionen op, så a mod n = 0, skriver man ofte n | a.

Kongruens - modulo

De to hele tal a og b kaldes kongruente modulo n, hvis de giver samme rest ved division med n. Man skriver

Mængden at tal kongruente med a modulo n skrives (a)n, så

så a – b kan divideres med n uden rest. Altså hvis n | (a – b).

Mængdesystemet

er en klasseldeling i de hele tal Z, fordi et vilkårligt helt tal er element i netop én af mængderne i systemet Kn. Et element i en klasse kaldes også en repræsentant for klassen. Et sæt af n hele tal, ét fra hver restklasse, kaldes et fuldstændigt sæt af rester. Kn er et fuldstændigt sæt af principale rester.

Regning med kongruensklasser

Vi definerer følgende regneregler i Kn:

Man kunne nu frygte, at resultatet afhang af valget af repræsentanter for klasserne, men ...
Lad a' ∈ (a)n og b' ∈ (b)n. Vi har (h og k er hele tal)

så resultatet er uafhængigt af valget af klasserepræsentant.

Forkortning

Vi ser på ligningen (kongruensen) (a · b)n = (a · c)n med a ≠ 0. Mon der kan forkortes med a ?
Der findes hele tal h og k, så a · b + h · n = a · c + k · n, eller a · (b – c) = n · (k – h) eller b – c = n · (k – h) / a
Har a og n ikke andre positive fælles faktorer end 1 (man siger, at tallene er indbyrdes primiske), må a gå op i k – h, så b – c = et helt tal · n, eller (b)n = (c)n. Vi har altså

Restklassegrupper

(Kn , + ) er en kommutativ gruppe med det neutrale element (0)n. (an) og (–a)n er hinandens inverse.

Er (Kn\ (0)n , · ) en gruppe, må det neutrale element være (1)n.
Skal (a)n have et inverst element, må ligningen (a)n · (x)n = (a · x)n = (1)n kunne løses. Der skal findes hele tal h og k så a · x + h · n = 1 + k · n eller a · x + (h – k) · n = 1. Ifølge Bezouts sætning kræver det, at sfd(a, n) = 1. Men skal det være tilfældet for alle a-værdier i {1, 2, 3, ... , n – 1}, må n være et primtal.

[ Hovedmenu ] [ Ordliste ]

Primtal

Et primtal p er et helt tal > 1, hvis eneste positive divisorer er 1 og p. Et sammensat tal er et helt tal > 1, som ikke er et primtal. (1 er altså "hverken eller"). Primtallene er

Eratostenes' si

Primtallene (op til en vis grænse) kan konstrueres på denne måde:

Eratostenes si - metode viser intuitivt, at der (i gennemsnit) bliver længere og længere mellem primtallene. Det kunne forlede os til at tro, at de slipper op, men ...
Hos Euklid findes et bevis for, at der findes uendelig mange primtal.
Antager vi, at p1, p2, p3, ... , pn var samtlige primtal, skulle p = p1· p2· p3· ...· pn + 1 være et sammensat tal. Men dels er p større end noget primtal, dels går intet primtal op i p. Men det er en umulighed, så antagelsen om endelig mange primtal må forkastes.

Primfaktoropløsning

Vi ser på et helt tal a > 1. Det er vel klart, at den mindste positive divisor i a er et primtal p1, så a = p1· a1. Er a1 > 1, er mindste positive divisor p2 et primtal og dermed a = p1· p2· a2. Er a2 > 1 fortsættes processen. Da talfølgen ai er aftagende, og der kun er endelig mange hele tal mellem 1 og a, standser processen med

Denne primfaktoropløsning af a er entydig (pånær ombytninger).

Fermats lille sætning

I restklassegruppen (Kp\ (0)p , · ), hvor p er et primtal, ser vi på kongruensen (am)p = (an)p.
Da a og dermed an er primisk med p, kan der forkortes, så (am–n)p = (1)p. Talfølgen a1 mod p, a2 mod p, a3 mod p, ... , an mod p, ... er altså periodisk (gentager sig selv med en fast periode). Da højest de p – 1 første tal i følgen kan være forskellige, er periodelængden m – n = p – 1, og gruppen kaldes cyklisk. Konklusion:

D.v.s. hvis p er et primtal og a ikke er et multiplum af p går divisionen (ap – 1 – 1) : p op .

[ Hovedmenu ] [ Ordliste ]

Pythagoræiske tripler

En Pythagoræisk tripel er et sæt af 3 hele positive tal a, b, c, hvor a2 + b2 = c2. Vi har

Da a2 er et kvadrattal og c + b og c – b er forskellige, er c + b og c – b begge kvadrattal.

Af b = ½(p2 – q2) = ½(p + q)(p – q) slutter vi, at p og q enten begge er ulige eller lige. Men de er ikke begge ulige, for i så fald er a ulige mens b og c begge er lige, hvilket er umuligt. Altså kan vi sætte

Vi har fundet en parameterfremstilling for samtlige Pythagoræiske tripler:

[ Hovedmenu ] [ Ordliste ]

Kædebrøker

På moderne lommeregnere findes en knap, der omsætter et decimaltal til blandet tal, d.v.s. som et helt tal plus en brøk. 1.25 skrives 1 1/4. Det sker v.h.a. kædebrøker (Eng.: continued fractions).

Kædebrøksalgoritmen

Er a et reelt tal, er int(a) heldelen af a d.v.s. det største hele tal, der er mindre end eller lig a. Vi sætter frac(a) = a – int(a). Er a en decimalbrøk, er 1 / frac(a) = a'1 > 1. Vi sætter int(a) = a0 og int(a'i) = ai og omskriver a

Fortsættes denne proces, får vi

og kaldes kædebrøksfremstillingen af a.

Standser processen, så kædebrøksfremstillingen for a endelig lang, er a (naturligvis) et rationalt tal, og vi viser, at hvis a er rational, er kædebrøksfremstillingen endelig.
Er nemlig a'i = pi/qi, pi > qi, er ai+1 = int(pi/qi) og a'i+1 = qi/ri hvor ri < qi. Da nævnerne er positive hele tal men bliver indre og mindre, må processen stoppe.

Kædebrøksfremstillingen er entydig bortset fra, at [a0, a1, a2, ..., an, 1] = [a0, a1, a2, ..., an+1], som er ét led kortere.

Brøkfremstilling

For at finde værdien af en endelig kædebrøk a = p / q = [a0, a1, a2, a3, ..., an], går man "baglæns" frem. Er vi undervejs nået til værdien T / N, er næste værdi 1 / (ai + T/N) = N / (N ai + T). Den "inderste" brøk er T / N = 1 / an, så kædebrøkens brøkfremstilling kan findes med følgende alghoritme

Denne regnemaskine udfører algoritmen. Indtast kædebrøken og klik på kør.

Kædebrøken = =

Uendelige kædebrøker

Ifølge ovenstående kan en uendelig kædebrøk ikke fremstille et rationalt tal. Spørgsmålet er, om de i det hele taget fremstiller noget. Vi giver et uformelt argument og indfører kædebrøkens konvergenter Ki = [a0, a1, ... , ai], som er rationale tal. Der gælder

Det skyldes, at når vi går frem i rækken K0, K1 , ... sker der en forøgelse først i tælleren, så i nævneren, så i nævnerens nævner (så værdien stiger). Forøgelsen sker skiftevis i tæller og nævner, så værdien skiftevis stiger og falder. Da desuden forøgelsen sker stadig dybere i nævnerens nævners ... nævner, bliver ændringen stadig mindre, så

Heraf slutter vi, at konvergenterne konvergerer (deraf navnet) mod et (irrationalt) tal

En hovedanvendelse af kædebrøker er, at de giver rationale tilnærmelser til irrationale tal, jo bedre, jo større i.

√2

Vi ønsker at finde en metode til beregning af √2 og tager udgangspunkt i ligningen

Indsætter vi dette udtryk for √2 på højre side, få vi

Da kædebrøken er uendelig, slutter vi, at √2 er et irrationalt tal.

Denne regnemaskine beregner √2. Klik på næste for at få næste værdi.

En fiksere metode er måske at se på k = √2 – 1. Sammenhængen ovenfor kan udtrykkes

Kædebrøksfremstilling af φ

φ er forholdet mellem den korte og den lange side af et stykke papir der lever op til det gyldne snit.
φ bestemmes af ligningen 1/φ = φ + 1 eller φ = 1 / (1 + φ). Sætter vi φ ind på φ's plads på højre side, få vi
φ = 1 / (1 + 1 /( 1+φ)). Fortsættes denne proces, har vi

Bemærk, at kædebrøken består af 0 efterfulgt af lutter 1 - taller.

Klik på næste for at få næste værdi af φ.

Algebraiske og transcendente tal

Et reelt tal a kaldes algebraisk, hvis det er rod i en n-te grads ligning, hvor koefficienterne er hele tal.

√2 og φ = (√5 – 1) / 2 er eksempler på algebraiske tal

Ikke - algebraiske tal kaldes transcendente. Eksempler er π og e (grundtallet for den naturlige logaritme).

Det kan vises, at kun tal, der kan skrives på formen (a + √b) / c har periodiske kædebrøksfremstillinger (d.v.s. at kædebrøken gentager sig selv fra et vist trin).

[ Hovedmenu ] [ Ordliste ]

Links

Generelt

Primtal

Fermats lille sætning

Pythagoræiske tripler

Kædebrøker

[ Toppen af siden ] [ Ordliste ] [ Tilbage til hovedsiden ]