algebra

Rozszerzony Algory tm Euklides a

NWDI >=1

^ro= 9ir.*r₃ ^r: = ?3^r:'⁺-^r3

Zasadnicze Tw arytmetyki Każda liczba naturalna złożona ’ cz?;l i nie będąca I.,pierwszą) może być przedstawiona jako iloczy n liczb pierwszych.

Kongruencje

Niech mfzZ. Mówimy. że 2liczby całkowite a. bcZ. są kongruencyjne modiao jeślim a-b a= b mod m > czyli mąiątakąsamą liczbę z dzielenia

Wiaznażc i k<tnsru£nz.ii:

1)    a=b modm *^a=b ' mod-m

2)    a=a madm

3)    Jeśli a=b mod m • i łr=c mod m ■ to a=ci mcdm<

4) Jeślia=b mod mdxcZ. to (a+;r)=( b~x)[modm)

! ax =.bx mod m)

5) JeśłiNWD\c. m = 1 to ca=cb modm' implikąje a=b mod m>

6)    Kongruencja ax=b mod m < marozwiązanie xtzZ**NWD\a. b

Małe tw. Fermata

Niechp~-K. p— l.pierwsza. a<zZ. a^O wówczas cć= a mod p >

Ponadto. jeślip\a to a*’’= 1 modp

Tw. Eulera Fermata

Funkcja Eulera «#> I m * to jes 11. naturalna < m względnie pierwsza z m

Jeśli a&.Z. mtN NWD a.m = 1 to a * = 1 i modm

3jł=2! mod5 NWD\35 =1

3x-t-5y=2—algorytm euklidesa Chińskie Tw o resztach

Niech nv m^ .... m, będą l.naturalnąwzgl.pierw. NWD\ m .m = 1 i=£j

wówczas dla dowolnychlcalk a. .... a, istnięjel. całk x taka. że x=a_k modm_:• k= 1,2.....n

31aznażac£sglc<zi Kaimńisa

\)d _u\a.a'=0

2) d_u\a.b»Ca*b

3) d_B\a.b<=d_B\b. a<

4) d_M\a.c)6d„\a.b\ + djb.c)

5) d_lt\a.b'=w_u\a-b>

Minimalna odległość kodu K

d^,\ K <=min{dg\a.b'\:a4=b. a.b^K)

Twierdzenie Kod wykrywa pojedynczy

błąd. gcfc wy krywa wszystkie bię$; e g$: w_a = 1

Twierdzenie Niech Kod K ma minimdną odległośćt .wówczas kod K będzie wykr.wd wszystkie błąd; etakie. żew_g\e i >< t-1 Ponadto istnieje błąd eow_x=t. który nie będzie wykryte przez kod K

Korygowanie błędów

Mówmy że kod korygąjebłąd e. jeśli dlalutżdego słowa kodowego bf±K. słowo b-ejest bliższe do bniż do innych słów kodowych. czyli d_u\b~e.b\<d_B\b-re.a' dlaafżK.a^b

Tw Kod kory gtge t błędów *$d^^ K i > 2t

Kod binaryK nazywamy liniowym, jeśli s urna każdxh 2 słów kodowych jest słowem kodowem. czyli a. btżK—r a— b~K

Kod K jest liniowy < > jest podprzestrz&śą liniową przestrzeni Z!

Ponadto, jeśli k=e£m K i wy mice podprzestrz toKma2‘slow kodowych d^,\K)=ie^\K)

xcKe>xH=0_;HtżZ'.’^m.rarkH=m dm V = n- rark A

Macierz H nar.WrOrrr; kontrolną macierzą parzy stości Macierz G nazywatt; macierzą generującą kod gt$; rakG=k

SYNDROM\S —w' H w" słowo kodowe er s=w' H=0 Własności s';ndomu w =w-*-e w—słowo kodowe e—błąd s=w^mH=wH+eH=em

Kod Hamminga jest doskonali. tzn każde słowo z Z\ jest albo słowem kodowym albo jest odieg^; o dokładne jednego słowa kodowego o 1i d _B= 1 1

TW: Niech H będzie kontrolną maci&zą parzystości kodu liniowegoKWówcza:kod K rrtad*,i K )=t**gtfr każcfr układ i -1 wiersąy macierz; H jest liniowo niezależą; i istnieje u kład t wiersąy. który jest lin zależą;

Pierścień całkowity

*    nie ma dzielników zera

*    ma jedynkę, jest przemienny

*    ma coną: mniej 2 elementy

Własność Mech Fbędzie ciałem, w, u, v€F \ x] Jeśliw{x)u\x i = v(xiu(x), toni xi=vix'i

Dzielenie wielomianów

MiechS-pierścień. Miech u, weS[x ] Jeśliwspółcz przy najwyższą potędze wielomianu u jestelemememodwracalnymwS, to S [x] jestwykonalnedzielenie zresztąwiełomianu w przezu, tznw=uq-r, q€S [x], r€S [x]

Każdy wielomian można zapisać jako iloczyn wielomianów nierozkiadalnych zewspółcz 1 przy najwyższą potędze. To przestawienie jest jednoznaczne

Podpierścień- warunki

*    niepusty podzbiór A

*    a, b€A=*a-b€A

*    a, beA^abeA

Ideał I T - pierścień ,1=T

*    niepusty podzbiór pierść. owiasnościach:

1) x,ve/=*x-ye/

2) x€l ,r€l =*xr€l

Wielomian w\ x i nazywany rozkładalnym nad F jeśli istniej a u,veF \x] stopnia dodatniego takie, żew=uv

I={ar:reT}-to ideał główny ZJx" w(xiZjx]-pierścieńilorazowy

działania.na wąrzr-yach

(a-I>-(b-D=(a-bH

(a+I)*(b^D=ab^I

Jeśli wielomian w (x )€Z_; f x 1 jes t nierozkiadalny

nad ciałem Z., to pierścień ilorazowy Z.[ x" wi xiZ_fx"

jest ciałem względemdodawania i mnożenia

Podprzestrzeńliniowa W, dim W=k, przestrz lin. Z'_: ma dokładnie 2 * wektorów