Si.chalmers.it

Matematiska Institutionen, KTHAlgebra D2, VT 2002Anders Bj¨ a 1200-talet (och i specialfall redan 1000 ˚ at m1, m2, . . . , mk vara positiva tal s˚ adana att bi Mi ≡ 1 (mod mi), 1 ≤ i ≤ k. L˚ x = a1 b1 M1 + a2 b2 M2 + · · · + ak bk Mk.
x = a1 b1M1 + · · · + ai biMi + · · · + ak bkMk ≡ ai (mod mi), mi (x − x ), f¨or ∀ 1 ≤ i ≤ k. Men eftersom mi ¨ar relativt prima m˚ a m1 m2 . . . mk (x − x ), d.v.s. x ≡ x (mod m).
osa system av typ (1). Arbetet ligger framf¨ amma talen bi , de multiplikativa inverserna till Mi modulo oras effektivt med Euklides algoritm.
ark att om flera system av typ (1) med olika h¨ ang. ”Vikterna” yi = bi Mi kan sedan lagras i datorns minne och varje individuellt system (1) har enl. (2) l¨ x = a1 y1 + a2 y2 + · · · + ak yk (mod m).
Vi har M1 = 3 · 5 = 15 , M2 = 4 · 5 = 20 , M3 = 4 · 3 = 12 , och vill osningen genom ”trial and error”. Genom att s¨ multipler av 15, 20 resp. 12, hittar vi f¨ varav: x = 1 · (−15) + 2 · (−20) + 4 · 36 = 89 ≡ 29 (mod 60).
amda. Exempelvis skulle y1 = 45, y2 = 40 och y3 = −24 osningen till systemet (3) bara kan best¨ a inte utan ytterligare information veta om ar en bijektion (d.v.s., injektion + surjektion) Ovning: Kontrollera att f (0) = 0 , f (1) = 1 , f (−a) = −f (a) , och om at R1, R2, . . . , Rk vara ringar. Det enklaste s¨ ar att ta den direkta (Cartesiska) produkten som R1 × R2 × · · · × Rk = {(a1, a2, . . . , ak) | ai ∈ Ri , 1 ≤ i ≤ k} a den definiera addition och multiplikation koordinatvis (a1, . . . , ak) + (b1, . . . , bk) = (a1 + b1, . . . , ak + bk) (a1, . . . , ak) · (b1, . . . , bk) = (a1 · b1, . . . , ak · bk).
or R1 × R2 × · · · × Rk till en ring ( ¨ iomen) som kallas den direkta produkten av ringarna Ri.
Exempel. R = Z8 × Z9 × Z5 ¨ar en ring med 8 · 9 · 5 = 360 element.
H¨ aknar vi modulo 8, i andra modulo 9, etc.) Sats 2. Antag att n = pe1 pe2 . . . pek ¨ definierad av [a]n → [a] e , [a] e , . . . , [a] e atriktade implikationerna ⇒ visar att avbildningen f ¨ar atriktade implikationerna ⇐= visar att f ¨ar in- adan alogritm har vi redan: Kinesiska rest- (iii) f respekterar multiplikation: Helt analogt.
Zn. Eftersom aritmetiken i en dator sker i angden Z ej kan representeras i en dator), s˚ Till exempel, om a · b skall ber¨aknas (modulo n) s˚ vilket ger a · b ≡ c (mod n). Ber¨akning av f kan ske effektivt meddivisionsalgoritmen (division av a med respektive pei ger som rest i angder additioner, subtraktioner och multiplikationer av akning av f −1 med kinesiska restalgoritmen kan orlagrade vikter yi (se kommentaren efter a kallad snabb aritmetik, se Knuth (1981).
Determinanten beror bara av ringoperationer (multiplikationer och ad-ditioner, t¨ a x = 1 · 15 + 2 · 10 + 3 · 6 = 53 ≡ 23 (mod 30) l¨oser systemet (5).
apeka att snabb aritmetik av detta slag (Sats 2 ara ekvationssystem med heltalskoefficienter. Detta finns beskrivet isomorf med en direkt produkt av cykliska grupper av primtalspotens-ordning. Detsamma g¨ angd primtalspotenser {pe1 , pe2 , . . . , pek oljer att |G| = pe1 pe2 . . . pek. Av Sats 3 f¨oljer d¨arf¨or att Exempel. (1) Varje Abelsk grupp av ordning 4 ¨ eller med Z2 × Z2. (I detta fall kan ordet ”Abelsk” tas bort, se ¨ovning13.5.2 och 13.6.4 i Biggs.) ar isomorf med Z100? Svar (enligt Sats 2): Z4 × Z25.) Avslutande kommentar. Satserna 2 och 3 ¨ strukturerna (beskrivet av en struktursats). Sats 3 s¨ att kan skrivas som produkt av primtal. Denna ager speciellt att de ”enkla” heltalen ¨ orstagradspolynom p(z) = (z − a1) . . . (z − an), angden av alla reella funktioner f : R → R med period 2π (d.v.s. f (x + 2π) = f (x) , ∀x R). Om en s˚ alartad (exempelvis om dess derivata existerar och ¨ aller enligt en sats av Dirichlet-Fourier or alla x R. Detta kan uppfattas som en struktursats som s¨ att komplicerade periodiska funktioner f (t.ex. vibrationer) alltid¨ sultat finns i det icke-kommutativa fallet. Svaret ¨ or vissa viktiga klasser av geometriska transformationsgrupper (Lie-grupper, Coxeter-grupper) finns detaljerade struktursatseroch klassifikation av de ”enkla” grupperna inom klasserna. Studietav s˚ adana grupper har varit en mycket viktig gren av 1900-tals- orjan av 1980-talet fullbordades en klassifikation av alla ¨ andig utskrift av alla delar av denna klassifikation (med ava 10.000-20.000 sidor. Begreppet ”enkel” har h¨ ar sammansatta av dessa enkla grupper p˚ D.E. Knuth, The art of computer programming, Vol. 2 (Seminumericalalgorithms), Addison-Wesley, 1969, 1981.
G. Mackiw, Applications of abstract algebra, Wiley & Sons, New York,1985.
at f : Z60 → Z3 × Z4 × Z5 vara avbildningen i Sats 2.
am f −1 (1, 0, 0) , f −1 (0, 1, 0) , f −1 (0, 0, 1) .
or ”snabb aritmetik” som skisserades att anga isomorfityper av Abelska grupper av ordning 24 finns am den produkt av cykliska grupper (som i Sats 3) 6. Visa att varje Abelsk grupp av ordning 30 ¨ 4. 3 isomorfityper: Z8 × Z3 , Z4 × Z2 × Z3 , Z2 × Z2 × Z2 × Z3.
5.
{[1], [5] , [7] , [11]} och alla element har ordning 2, s˚ a enligt Sats 3 existerar bara en isomorfiklass,

Source: http://si.chalmers.it/diskretmatte/resurser/teman/kines/Kines.pdf