Teoria Liczb dla początkujących

I

Zakładamy ,że znane ci są pojęcia "zbiór" i "podzbiór"; ∈ oznacza "należy do" .Użyjemy Z dla oznaczenia zbioru liczb całkowitych, i Q dla zbioru liczb wymiernych. Zakładamy podstawowe właściwości liczb całkowitych i wymiernych:
(1) (x+y)+z = x + (y+z)
(2) x+y = y+x
(3) Równanie a+x=b ma jednoznaczne rozwiązanie x (w Z, jeśli a,b są w Z;w Q, jeśli są w Q)
(4) 0+x = x
(1′) (xy)z = x(yz)
(2′) xy = yx
(3′) Równanie ax = b ma jednoznaczne rozwiązanie x w Q , jeśli a,b są w Q i a ≠ 0
(4′) 1*x = x
(5) x(y+z) = xy + xz (jest to prawo rozdzielności)

Jednoznaczne rozwiązanie a + x = b jest zapisane jako b-a. Dla a ≠0, jednoznaczne rozwiązanie ax =b jest zapisane b/a. Liczba wymierna jest dodatnia (≥ 0) lub ujemna (≤ 0); tylko 0 jest w obu; b ≥ a (lub a ≤ b) oznacza b-a ≥ 0; b > a (lub a < b) oznacza b≥a, b≠ a. Jeśli x > 0 i y > 0,wtedy x+y > 0 i xy > 0. Jeśli a,b,x są liczbami całkowitymi, a b = ax, mówimy ,że b jest wielokrotnością a ; mówimy ,że a jest podzielne przez b lub jest dzielnikiem b; co zapisujemy a|b.
Wreszcie mamy:
(6) Dowolny niepusty zbiór liczb dodatnich całkowitych zawiera co najmniej liczbę całkowitą.
Faktycznie, taki zbiór zawiera pewną liczbę całkowitą n;wtedy pierwsze wśród liczb całkowitych 0,1,...,n-1,n będą zawarte w tym zbiorze mającym wspomnianą właściwość. Odpowiednikiem postaci (6) jest "zasada indukcji matematycznej" :
(6′) Jeśli wyrażenie dotyczące liczby dodatniej x jest prawdziwe dla x = 0 i jest prawdziwe dla dla wszystkich x < n implikując prawdziwość dla x = n, wtedy jest prawdziwe dla wszystkich x.
Dowód .Nazwijmy F zbiór składający się z dodatnich liczb całkowitych , dla których wyrażenie nie jest prawdziwe. Jeśli F nie jest pusty ,zastosujemy do niego (6); wniosek jest sprzeczny z założeniem (6′)

ĆWICZENIA
I.1. Wykaż ,że relacja (-1)*(-1) = +1 jest konsekwencją prawa rozdzielności.
I.2. Udowodnij ,że dowolna liczba całkowita x > 1 ma albo dzielnik > 1 i ≤ √x albo nie ma dzielnika >x1 i < x ( w tym drugim przypadku jest nazywana liczbą pierwszą)
I.3. Udowodnij przez indukcję ,że
13 + 23 + ... + n3 = [n(n+1) / 2]2
I.4. Udowodnij prze indukcję ,że 42n+1 3n+2 jest wielokrotnością 13 dla n ≥ 0.
I.5. Wyka ,że liczba wyrazów w wielomianie stopnia d z n zmiennymi to co najwyżej (n+d)! /n!d! (Podpowiedź: użyj indukcji ma d, i obserwuj czy liczba wyrazów w homogenicznym wielomianie stopnia d n zmiennymi jest taka sama jak wielomianu stopnia d z n-1 zmiennymi)

II

Lemat. Niech d,a będą liczbami całkowitymi , d > 0. Wtedy istnieje jednoznaczna największa wielokrotnością, x dq z d która jest ≤ a; może być charakteryzowany przez dq ≤ a < d(q+1), lub również przez a = dq + r, 0 ≤ < r < d.
W tej relacji, r jest nazywane resztą z dzielenia a przez d; d jest nazywane dzielnikiem a q ilorazem).
Dowód . Zbiór liczb całkowitych w postaci a - dz z z ∈ Z zawiera liczby całkowite dodatnie, ponieważ z może być ujemne i duże w wartości absolutnej (tj. z = -N, z N jako dużą liczbą całkowitą dodatnią). Zastosujemy (6) z części I do tego zbioru wszystkich dodatnich liczb całkowitych, które mogą być zapisane w tej postaci; weźmy jej najmniejszy element r, i zapiszmy go jako a -dq; to jest ≥ 0 i < d, ponieważ w przeciwnym razie a -d(q+1) będzie należał do tego samego zbioru i będzie < r
Twierdzenie II.1. Niech M będzie niepustym zbiorem liczb całkowitych, zamkniętym ze wzglęu na odejmowanie. Wtedy istnieje jednoznaczne m ≥ 0 tak ,że M jest zbiorem wszystkich wielokrotności m: M = {mz}z∈Z = mZ.
Dowód.Jeśli x ∈ M, wtedy przy założeniu, 0 = x -x ∈M i -x = 0 -x∈ M, Jeśli również y ∈ M, wtedy y+x=y-(-x) ∈ M, tak że M jest również zamknięte pod względem dodawania. Jeśli x ∈M i nx ∈ M, gdzie n jest dowolną liczbą dodatnią całkowitą, wtedy (n+1)x = nx+x∈M; dlatego też, przez indukcję, nx ∈ M dla wszystkich n ≥ 0, stąd również dla wszystkich n ∈ Z. W końcu, wszystkie liniowe połączenia elementów M ze współczynnikami całkowitymi są w M; przy takiej właściwości M oczywiście implikuje to ,że M jest zamknięte pod względem dodawania i odejmowania, jest to równoważne z naszym założeniem na M. Jeśli M = {0}, twierdzenie jest prawdziwe przy m = 0. Jeśli nie, zbiór elementów > 0 w M nie może być pusty;. Wszystkie wielokrotności m są wtedy w M. Dla dowolnego x ∈ M, stosujemy lemat i zapisujemy x = my+r przy 0 ≤ r < m ; wtedy r = x-my jest w M. Ze względu na definicję m, implikuje to r = 0, x = my. Dlatego też M = mZ. Odwrotnie, ponieważ m jest najmniejszym elementem > 0 w mZ, jest jednoznacznie określony kiedy dane jest M.
Następstwo 1. Niech a,b,...,c będą liczbami całkowitymi w dowolnej (skończonej) liczbie. Wtedy jest jednoznaczna liczba całkowita d ≥ 0 taka ,że zbiór wszystkich liniowych połączeń ax + by +...+cz z a,b,...,c ze współczynnikami całkowitymi x,y,....,z jest zbiorem wszystkich wielokrotności d.
Dowód. Zastosujemy twierdzenie II.1 do tego zbioru.
Następstwo 2.Założenia i adnotacje będą takie samej jak w następstwie, d jest dzielnikiem każdej liczby całkowitej a,b,...c, a każdy wspólny dzielnik tych liczb całkowitych jest dzielnikiem d.
Dowód. Każda z tych liczb całkowitych a,b,...,c należy do zbioru ich kombinacji liniowych. Odwrotnie, każdy wspólny dzielnik a,b,...,c jest dzielnikiem dla dla każdej z ich liniowych kombinacji, stąd w szczególności d.
Definicja . Liczba całkowita d zdefiniowana w następstwach twierdzenia II.1 jest nazywana największym wspólnym dzielnikiem (lub w skrócie g.c.d.) a,b,...,c; jest to oznaczone przez (a,b,...,c). Ponieważ g.c.d. (a,b,...,c) należy do zbioru liniowych kombinacji z a,b,...,c (ponieważ jest to najmniejszym elementem > 0 tego zbioru, chyba ,że a,b,...,c są wszystkie zerami), może być zapisany w postaci
(a,b,...,c) = ax0 + by0 + ... + cz0
gdzie x0,y0,...,z0 wszystkie są liczbami całkowitymi.

ĆWICZENIA
II.1 Udowodnij ,że (a,b,c) = ((a,b),c) = (a,(b,c)).
II.2 Udowodnij ,że w "szeregu Fibonacciego" 1,2,3,5,8,13,..., w którym każdy wyraz po drugim jest sumą dwóch poprzedzających, każde dwa kolejne wyrazy mają g.c.d. równy jest 1
II.3 Jeśli p,q,r,s są liczbami całkowitymi takimi ,że ps - qr = ± 1, a a,b,a′,b′ są liczbami całkowitymi takimi ,że
a′ = pa + qb , b′ = ra + sb, udowodnij że (a,b) = (a′, b′) (Podpowiedź: rozwiąż ostatnie dwa równania dla a,b)
II.4 Niech a,b będą dwoma liczbami całkowitymi > 0. Umieść a0 = a ,a1 = b; dla n ≥ 1, definiujemy an+1 przez an-1 = anqn + an+1, 0 ≤ an+1 < an , o ile an > 0. Udowodnij ,że istnieje N ≥ 1 takie ,że aN+1 = 0 i ,że aN jest wtedy równe (a,b).
II.5 Przy adnotacjach z II.4, udowodnij ,że an może być zapisane w postaci ax + by, z całkowitymi x, y dla wszystkich n ≥ 0 i ≤ N
II.6 Użyj procedur opisanych w ćwiczeniach II.4 i II.5 ,najdź (a,b)i rozwiąż ax + by = (a,b)w każdym z poniższych przypadkach: (i) a = 56, b = 35; (ii) a = 309, b = 186; (iii) a = 1024, b = 729
II.7 Jeśli a,b,...,c,m są liczbami całkowitymi, i m > 0, wykaż ,że
(mn,mb,...,mc) = m(a,b,...,c)
II.8 Udowodnij ,że każda liczba wymierna może być zapisana w jeden i tylko jeden sposób jako m/n, przy (m,n) = 1 i n > 0

III

Definicja Liczby całkowite a,b,...,c są nazywane wzajemnie względnie pierwszymi jeśli ich g.c.d. jest to 1
Innymi słowy są one wzajemnie relatywnie pierwsze jeśli nie mają innych wspólnych dzielników niż 1. Jeśli dwie liczby całkowite a,b są wzajemnie względnie pierwsze , wtedy mówimy ,że a jest pierwsza do b, a b pierwszą do a; kiedy tak jest , każdy dzielnik a jest również pierwszy do b a każdy dzielnik b jest pierwszy do a.
Twierdzenie III.1. Liczby całkowite a,b,...,c są wzajemnie względnie pierwsze jeśli i tylko jeśli równanie ax + by + ... + cz = 1 ma rozwiązanie w liczbach całkowitych,y,...,z.
Faktycznie,jeśli (a,b,...,c) = 1 ,wtedy przez następstwo 1 twierdzenia II.1, wspomniane równanie ma rozwiązanie. Odwrotnie, jeśli ma rozwiązanie, wtedy każdy wspólny dzielnik d > 0 a,b,...,c musi dzielić się przez 1 i dlatego musi być 1.Następstwo Jeśli d jest g.c.d. liczb całkowitych a,b,..,c wtedy a/d, b/d,...,c/d są wzajemnie względnie pierwsze.
Wynika to od razu z faktu, że d może być zapisane w postaci ax0+by0+...+cz0.
Twierdzenie III.2 Jeśli a,b,c są liczbami całkowitymi takimi ,że a jest liczbą pierwszą do b i podzielną przez bc, wtedy jest podzielną przez c
Jeśli (a,b) = 1, możemy rozwiązać ax+by=1. wtedy mamy
c = c(ax+by) = a(cx) + (bc)y
Jeśli a jest podzielne przez oba wyrazy po prawej stronie, jest podzielne przez c.
Następstwo 1. Jeśli a,b,c są liczbami całkowitymi, i jeśli a jest liczbą pierwszą zarówno dla b i c, jest pierwszą dla bc.
Jeśli d jest dodatnim wspólnym dzielnikiem a i bc, jest pierwszy do b (ponieważ jest podzielne przez a) i musi również być podzielne przez c, według twierdzenia III.2 .Jeśli (a,c) = 1, d musi być 1
Następstwo 2. Jeśli liczba całkowita jest pierwsza dla każdej liczby całkowitej a,b,...,c, jest pierwsza dla ich iloczynu.
Wynika to z następstwa 1 przez indukcję na szereg czynników w tym iloczynie.

ĆWICZENIA
III.1 Jeśli (a,b) = 1 i zarówna a i b są podzielne przez c, wykaż ,że ab jest podzielne przez c
III.2 Jeśli m > 1 i a jest pierwsze do m, wykaż ,że reszty uzyskiwane przez podzielenie a, 2a,...,(m-1)a przez m są liczbami 1,2,..,m-1 w tym porządku.
III.3 Wykaż ,że jeśli N jest liczbą całkowitą > 0, albo jest "doskonałym kwadratem" (tj. postaci n2, gdzie n jest liczbą całkowitą > 0) lub √N nie jest liczbą wymierną (Podpowiedź: użyj ćwiczenia II.8)
III.4 Dowolna liczba całkowita > 1 która nie jest potęgą 2 może być zapisana jako suma (dwóch lub więcej) kolejnych liczb całkowitych.
III.5 Jeśli a,b są dodatnimi liczbami całkowitymi, i (a,b) = 1 , wykaż ,że każda liczba całkowita ≥ ab może być zapisana w postaci ax+by z dodatnimi liczbami całkowitymi x,y
III.6 Korzystając z ćwiczenia III.5 i indukcji na m, wykaż ,że jeśli a1,a2,...,am są dodatnimi liczbami całkowitymi i d = (a1,a2,...,am,), każda wystarczająco duża wielokrotność d może być zapisana w postaci a1x1 + a2x2 + ... + amxm, gdzie xi są liczbami całkowitymi dodatnimi.

IV

Definicja.Liczba całkowita p > 1 jest nazywana pierwszą jeśli nie ma innych dodatnich dzielników innych niż ona sama i 1.
Każda liczba całkowita > 1 ma przynajmniej jeden pierwszy dzielnik tj. najmniejszym dzielnikiem > 1 . Jeśli a jest liczbą całkowitą a p jest liczbą pierwszą ,wtedy albo p jest podzielna przez a lub jest pierwsza do a.
Twierdzenie IV.1. Jeśli liczba pierwsza dzieli się przez iloczyn liczb całkowitych,dzieli się przynajmniej przez jeden ze współczynników.
W przeciwnym razie będzie pierwszą dla wszystkich tych współczynników , i dlatego,według następstwa 2 z twierdzenia III.2, będzie pierwszą do ich iloczynu.
Twierdzenie IV.2 Każda liczba całkowita > 1 może być zapisana jako iloczyn liczb pierwszych; może być zapisana tylko w jeden sposób z wyjątkiem porządku współczynników.
Weźmy a > 1; nazwijmy p pierwszym dzielnikiem a. Jeśli a = p, twierdzenie jest prawdziwe dla a; jeśli nie, a/p jest > 1 i < a; jeśli pierwsze twierdzenie jest prawdziwe dla a/p, jest prawdziwe dla a. Dlatego też twierdzenie wynika przez indukcję na a. Drugie twierdzenie może być również udowodnione przez indukcję. Załóżmy ,że a jest zapisane na dwa różne sposoby jako iloczyn liczb pierwszych, powiedzmy jako a = pq...r i jako a = p′q′...s′ jeśli p dzieli się przez a, twierdzenie IV.1 implikuje ,że p musi dzielić się przez jeden z czynników pierwszych p′q′...s′, powiedzmy p′. Wtedy p = p′ ;zastosujemy drugą część twierdzenia do a/p, zobaczymy ,że q′...s′ muszą być takie same jak q,...,r, z wyjątkiem ich porządku,. Przez indukcję, to dowód dla drugiej części. Warto jest podać inny dowód. Zapiszemy a jako iloczyn liczb pierwszych, a=pq...r; niech P będzie dowolną liczbą pierwszą; niech n będzie ilością razy występowania P wśród współczynników p,q,...,r z a. Wtedy a jest wielokrotnością Pn; z drugiej strony, ponieważ a*P-n jest iloczynem liczb pierwszych innych niż P, nie jest wielokrotnością P, z twierdzenia IV.1, i dlatego też a nie jest wielokrotnością Pn+k. Zatem n jest jednoznacznie określone jako największa liczba całkowita taka ,że Pn dzieli się przez a; możemy zapisać n = vP(a). Zatem, dla dowolnych dwóch sposobów zapisania a jako iloczynu liczb pierwszych, muszą wystąpić ,te same liczby pierwsze i muszą wystąpić tą samą ilość razy w obu iloczynach; to ponownie dowodzi drugiej części naszego twierdzenia.
2 jest liczbą pierwszą; jest jedyną liczbą pierwszą parzystą; wszystkie pozostałe są nieparzyste. Pierwsze dziesięć liczb pierwszych to
2,3,5,7,11,13,17,19,23,29
Niech p1 =2,p2,p3,... będą wszystkie liczbami pierwszymi w ich naturalnym (tzn. rosnącym) porządku. Niech a będzie liczbą całkowitą ≥ 1; dla każdego i ≥ 1, niech αi będzie ilością razy wystąpienia pi wśród współczynników pierwszych a kiedy a jest zapisane jako iloczyn takich współczynników (z αi = 0 jeśli pi nie jest podzielne przez a).Wtedy mamy
a = p1α1p2α2 ... prαr
o ile weźmiemy r wystarczająco duże (tj. tak duże, że wszystkie odrębne dzielniki pierwsze a wystąpią wśród p1,p2,...,pr )
Twierdzenie IV.3. Jest nieskończenie wiele liczb pierwszych
Faktycznie, jeśli p,q,...,r są liczbami pierwszymi w dowolnej skończonej liczbie, dowolny pierwszy dzielniki z pq...r+1 musi być różny od p,q,...,r. (Jest to dowód Euklidesa dla tego twierdzenia )

ĆWICZENIA
IV.1 Niech n będzie liczbą całkowitą ≥ 1, a p liczbą całkowitą. Jeśli dla liczby wymiernej x oznaczmy przez [x] największą liczbę całkowitą ≤ x, wykaż ,że największa liczba całkowita N taka ,że pN dzielona przez n! jest dana przez
N = [n/p]+[n/p2]+[n/3]+....
IV.2 Udowodnij ,że jeśli a,b,...,c są liczbami całkowitymi ≥ 1,wtedy
(a+b+...+c)!/a!b!...c!
jest liczbą całkowita.
IV.3 Jeśli a,m,n są dodatnimi liczbami całkowitymi, i m ≠ n, wykaż ,że g.c.d. z a2m + 1 i a2n + 1 to 1 lub 2 w zależności czy a jest parzyste czy nieparzyste (Podpowiedź: skorzystaj z faktu ,że a2n - 1 jest wielokrotnością a2m + 1 dla n > m). Z tego dedukujemy istnienie nieskończenie wiele liczb pierwszych.
IV.4 jeśli a = pαqβ ... rγ , gdzie p,q,...,r są różnymi liczbami pierwszymi a α, β,..., γ są dodatnimi liczbami całkowitymi, udowodnij ,że liczba różnych dzielników a ,w tym a i 1 to
(α +1)(β +1)...(γ+1)
a ich suma to
pα+1 - 1 / p-1 * qβ+1 - 1 / q-1 ... rγ+1 - 1 / r-1
IV.5 Udowodnij ,że jeśli D jest liczbą różnych dzielników a, ich iloczyn to aD/2
IV.6 Jeśli n,a,b,...,c są liczbami całkowitymi > 1, wtedy liczba różnych liczb całkowitych w postaci aαbβ...cγ które są ≤ n (gdzie α,β...,γ) są dodatnimi liczbami całkowitymi to
&le (1 + logn/loga)(1+logn/logb)....(1+logn/logc)
Skorzystaj z tego faktu i faktu ,że


dla każdego r > 0, udowodnij ,że liczba liczb pierwszych jest nieskończona
IV.7 Jeśli (a,b) = 1 a a2 - b2 jest "doskonałym kwadratem", wykaż ,że albo a+b i a-b są doskonałymi kwadratami albo każdy jest dwukrotnie doskonałym kwadratem. (Podpowiedź: wykaż ,że g.c.d. a+b i a-b to 1 lub 2).

V

Definicja.Grupa przemienna (lub "abelowa") jest zbiorem G, razem z operacją binarną między elementami G, spełniająca poniższe aksjomaty ( w których operacja grupowa jest oznaczona przez +):
I. (Łączność).(x+y)+z = x + (y+z) dla wszystkich x,y,z w G
II. (Przemienność). x+y = y+x dla wszystkich x,y w G.
III. Jeśli x,y są w G, równanie x+z=y ma jednoznaczne rozwiązanie z w G(zapisane z = y - x)
IV. Jest element w G ,nazywany elementem neutralnym(i oznaczonym przez 0) taki ,że 0+x = x dla wszystkich x w G
Na przykład , liczby całkowite, liczby wymierne (i liczby rzeczywiste) są grupą przemienną w ramach operacji dodawania. Jest oczywiście wiele przypadków grup przemiennych gdzie operacja grupowa nie jest zapisana addytywnie tj. nie jest oznaczona przez +; wtedy zapis y-x w III i 0 w IV, są odpowiednio modyfikowane. Jeśli ta operacja jest zapisana jako mnożenie, wtedy zazwyczaj piszemy y/x, lub yx-1, dla elementu z w III i 1 dla elementu neutralnego w IV. Nie zerowe liczby wymierne dają przykład grupy przemiennej w ramach operacji mnożenia. U nas żadne grupy nie wystąpią inne niż przemienne; dlatego też słowo "przemienna" będzie najczęściej pomijane. Podzbiór grupy G który tworzy grupę w ramach tej samej operacji bitowej co G jest nazywany podgrupą G. Jeśli G jest zapisywana addytywnie, podzbiór G jest podgrupą jeśli i tylko jeśli jest zamknięty pod względem dodawania i odejmowania , lub nawet tylko pod względem odejmowania. Twierdzenie II.1 może być wyrażone zwięźle przez powiedzenie ,że każda podgrupa Z jest postaci mZ z m ≥ 0
Definicja.Jeśli m,x,y są liczbami całkowitymi i m > 0, x i y są kongruentne modulo m jeśli x-y jest wielokrotnością m; wtedy piszemy x ≡ y (mod m), lub krócej x ≡ y (m)
Lemat w II pokazuje ,że każda liczba całkowita jest kongruentna modulo m do jednej i tylko jednej liczby całkowitej 0,1,...,m-1, i ,że dwie liczby całkowite są kongruentne modulo m jeśli i tylko jeśli mają tą samą resztę w dzieleniu przez m. Związek kongruencji modulo m ma poniższe właściwości:
(A)(Zwrotność) x ≡ x (mod m)
(B) (Przechodniość) x ≡y i y≡z (mod m) implikuje x ≡ z (mod m)
(C) (Symetria) x ≡ y (mod m) implikuje y ≡ x (mod m)
(D) x ≡ y, x′ ≡ y′ (mod m) implikuje x ± x′ ≡ y ± y′ (mod m)
(E) x ≡ y, x′ ≡ y′ (mod m) implikuje xx′ ≡ yy′ (mod m)
(F) Niech d > 0 dzieli się przez m, x i y; wtedy x ≡ y (mod m) jeśli i tylko jeśli x/d ≡ y/d (mod m/d)
Co do (E), jest konsekwencją tożsamości
xx′ - yy′ = x(x′ - y′) + (x-y)y′
weryfikacja wszystkich pozostałych stwierdzeń jest bezpośrednia. Właściwości (A),(B),(C) są wyrażone przez powiedzenie ,że relacja kongruencji modulo m jest "relacją równoważności" między liczbami całkowitymi.
Definicja Klasa kongruencji liczb całkowitych modulo m jest zbiorem składającym się ze wszystkich liczb całkowitych , które są kongruentne to danego modułu m. Jeśli x jest liczbą całkowitą, piszemy (x mod m) (lub po prostu (x) jeśli żadna niejednoznaczność nie wystąpi) dla klasy kongruencji liczb całkowitych kongruentnych do x modulo m. Przy (A), x należy do tej klasy (x mod m); jest nazywane przedstawicielem tej klasy. Z (A),(B),(C) wynika ,że dwie klasy (x mod m), (y mod m) zbiegają się jeśli x ≡ y (mod m) i sa rozłączne (tj nie mają wspólnego elementu) w przeciwnym razie. Zatem zbiór wszystkich liczb całkowitych jest rozdzielony na m rozłącznych klas (0 mod m),(1 mod m),...., (m-1 mod m). Definiujemy dodawanie klasy kongruencji prze :
(x mod m) + (y mod m) = (x+y mod m)
ma to sens ,dla (D) pokazującego ,że prawa strona zależy tylko od dwóch klas po lewej stronie i nie zależy od wyboru reprezentantów x,y dla tych klas
Twierdzenie V.1 Dla dowolnej liczby całkowitej m > 0, klasy kongruencji modulo m, według dodawania, tworzą grupę przemienną m elementów.
Równanie
(x mod m) + (z mod m) = (y mod m)
dla danych x,y ma jednoznaczne rozwiązanie (y-x mod m) i ,że (0 mod m) ma właściwość wymaganą dla elementu neutralnego.

ĆWICZENIA
V.1 Jeśli x1,...,xm to m liczb całkowitych, wykaż, że suma odpowiedniego niepustego podzbioru tego zbioru jest wielokrotnością m (Podpowiedź: rozważ różne klasy modulo m wśród tych określonych przez 0,x1,x1+x2,x1+x2+...+x1+x2+...+xm)
V.2 Udowodnij ,że każdy "doskonały kwadrat"jest kongruentny do 0,1 lub 4 modulo 8.
V.3 Udowodnij przez indukcję ,że jeśli n jest dodatnią liczbą całkowitą,l wtedy 22n+1 ≡ 9n2 - 3n +2 (od 54)
V.4 Wykaż, że jeśli x,y,z są liczbami całkowitymi i x2 + y2 = z2, wtedy xyz ≡ 0 (mod 60)
V.5 Jeśli x0,x1,...,xn są liczbami całkowitymi, wykaż ,że
x0 + 10x1+...+10nx0 ≡ x0 + x1 + ... + xn (mod 9)
V.6 Wykaż ,że konieczny i wystarczający warunek dla pary kongruencji x ≡ a (mod m), x ≡ b (mod m) mający rozwiązanie, jest taki ,że a ≡ b (mod d), gdzie d = (m,n). Jeśli c = 1, wykaż ,że rozwiązanie jest jednoznaczne modulo mn.
V.7 Jeśli n jest liczbą całkowitą > 0, wykaż ,że n+1 z pierwszych 2n liczb całkowitych zawiera parę x,y taką, że y/x jest potęgą 2 (Podpowiedź: dla każdego z danych liczb całkowitych x0, x1,..., xn, wywołaj xi największego nieparzystego dzielnika xi i wykaż ,że przynajmniej dwa z nich muszą być równe)
V.8 Kiedy x,y są dwoma liczbami całkowitymi > 0, piszemy x ~ y jeśli y/x jest potęgą 2 tj. w postaci 2n z n ∈ Z; wykaż ,że jest to relacja równoważności, i ,że x ~ y jeśli i tylko jeśli nieparzyste dzielniki x są takie same jak te z y.

VI

Jeśli m jest liczbą całkowitą > 0, definiujemy mnożenie klas kongruencji przez:
(x mod m) * (y mod m) = (xy mod m),
właściwość(E) pokazuje ,że prawa strona zależy tylko od tych dwóch klas po lewej stronie i nie zależy od wyboru ich reprezentacji x,y
Definicja.Pierścień jest zbiorem R, razem z dwoma operacjami binarnymi, dodawaniem (zapisanym przez +) i mnożeniem (zapisanym przez * lub x), spełniającym następujące aksjomaty:
I. Przy dodawaniu, R jest grupą
II. Mnożenie jest łączne , przemienne i rozdzielne w odniesieniu do dodawania: (xy)z = x(yz), xy = yz, x(y+z) = xy + xz dla wszystkich x,y,z
Jeśli R jest pierścieniem wtedy z prawa łączności
(x*0) + (xz) = x(0+z) = xz
tak ,że x*0 = 0 przez właściwość grupy addytywnej. Podobnie x*(-y) = -xy. Jeśli jest w R element e taki ,że ex = x dla wszystkich x, jest to jednoznaczne; jeśli f jest również takie, wtedy ef = f i ef = fe = e. Taki element jest nazywany elementem jednostkowym i często jest oznaczany przez 1R lub przez 1; pierścień jest nazywany unitarnym (jednostkowym) jeśli ma element jednostkowy. Zbiór Z liczb całkowitych i zbió Q liczb wymiernych są pierścieniami unitarnymi
Twierdzenie VI.1 Dla dowolnej liczby całkowitej m > 0, klasy kongruencji modulo m, według dodawania i mnożenia, tworzy pierścień unitarny m elementów.
Weryfikacja jest bezpośrednia. Element jednostkowy jest klasą kongruencji (1 mod m); dla tej klasy, zazwyczaj piszemy 1 , i 0 dla klasy (o mod m); mamy 1 ≠ 0 chyba ,że m = 1. Przykład m = 6 pokazuje ,że w pierścieniu jednostkowym xy mogą być 0 bez x lub y będących 0 (bierzemy dla x,y klasy 2 i 3 modulo 6); kiedy tak jest, x i y są nazywane dzielnikami zera . Pierścienie Z ,Q są bez dzielników zera. Jeśli a jest liczbą pierwszą do m, a a′ = a +mt, wtedy każdy wspólny dzielnik a′ i m musi również dzielić się przez a = a′ - mt; pokazuje to ,ze wszystkie liczby całkowite w klasie kongruencji (a mod m) są wtedy pierwszymi do m. Taka klasa będzie nazywana pierwszą do m. Jeśli (a mod m), (b mod m) oba są pierwszymi do m, więc jest (ab mod m) przez następstwo 1 twierdzenia III.2; w szczególności takie klasy nie mogą być dzielnikami zera w pierścieniu klas kongruencji modulo m.
Twierdzenie VI.2 Niech m,a,b będą liczbami całkowitymi, z m > 0; wstawiamy d = (a,m). Wtedy kongruencja ax ≡ b (mod m) ma albo dokładnie d rozwiązań modulo m, lub nie ma rozwiązań; ma rozwiązanie jeśli i tylko jeśli b ≡ 0 (mod d); są dokładnie m/d różnych wartości b modulo m.
Faktycznie, x jest rozwiązaniem jeśli i tylko jeśli jest liczba całkowita y taka ,że ax-b = my, tj,. b = ax - my; według następstwa 1 twierdzenia II.1, ma rozwiązanie jeśli i tylko jeśli d dzieli się przez b, tj. b = dz; uzyskujemy wszystkie różne wartości b modulo m tej postaci dając do z wartości 0,1,..., m/d-1. Jeśli x jest rozwiązaniem ax ≡ b (mod m), wtedy x′ jest również rozwiązaniem jeśli i tylko jeśli a(x′ - x) ≡ 0 (mod m); z właściwości (F) kongruencji, jes tto równoważne a/d(x′-x) ≡ 0 (mod m/d), i dlatego x′ ≡ x (mod m/d) z twierdzenia III.2 i następstwa twierdzenia III.1 .To pokazuje ,że wszystkie rozwiązania ax′ ≡ b (mod m) może być zapisane jako x′ = x +m/d * u; rożne rozwiązania modulo m są potem uzyskiwane przez podanie u wartości 0,1,..,d-1
Następstwo Klasy kongruencji pierwsze do modulo m tworzy grupę względem mnożenia.
Wynika stąd od razu z następstwa 1 twierdzenia III.2, z twierdzenia VI.2 i z faktu ,że klasa (1 mod n) jest elementem neutralnym dla mnożenia w pierścieniu klas kongruencji modulo m.
Definicja. Dla liczby całkowitej m > 0, liczba klas kongruencji pierwszych do m modulo m jest oznaczona przez φ(m),a φ jest nazywane funkcją Eulera
Zgodnie z tym, mamy
φ(1) = φ(2) = 1, φ(3)=φ(4) = 2 , φ(5) = 4 itd.
Jeśli m ≥ 2, φ(m) może być również zdefiniowana ajko liczba pierwszych liczb całkowitych dodatnich do m i ≤ m-1. Jeśli p jest pierwsza, φ(p) = p-1.
Definicja Pole jest pierścieniem którego elementy nie zerowe tworzą grupę względem mnożenia
Pierścień Q liczb wymiernych jest polem; pierścień Z liczb całkowitych nie jest polem. Pole nie ma dzielników zera; przykład Z pokazuje ,że konwersja nie jest prawdziwa
Twierdzenie VI.3 Dla dowolnej liczby całkowitej m > 1, pierścień klas kongruencji modulo m jest polem jeśli i tylko jeśli m jest liczbą pierwszą.
Jeśli m jest liczbą pierwszą, wszystkie klasy modulo m,inne niż 0, są pierwsze do m i dlatego tworzą grupę multiplikatywną, przez następstwo twierdzenia VI.2. Z drugiej strony, jeśli m nie jest liczbą pierwszą, ma dzielnik d który jest > 1 i < m; wtedy 1 < m/d < m, tak ,że kasy (d mod m), (m/d mod m) nie są 0 podczas gdy ich iloczyn to 0. Dlatego też są dzielnikami zera a pierścień modulo m nie jest polem. Jeśli p jest liczbą pierwszą, pole klas kongruencji modulo p będzie oznaczone przez Fn; ma p elementów

ĆWICZENIA
VI.1 Jeśli F(X) jest wielomianem z całkowitymi współczynnikami, i jeśli x ≡ y (mod m), wykaż ,że F(x) ≡ F(y) (mod m)
VI.2 Rozwiąż parę kongruencji
5x - 7y ≡ 9 (mod 12), 2x + 3y ≡ 10 (mod 12);
wykaż ,że rozwiązanie jest jednoznaczne modulo 12
VI.3 Dla wszystkich wartości a i b modulo 2 , rozwiąż
x2+ax+b≡ 0 (mod 2)
VI.4 Rozwiąż x2 - 3x + 3 ≡ 0 (mod 7)
VI.5 Jeśli m > 1, wykaż ,że średnia arytmetyczna wszystkich pierwszych dodatnich liczb pierwszych do m i < m to m/2
VI.6 Jeśli m jest liczbą całkowita nieparzystą, udowodnij ,że
1m + 2m + ... + (m-1)m ≡ 0 (mod m)
VI.7 Jeśli m, n są liczbami całkowitymi > 0, i (m,n) = 1, udowodnij ,że φ(mn) = φ(m)φ(n)(Podpowiedź: skorzystaj z ćwiczenia V.6)
VI.8 Wykaż ,że , jeśli m > 1 i p,1,...,r są wszystkie różnymi pierwszymi dzielnikami m, wtedy
φ(m) = m(1- 1/p)(1-1/q)...(1-1/r)
VI.9 Jeśli p jest liczbą pierwszą, udowodnij przez indukcję na m, używając formuły binomialnej, że np ≡ n (mod p) dla wszystkich liczb całkowitych n
VI.10 Jeśli p jest liczbą pierwszą, a n > 0, udowodnij przez indukcję na n ,że jeśli a ≡ b (mod p), wtedy apn ≡ bpn (mod pn=1)
VI.11 Jeśli p jest nieparzystą liczbą pierwszą, i x2 ≡ x2 (mod p), wykaż ,że x jest kongruentne albo do y albo do -y modulo p, ale nie do obu, chyba ,że p jest podzielne przez x i y; zatem konkludujemy ,że x2 ≡ a (mod p) ma rozwiązanie x dla dokładnie połowy liczb całkowitych a wśród 1,2,...,p-1
VI.12 Wykaż ,że liczby w postaci x + y√2, gdzie x i y są liczbami całkowitymi, tworzy pierścień; jeśli x,y są w zakresie wszystkich liczb wymiernych. wykaż ,że tworzą one pole.

VII

Z definicji grupy i podgrupy wynika jasno ,że część wspólna podgrupy grupy G (w liczbie, skończonej lub nie) jest ponownie podgrupą G.
Definicja.Niech a,b,...,c będą elementami grupy G. Wtedy część wspólna G′ wszystkich podgrup G (w tym sama G), która zawiera a,b,...,c, mówimy ,że jest generowana przez a,b,..,c i są generatorami G′
Może być to również wyrażone przez stwierdzenie ,że G′ jest najmniejszą podgrupą G ,zawierając a,b,...,c; może się zdarzyć ,że nie ma innych niż G. Niech G będzie grupa, x elementem G, i wywołujemy Gx, podgrupę generowaną przez x. Przypuśćmy ,ze G jest zapisane addytywnie. Jak zwykle, zapisujemy -x dla 0 -x; musi to być w Gx. Również zapisujemy 0*x dla 0; dla każdej liczby całkowitej n > 0, zapisujemy nx dla sumy x+x+...+x n wyrazów wszystkich równych x,i (-n)x dla -(nx); przez indukcje na n, wszystkie muszą być w Gx. Również przez indukcję, weryfikujemy jednocześnie formuły
mx + nx = (m+n)x , m(nx) = (mn)x
dla wszystkich m,n w Z. Pierwsza formuła pokazuje ,że elementy nx , dla n ∈ Z, tworzą podgrupę G; wyraźnie, nie ma innej niż Gx. Dla wygody określimy to jako twierdzenie tylko w przypadku kiedy G jest zapisywane multiplikatywnie; wtedy zapisujemy x0 dla elementu neutralnego 1 z G, x-1 dla elementu x′ definiujemy przez x′x = 1, xn dla iloczynu x*x*...*x n czynników równych x,a x-n dla (xn)-1
Twierdzenie VII.1 Niech G będzie grupa względem mnożenia; wtedy , dla każdego x ∈ G, podgrupa G generowana przez x składa sie z elementów xn dla n ∈ Z. G i x będące jak w twierdzeniu VII.1, wywołują Mx zbiór tych liczb całkowitych a dla których xa = 1. Jeśli x0 = 1 , Mx nie jest pust. Mamy również dla wszystkich liczb całkowitych a,b:
xa-b = xa*(xb)-1
co pokazuje ,że xa = xb jeśli i tylko jeśli a - b jest w Mx; w szczególności, Mx jest zamknięty względem odejmowania. Dlatego Mx spełnia te założenia w twierdzeniu II.1 (innymi słowy, jest to podgrupa grupy addytywnej Z) i składa się z wielokrotności pewnych liczb całkowitych m &ge> 0; jeśli m nie jest 0, jest to najmniejsza liczba całkowita > 0 , taka, ze xm = 1. Zatem, jeśli m=0 , wszystkie elementy xa są różne; jeśli m > 0, xa jest takie same jak xb jeśli i tylko jeśli a ≡ b (mod m).
Definicja Izomorfizm między dwoma grupami G,G′ jest odpowiedniością wzajemnie jednoznaczną ("bijekcją") między elementami G a tymi z G′, transformacja operacji grupy w G na operację grupy w G′. Kiedy jest taka odpowiedniość , G i G′ są izomorficzne. Pojęcie izomorfizmu może być przenoszone w sposób oczywisty na pierścienie i pola. Przy tej definicji, uzyskane wyniki mogą być przeformułowane jak następuje:
Twierdzenie VII.2 Niech G będzie grupą względem mnożenia, generowaną przez pojedynczy element x. Wtedy albo G jest nieskończone a przekształcenie xa → a jest izomorfizmem G na grupę addytywną Z, albo składa się ze skończonej liczby m elementów, a wtedy przekształcenie xa → (a mod m) jest izomorfizmem G na grupę addytywną klasy kongruencji modulo m w Z.
Oczywiści ,jeśli G jest dowolną grupa a x dowolnym elementem G, twierdzenie VII.2 może być zastosowane do podgrupy G wygenerowanej przez x.
Definicja. Liczba elementów grupy skończonej jest nazywana jej rzędem. jeśli grupa skończonego rzędu jest generowana przez pojedynczy element, jest nazywana cykliczną; jeśli element x grupy, generuje grupę skończonego rzędu m, m jest nazywane rzędem x.

ĆWICZENIA
VII.1 Jeśli F jest polem skończonym, wykaż ,że podgrupa grupy addytywnej F generowanej przez 1 jest pierwszego porządku p i jest subpolem F, izomorficznym do pola Fp klasy kongruencji modulo p
VII.2 Wykaż ,że niepusty skończony podzbiór S grupy G jest podgrupą G jeśli i tylko jeśli jest zamknięta względem operacji grupy (Podpowiedź: jeśli a ∈ S, wtedy a → ax jest bijekcją S na samo S)
VII.3 Wykaż ,że skończony pierścień jest polem jeśli i tylko jeśli nie ma dzielników zera
VII.4 Jeśli G jest grupą (przemienną) a n liczbą całkowitą, wykaż ,że elementy xn , dla x ∈ G, tworzy podgrupę G
VII.5 Jeśli G′ , G″ są podgrupami grupy (przemiennej) G ,wykaż ,że elementy x′x″ z x′; ∈ G′ , x″ ∈ G″, tworzy podgrupę G
VII.6 Niech G będzie grupą (przemienną), x elementem G rzędu m a y elementem G rzedu n. Wykaż ,że jeśli (m,n) = 1, wtedy xayb = 1 jest xa jeśli i tylko jeśli xa = yb = 1: zatem wykaż ,że grupa generowana przez x i y jest cykliczna rzędu mn, generowaną przez xy
VII.7 Wykaż ,że jeśli m > 2 , n > 2 i (m,n) = 1, grupa multiplikatywna klasy kongruencji pierwszej do mn modulo mn nie jest cykliczna (Podpowiedź: użyj ćwiczenia V.6 i faktu ,że grupa cykliczna ma co najmniej jedną podgrupę rzędu 2)
VII.8 Znajdź wszystkie wartości n dla których grupa multiplikatywna nieparzystych klas kongruencji modulo 2n jest cykliczna
VII.9 Wykaż ,że jeśli G jest grupą (przemienną), a n liczbą całkowitą > 0, elementy G których rząd podzielny przez n tworzy podgrupę z G.
VII.10 Wykaż ,że ,jeśli G jest skończoną grupą (przemienną), iloczyn wszystkich elementów G jest 1 lub elementem rzędu 2
VII.11 Jeśli p jest liczbą pierwszą, wykaż ,że (p-1)! ≡ -1 (mod p)(Podpowiedź: rozważ grupę multiplikatywną modulo p)

VIII

Twierdzenie II.1 pokazuje,że każda podgrupa M z Z jest albo 0 albo generowana przez jej najmniejszy element m > 0; w drugim przypadku jest generowany przez m lub również przez -m, ale nie przez inny element M. dla grup cyklicznych mamy:
Twierdzenie VIII.1 Niech G będzie grupą cykliczną rzędu m, generowaną przez element x. Niech G′ będzie podgrupą G; wtedy jest dzielnik z m taki ,że G′ jest grupą cykliczną rzędu m/d generowany przez xd
Niech M będzie zbiorem takich liczb całkowitych a dla których xa ∈ G′. Formuła xa-b =(xa) * (xb)-1 pokazuje ,ż eM jest podgrupą Z; jeśli zawiera m , składa się z wielokrotności dzielnika d z m. Dlatego też G′ składa się z elementów xda z a ∈ Z, tj. jest generowany przez xd. Mamy xda = xdb jeśli i tylko jeśli da ≡ db (mod m); z właściwości (F) relacji kongruencji, jest to równoważne a ≡ b (mod m/d)Następstwo 1. Dla każdego dodatniego dzielnika n z m, grupa cykliczna rzędu m a jedną i tylko jedna podgrupę rzędu n.
Niech G będzie takie jak w twierdzeniu VIII.1, i wstaw d = m/b; z tego twierdzenia, jeśli G′ jest podgrupą G rzędu n, musi być wygenerowana przez xd, a xd generuje taką podgrupę.
Następstwo 2. G,m,x,G′ będą jak w twierdzeniu VIII.1, element xa G generuje G′ jeśli i tylko jeśli (a,m) = d.
Jeśli (a,m) = d , xa jest w G′ co więcej, z twierdzenia VI.2 możemy rozwiązać at ≡ d (mod m) i wtedy mamy xd = (xa)1 tak więc grupa generowana przez xa zawiera xd a zatem G′
Następstwo 3. G,m,x będą jak powyżej, xa generuje G jeśli i tylko jeśli (a,m) = 1 i G ma dokładnie φ(m) różnych generatorów.
Następstwo 4 Dla każdej liczby całkowitej m > 0, mamy

(tu suma po lewej stronie przybiera wszystkie dodatnie dzielniki d z m). Rozważmy grupę cykliczną G rzędu m (tj. grupa addytywna kongruencji klas modulo m). Z następstwa 1 dla każdego dzielnika d z m, G ma dokładnie jedną podgrupę Gd rzędu d a d → Gd jest odpowiedniością wzajemnie jednoznaczną między dzielnikami m a podgrupami G. Dla każdego d, wywołujemy Hd zbiór wszystkich różnych generatorów Gd, których liczba jest φ(d) z następstwa 3. Każdy element G należy do jednego i tylko jednego zbioru Hd,ponieważ generuje jedną i tylko jedną podgrupę z G. Niech G będzie grupą a X podzbiorem G; dla każdego a ∈ G, zapisujemy aX dla zbioru elementów ax z x ∈ X. Definicja grupy implikuje ,że x → ax jest bijekcją X na aX, tak ,że jeśli X jest skończony, wszystkie zbiory aX mają taką samą liczbę elementów jak X.
Definicja. Jeśli G jest grupą a H podgrupą z G, każdy zbiór w postaci xH z x ∈ G jest nazywany warstwą H w G.
Lemat. Niech xH, yH będą dwoma warstwami podgrupy H z grupy G; wtedy albo nie mają elementu wspólnego lub xH = yH.
Jeśli mają wspólny element , może to być zapisane jak xh z h ∈ H i również jako yh′ z h′ ∈ H. daje to y-1 = h′H-1 ∈ H, a zatem xH = y*(y-1x)H = y*(h′h-1 = yH.
Twierdzenie VIII.2. Jeśli H jest podgrupą grupy skończonej G, rząd H dzieli się przez rząd G
Faktycznie, każdy element x z G należy do jakiejś warstwy H (tzn. do xH), i, wynika z lematu, tylko do jednej. Jeśli liczba elementów każdej warstwy jest równa rzędowi H, rząd G musi być wielokrotnością tej liczby
Następstwo. Jeśli x jest dowolnym elementem grupy rzędu m, jej rząd dzieli się przez m, a xm = 1
Jeśli rząd d z x jest rzędem podgrupy G wygenerowanej przez x, twierdzenie VIII.2 pokazuje ,że dzieli się przez m. wtedy xm = (xd)m/d = 1
Twierdzenie VIII.3. Jeśli m jest liczbą całkowita > 0 a x liczbą całkowita pierwszą do m, wtedy xφ(m) ≡ 1 (mod m)
Jest to specjalny przypadek powyższego następstwa, kiedy jest stosowane do grupy multiplikatywnej klasy kongruencji pierwszej do m modulo m.
Następstwo.Jeśli p jest liczbą pierwszą, wtedy xp-1 ≡ 1 (mod p) dla każdego x pierwszego do p, a xp ≡ x (mod p) dla każdego x
Pierwsze założenie jest specjalnym przypadkiem twierdzenia VIII.3, a drugi jest bezpośrednim następnikiem. Następstwo było znane Fermatowi i jest znane jako twierdzenie Fermata; dowód został po raz pierwszy przez Eulera, który dał również dowód na twierdzenie VIII>3 , które jest znane jako twierdzenie Eulera

ĆWICZENIA
VIII.1 Jeśli G jest grupą rzędu m i jeśli n jest liczbą pierwszą do m, wykaż ,że każdy element G może być zapisany w postaci xn z pewnym x ∈ G
VIII.2 Jeśli p jest liczbą pierwszą, wykaż ,że każda grupa rzędu pn, z n > 0, zawiera element rzędu p, i że każda grupa rzędu p jest cykliczna
VIII.3 Jeśli p jest nieparzystym pierwszym dzielnikiem a2* + 1, z n≥ 1, wykaż ,że p ≡ 1 (mod 2n+1)
VIII.4 Jeśli a,b są liczbami całkowitymi > 0, i a 2α5βm , z m pierwszym do 10, wykaż ,że ułamek dziesiętny dla b/a ma okres liczbowy którego cyfry dzielą się przez φ(m); wykaż ,że jeśli nie ma okresu mniejszego niż m-1 cyfr, wtedy m jest liczbą pierwszą

IX

Aby rozważać wielomiany ze współczynnikami w polu Fp i równaniami nad takim polem ,zaczniemy od przejrzenia pewnych elementarnych właściwości wielomianów nad arbitralnym polem; są niezależne od natury tego pola, i całkiem analogiczne do właściwości liczb całkowitych podanych powyżej. Tu będziemy rozpatrywać pole K jako stałe raz dla wszystkich. Wielomian P nad K (tj. ze współczynnikami w K), w jednym nieoznaczonym X, jest podany wyrażeniem
P(X) = a0 + a1X + ...+ anXn
z a0,a1,...,an w K. Jeśli an ≠ 0 ,mówimy ,że P będzie stopnia n, i zapisujemy n = deg(P); każdy wielomian z wyjątkiem 0 ma stopień. Dodawanie i odejmowanie będzie zdefiniowane w zwykły sposób, takie wielomiany tworzą pierścień, zwykle zapisujemy K[X]. Jeśli P,Q są wielomianami niezerowymi, wtedy deg(PQ) = deg(P) + deg(Q).
Lematniech A,B będą dwoma wielomianami , z B ≠ 0, wstawiamy m = deg(B). Wtedy jest jednoznaczny wielomian Q taki ,że A - BQ to 0 lub stopnia < m.
Jeśli A = 0, nie ma nic do udowodnienia; przechodzimy przez indukcję na n = deg(A): najpierw udowodnimy istnienie Q . Jeśli n < m, bierzemy Q = 0. W przeciwnym razie ,wywołujemy bXm, wyraz stopnia m w B, i aXn wyrazem stopnia n w A; ponieważ wielomian A′ = A - B*(a/b Xn-m) jet stopnia < n, możemy zapisać go jako BQ′ + R z R = 0 lub stopnia < m przy założeniu indukcji. Wtedy A = BQ + R, z Q = Q&prime + a/b*Xn-m .Dla jedności Q, niech A-BQ i A-BQ1 będą 0 lup stopnia < m;wtedy to samo jest prawdziwe dla B(Q - Q1); ponieważ jest to stopień m+deg(Q-Q1), chyba,że Q-Q1 to 0, Q musi być takie samo jak Q1. Jeśli R = 0,A =BQ, mówimy ,że A będzie wielokrotnością B a B dzielnikiem A. Jeśli B = X-a, R musi być 0 lub stopnia 0, tj. "stałe" (element K), tak więc możemy zapisać
A = (X-a)Q+r
z r ∈ K. Zastępując a dla X po obu stronach, otrzymamy A(a) = r; jeśli jest to 0, a jest nazywane pierwiastkiem z A.
Twierdzenie IX.1 Niech ℜ będzie niepustym zbiorem wielomianów (nad K), zamkniętych względem dodawania i takim ,że jeśli A jest w ℜ wszystkie wielokrotności A są w ℜ. Wtedy ℜ składa się ze wszystkich wielokrotności pewnego wielomianu D, jednoznacznie określonego do mnożenia przez niezerową stałą. Jeśli ℜ = {0}, twierdzenie jest prawdziwe z D = 0. W przeciwnym razie bierzemy w ℜ wielomianu D ≠ 0 najmniejszego stopnia d. Jeśli A jest w ℜ, możemy zastosować ten lemat do A i D i zapisujemy A = DQ+R, gdzie R jest 0 lub stopnia < d. Wtedy R = A +D*(-Q) jest w ℜ, zatem 0 z definicji D, i A = DQ. jeśli D1 ma tą samą właściwość co D, wtedy jest wielokrotnością D a D jest wielokrotnością D1, tak że mają ten sam stopień; zapisujemy wtedy D1 = DE, widzimy ,że E jest stopnia 0, tj, stałą niezerową. Wywołujemy aXd wyraz stopnia d w D; wśród wielomianów różniących się od D tylko współczynnikiem stałej niezerowej, jest jeden i tylko jeden z najwyższym współczynnikiem 1, tzn. a-1D; taki wielomian będzie nazywany znormalizowanym. Możemy zastosować twierdzenie IX.1 do zbioru ℜ liniowych kombinacji AP + BQ + ...+CR dowolnej liczby danych wielomianów A,B,...,C; tu P,Q,...R oznaczają dowolne wielomiany. Jeśli wtedy ℜ składa się z wielokrotności D, gdzie D jest albo 0 albo znormalizowanym wielomianem, będziemy wywoływać g.c.d. A,B,..,C i będziemy oznaczać przez (A,B,..,C). Jak w II, D jest dzielnikiem A,B,...,C i każdy wspólny dzielnik A,b,...,C będzie się dzielić przez D. Jeśli D = 1, wtedy A,B,...,C będziemy nazywać wzajemnie względnie pierwszymi; są, jeśli i tylko jeśli są wielomianami P,Q,...,R takie ,że
AP + BQ + ...+ CR = 1 0 będzie pierwszy lub nieprzywiedlny, jeśli nie ma dzielnika stopnia > 0 i < n. Każdy wielomian stopnia 1 jest nieprzywiedlny. Powinieneś zauważyć ,że właściwość wielomianu będącego nieprzywiedlnym musi być zachowana kiedy zmienia się pole podstawowe: na przykład X2 + 1 jest nieprzywiedlny nad Q i również nad polem liczb rzeczywistych, ale nie nad polem liczb złożonych, ponieważ X2 + = (X+i)(X-i). Dokładnie jak w IV, możemy udowodnić teraz, że każdy wielomian stopnia > 0 może być zapisany, szczególnie jednoznacznie, jako iloczyn wielomianów pierwszych
Twierdzenie IX.2. Niech A będzie wielomianem stopnia n > 0 nad K; można to zapisać, jednoznacznie do rzędu współczynników w postaci
A = (X-a1)(X-a2)...(X-am)Q,
gdzie 0 ≤ n, a1,a2...am są w K , a Q jest bez pierwiastka w K.
Jeśli A nie ma pierwiastka, to jest jasne; w przeciwnym razie używamy indukcji na n. Jeśli A ma pierwiastek a, zapisujemy A =(X-a)A′; ponieważ A′ jest stopnia n-1, możemy zastosować to twierdzenie do niego; zapisujemy A′ w określonej formie, uzyskujemy podobny iloczyn dla A. Jeśli A może być zapisane jak powyżej jak i
A = (X-b1)(X-b2)...(X-art)R,
gdzie R nie ma pierwiastka w K, wtedy pierwiastek a z A musi występować wśród ai i również wśród bj, a potem, dzielimy przez X - a, uzyskujemy dla A′ dwa iloczyny które , przez założenie indukcji muszą się zbiegać.
Następstwo. Wielomian stopnia n > 0 ma co najmniej n różnych pierwiastków.

ĆWICZENIA
IX.1 Znajdź g.c.d. wielomianów nad Q:
X5 - X4 - 6X3 - 2X2 + 5X + 3, X3 - 3X -2
Znajdź również ich g.c.d. nad polem F3 jeśli współczynniki są interpretowane jako klasa kongruencji modulo 3.
IX.2 Wykaż ,że X4+1 jest wielomianem pierwszym nad Q, ale ma dzielnik stopnia 2 nad polem zdefiniowanym w ćwiczeniu VI.12
IX.3 Niech K będzie polem a R podpierścieniem K[X] zawierającym K. Udowodnij ,że istnieje skończony zbiór wielomianów P1,P2,...,Pn w R ,takim ,że R składa się ze wszystkich wielomianów w P1,P2,...,Pn ze współczynnikami w K(Podpowiedź: wywołaj d g.c.d. stopni wszystkich wielomianów w R, weź P1,P2,...,Pm w R takie ,że g.c.d ich stopni to d, a potem zastosuje konkluzje w ćwiczeniu III.6).

X

Lemat. Niech G będzie grupą rzędu m. Jeśli dla każdego dzielnika d z m, nie ma więcej niż d elementów z G spełniających xd = 1, G jest cykliczne.
Dla każdego dzielnika d z m,wywołujemy Ψ(d) liczby elementów rzędu d w G; musimy udowodnić ,że Ψ(m) > 0. W dowolnym przypadku, ponieważ każdy element z G ma rząd który dzieli się przez m, mamy

Jeśli, dla pewnego d, Ψ(d) > 0 ,wtedy G ma element rzędu d, a to generuje grupę cykliczną G′ rzędu d. Jeśli wszystkie d elementy G′ spełniają xd = 1, nasze założenie na G implikuje ,że wszystkie Ψ(d) elementów z G rzędu d są w G′ z następstwa 3 twierdzenia VIII.1, jest dokładnie φ(d) takich elementów. Dlatego też, jeśli Ψ(d) nie jest 0, ma wartość φ(d). Ponieważ ΣΨ(d) ma wartość m a Σφ(d) ma taką samą wartość z następstwa 4 twierdzenia VIII.1, implikuje to ,że &PSi;(d) = &phi(d) dla wszystkich d; w szczególności, &Psi(m) = &phi(m) > 0.
Teraz rozważmy dowolne pole K, i oznaczmy przez Kx grupy multiplikatywnej elementów niezerowych K, rozważmy te elementy i podgrupy skończonego rzędu Kx Jeśli x jest elementem Kx rzędu m, spełnia xm = 1 a xa = xb jeśli i tylko jeśli a ≡ b (mod m); tradycyjnie, x jest wtedy nazywane pierwiastkiem z jedności a bardziej precyzyjnie pierwotnym m-tym pierwiastkiem z jedności. Dla dowolnego n, element x z K, który spełnia xn = 1 jest pierwiastkiem z jedności którego rząd dzieli się przez n. W polu liczb złożonych, liczba

jest pierwotnym m-tym pierwiastkiem z jedności, tak więc e2πia/m dla (a,m)=1
Twierdzenie X.1. Jeśli K jest dowolnym polem, każda skończona podgrupa z Kx jest cykliczna
Dla każdego n > 0,element z K spełnia xn = 1 jest pierwiastkiem wielomianu Xn - 1; z następstwa twierdzenia IX.2, jest co najmniej n takich elementów w K. Nasze twierdzenie wynika prosto z tego lematu
Następstwo 1. Jeśli K jest polem skończonym, Kx jest cykliczne
Następstwo 2. Jeśli K jest dowolnym polem, a n liczbą całkowitą > 0, elementy K spełniające xn = 1 tworzy grupę cykliczną której rząd dzieli się przez n.
Jasne jest ,że tworzą one podgrupę Kx; jest cykliczna, z twierdzenia X.1; jeśli jest generowana przez x, rząd x, który jest również rzędem grupy,musi dzielić się przez n
Twierdzenie X.2 Jeśli p jest liczbą pierwszą, jest liczba całkowita r pierwsza, taka ,że 1,r,r2,r3,...,rp-2, w pewnym porządku, są odpowiednio kongruentne do 1,2,..., p-1 modulo p.
Jest tylko tradycyjne sformułowanie dla tego faktu, że klasy kongruencji pierwsze do p modulo p tworzą grupę multiplikatywną Fpx pola Fp klasy kongruencji modulo p, i ,że, z następstwa 1 twierdzenia X.1, to musi być cykliczne; jesli (r mod p) jest generatorem tej grupy, r ma właściwość ustanowioną w twierdzeniu X.2. Jeśli m jest liczbą całkowitą > 1, grupa multiplikatywna klasy kongruencji pierwszej do m modulo m nie zawsze jest cykliczna. Jest to cykliczne jeśli jest liczba całkowita r pierwsza do m taka ,ze (r mod m) jest rzędu φ(m) w tej grupie, tj. jeśli i tylko jeśli najmniejsza liczba całkowita x > 0 taka ,że rx ≡ 1 (mod m) jest φ(m); kiedy tak jest, r jest nazywane pierwotnym pierwiastkiem modulo m. Wtedy, każda liczba całkowita a pierwsza do m, jest liczba całkowita x taka ,że rx ≡ a (mod m); ta liczba całkowita x , która jest określona tylko modulo φ(m), jest nazywana indeksem a i oznaczonym przez indr(a). Z twierdzenia VII.2, jeśli r jest pierwotnym pierwiastkiem modulo m, przekształcenie
(a mod m) → (indr(a) mod φ(m))
jest izomorfizmem grupy multiplikatywnej klasy kongruencji pierwszej do m na grupę addytywną wszystkich klas kongruencji modulo φ(m). W szczególności, mamy, dla a i b pierwszą do m:
indr(ab)≡ indr(a) + indr(b) (mod φ(m))
Analogia z logarytmami jest oczywista

ĆWICZENIA
X.1 Jeśli m jest liczbą całkowitą > 1, wykaż ,że liczba pierwotnych pierwiastków modulo m jest albo 0 albo φ(φ(m))
X.2 Znajdź pierwotny pierwiastek r modulo 13;ujmij w tabele indr(a) dla 1 ≤ a ≤ 12; użyj tej tabeli dla znalezienia wszystkich pierwotnych pierwiastków modulo 13 i ujmij w tabelę 5-tą i 29-tą potęgę modulo 13
X.3 Użyj istniejącego pierwotnego pierwiastka modulo p, gdzie p jest liczbą pierwszą, wykaż ,że 1n + 2n + ...+ (p-1)n jest kongruencją do 0 lub do -1 modulo p ze względu na wartość liczby całkowitej n ≥ 0
X.4 Wykaż ,że pierwotny pierwiastek modulo liczba całkowita m > 1 jest również pierwotnym pierwiastkiem modulo każdy dzielnik m (Podpowiedź: użyj ćwiczenia V.6)
X.5 Używając binomialnej formuły, udowodnij przez indukcje ,że jeśli p jest nieparzystą liczbą pierwszą, wtedy dla wszystkich n ≥ 0
: (1+px)pn ≡ 1 + pn+1x(mod p(n+2)
Zatem wykaż ,że jeśli r jest pierwotnym pierwiastkiem modulo p, jest pierwotnym pierwiastkiem modulo pn jeśli i tylko jeśli p2 nie dzieli się przez rp-1 -1 , i ,że w dowolnym przypadku albo r albo r+p jest pierwotnym pierwiastkiem modulo pn
X.6 Znajdź wszystkie liczby całkowite m > 1 takie ,że istnieje pierwotny pierwiastek modulo m
X.7 Liczba całkowita m > 0 jest nazywam,"wolnym kwadratem" jeśli nie ma dzielnika w postaci n2 gdzie n jest liczba całkowitą > 1. Dla każdego m >0, wstaw μ(m) = (-1)r jeśli m jest wolnym kwadratem a iloczyn r liczb pierwszych (z r = 0 jeśli m = 1), i μ(m) = 0 w przeciwnym razie. Udowodnij ,że μ(ab) = μ(a)μ(b) jeśli a jest liczba pierwszą do b; zatem wykaż ,że Σμ(d) to 1 jeśli m = 1 i 0 jeśli m > 1
X.8 Niech K będzie polem zawierającym pierwotny m-ty pierwiastek z jedności x; dla każdego dzielnika d z m, wywołujemy Fd(X) iloczyn współczynników X - xa dla 0 ≤ a < m, (a,m) = m/d .Wykaż ,że Fd jest stopnia φ(d) i udowodnij formułę


zatem, użyj ćwiczenia X.7 dla udowodnienia ,że


X.9 K będące w ćwiczeniu X.8, udowodnij ,że suma wszystkich pierwotnych m-tych pierwiastków z jedności w K jest μ(m). Ustanów specjalny przypadek tego wyniku dla K = Fp, m = p-1

XI

Teraz rozważmy równanie postaci xm = a w polu K (lub okazjonalnie w pierścieniu); przypadek a = 1 omówiliśmy w X. Jeśli przypadek a = 0 jest trywialny, zakładamy a ≠ 0. Jeśli tak, w polu K ,x jest rozwiązaniem xm = a, element x′ K jest również rozwiązaniem jeśli i tylko jeśli (x′ / x)m=1. Dlatego też ,jeśli xm = a ma rozwiązanie w K, ma wiele rozwiązań ponieważ K zawiera m-te pierwiastki z jedności, tj, pierwiastki z Xm-1. Tu, skupimy się na polu Fp kals kongruencji modulo a liczby pierwszej p.
Twierdzenie XI.1 Niech p będzie liczbą pierwszą, m liczbą całkowitą > 0, a a liczbą całkowita pierwszą do p.;umieszczamy d = (m,p-1). Wtedy kongruencja xm ≡ a (mod m) ma albo dokładnie d rozwiązań modulo p lub nie ma rozwiązań; ma rozwiązanie jeśli i tylko jeśli kongruencja yd ≡ a (mod p) ma rozwiązanie; jest tak jeśli i tylko jeśli a(p-1)/d ≡ 1 (mod p), i jest dokładnie p-1/d takich wartości a modulo p.
Skorzystamy z faktu ,że grupa Fpx jest cykliczna, lub ,co jest tym samym, ,że jest pierwotny pierwiastek r modulo p. Wstawimy a ≡ rt , x &equiv ru (mod p), tj. t = indr(a), u = indrx .Wtedy kongruencja xm ≡ a (mod p) jest równoważna do mu ≡ t (mod p-1) , zauważmy ,że t ≡ 0 (mod d) jest równoważne do p-1/d t≡ 0(mod p-1) tj, a(p-1)/d ≡ 1 (mod p)
Weźmy na przykład kongruencję x3 ≡ a (mod p), z pierwszym a do p. Dla p = 3, jest to równoważne x ≡ a (mod 3). Weźmy przypadek gdzie p ≡ (mod 3); ponieważ to implikuje p ≠ 2, p jest również ≡ 1 (mod 2), stąd postać 6n+1; mamy d = 3, p-1/d = 2n; kongruencja x3 ≡ a (mod p) ma rozwiązanie jeśli i tylko jeśli a jest kongruentne do jednej z liczb 1, r3,...,rp-4 modulo p, a potem, jeśli x jest jedynym rozwiązaniem, rozwiązania są dane przez x2mz modulo p z z =0,1,2. jeśli p ≡ 2 (mod 3) w przypadku gdy p jest albo 2 albo w postaci 6n-1, kongruencja x3 ≡ a (mod p) ma jedno i tylko jedno rozwiązanie dla każdego a pierwszego do p. Teraz , rozważmy tylko przypadek m = 2. Wtedy x2 ≡ 1 (mod p) nie ma innego rozwiązania niż 1 jeśli p = 2 i ma dwa rozwiązania ± 1 jeśli p > 2
Definicja Jeśli p jest nieparzystą liczbą pierwszą, liczba całkowita a pierwszą do p jest nazywana resztą kwadratową lub nieresztą kwadratową modulo p ze względu na kongruencję x2 ≡ a (mod p) ma rozwiązanie lub nie.
W każdym innym przypadku niż m = 2 jaki wystąpi, słowo "kwadratowe" będzie okazjonalnie pomijane; w przeciwnym razie mówimy o "reszcie trzeciego stopnia" jeśli m = 3, "resztą bikwadratową" jeśli m=4 itd. Niech p będzie nieparzystą liczbą pierwszą; wstawimy p = 2n+1 i niech r będzie pierwotnym pierwiastkiem modulo p. Wtedy twierdzenie XI.1 pokazuje ,że jest n reszt kwadratowych modulo p, tzn. klasy 1,r2,...,r2n-2 i tym samym liczby niereszt tzn. klas r, r2,...,r2n-1. Jeśli x jest rozwiązaniem x2 ≡ a (mod p), ta kongruencja ma dwa rozwiązania ± x i żadnych innych, modulo p.
Twierdzenie XI.2 Niech p = 2n+1 będzie nieparzystą liczbą pierwszą, a a liczbą całkowitą pierwszą do p. Wtedy an jest kongruentne albo do +1 albo do -1 modulo p; a jest resztą kwadratową lub nieresztą modulo p zależnie od an ≡ + 1 (mod p ) lub an ≡ - 1 (mod p )
Wstawiamy b = an , z twierdzenia Fermata mamy b2 ≡ 1 (mod p), stąd b ≡ ± 1 (mod p). Możemy teraz zastosować twierdzenie XI.1
Następstwo -1 jest resztą kwadratową lub nieresztą modulo do liczby nieparzystej pierwszej p, zależnie od p ≡ 1 lub p ≡ -1 (mod 4).
Faktycznie, (-1)n jest +1 lub -1 ze względu na to ,że n jest parzyste lub nieparzyste.

ĆWICZENIA
XI.1 Jeśli p jest nieparzystym pierwszym dzielnikiem z a2 + b2, gdzie a,b są liczbami całkowitymi, wykaż ,że p musi być kongruentne do 1 modulo 4 chyba ,że dzieli się zarówno przez a i b
XI.2 Jeśli p jest nieparzystą liczbą pierwszą, i a jest liczbą pierwszą do p, wykaż ,że kongruencja ax2 + bx + c ≡ 0 (mod p) ma dwa rozwiązania jedno lub nie ma rozwiązania zależnie od b2 - 4ac ,które jest resztą kwadratową, 0 lub nie resztą modulo p.
XI.3 Jeśli m,n są wzajemnie pierwszymi liczbami całkowitymi > 0, i F jest wielomianem z z całkowitymi współczynnikami, wykaż ,że kongruencja F(x) ≡ 0 (mod mn) ma rozwiązanie jeśli i tylko jeśli F(x) ≡ 0 (mod m a F(x)≡ 0 (mod n) zarówno mają rozwiązania.
XI.4 Jeśli p jest liczbą pierwszą nieparzystą , n > 0, i a jest liczbą pierwszą do p, udowodnij przez indukcję na n, że kongruencja x2 ≡ a (mod pn) ma rozwiązanie jeśl i tylko jeśli a jest resztą kwadratową modulo p: wykaż ,że jeśli x jest rozwiązaniem, nie ma innych rozwiązań niż ± modulo pn
XI.5 Wykaż ,że jeśli a jest nieparzystą liczbą całkowitą, a n > 2, kongruencja x2 ≡ a (mod 2n) ma rozwiązanie jeśli i tylko jeśli a ≡ 1 (mod 8). Jeśli x jest rozwiązaniem, znajdź inne rozwiązania
XI.6 Użyj ćwiczeń XI.3,4,5 aby podać kryteria dla kongruencji x2 ≡ a (mod m) mające rozwiązanie kiedy m jest liczbą całkowitą > 1 a a jest liczbą pierwszą do m.
XI.7 Jeśli, dla pewnego m > 1 i pewnej liczby pierwszej a do m, kongruencja x2 ≡ a (mod m) ma dokładnie n różnych rozwiązań modulo m, wykaż ,że są dokładnie &phi.(m)/n wartości a ,pierwszego do m modulo m, dla których tak jest

XII

Niech p będzie nieparzystą liczbę pierwszą; wstawiamy p =2n+1. Zapiszemy G dla grupy multiplikatywnej Fpx klasy kongruencji pierwszej do p modulo p; to ma podgrupę H rzędu 2 składającą się z klas (±1 mod p); zastosujemy do G i H definicje i lemat z VIII. Jeśli x jest elementem G należy do jednej i tylko jednej warstwy xH; ta składa się z dwóch elementów (±x mod p) ; jest n takich warstw, tzn. warstwy (±1 mod p), (±2 mod p),(±n mod p). Jeśli w każdej warstwie wybierzemy jeden element i jeśli zapiszemy te elementy, w porządku ,jako u1,....,un jest to znane jako "zbiór reprezentacji" dla tych warstw H w G; wtedy każda pierwsza liczba całkowita do p jest kongruentna do jednej i tylko jednej liczby całkowitej ±u1,...,±un modulo p. Z powodu kolejnego lematu, znanego jako lemat Gaussa, taki zbiór {u1,...,un} jest nazywany "zbiorem Gaussa" modulo p. Najprostszym takim zbiorem jest {1,2,...,n}
Lemat Niech p = 2n+1 będzie nieparzystą liczbą pierwszą , a {u1,...,un} zbiorem Gaussa modulo p. Niech a będzie całkowitą liczbą pierwszą do ; dla 1 ≤ i ≤ n, niech ei = ± 1 i i′ będzie takie ,że aui ≡ eiui (mod p). Wtedy a jest resztą kwadratową modulo p lub niezależnie iloczynem e1e2...en jest +1 lub -1
W n kongruencjach dui ≡ eiui (mod p), żadne z dwóch wartości i&prime nie mogą być takie same, ponieważ w przeciwnym razie dane byłoby aui ≡ ± auk (mod p) dla pewnych i ≠ k , zatem ui ≡ ± uk (mod p), co zaprzecza definicji zbioru Gaussa. Dlatego też, jeśli weźmiemy iloczyn wszystkich tych kongruencji, otrzymamy
an(u1u2...un) ≡ (e1e2...en)*(u1u2...un) (mod p)
i dlatego
an ≡ e1e2...en (mod p)
ponieważ wszystkie ui są pierwsze do p. Nasza konkluzja wynika z twierdzenia XI.2
Twierdzenie XII.1 Niech p będzie nieparzystą liczbą pierwszą; wtedy 2 jest resztą kwadratową modulo p jeśli p &equiv 1 lub 7 (mod 8), a a nieresztą jeśli p ≡ 3 lub 5 (mod 8).
Wstawmy p =2n+1 i zastosujmy lemat Gaussa do a = 2 i zbiór Gaussa {1,2,...,n}. Jeśli n = 4m lub 4m+1, ei ma wartość +1 dla 1 1 ≤ i ≤ 2m, i -1 w przeciwnym razie;wtedy iloczynei to (-1)n-2m = (-1)π. Jeśli n = 4m+2 lub 4m+3, ei to +1 dla 1 ≤ i ≤ 2m+1, i -1 przeciwnym razie a iloczyn ei to (-1)n-2m-1 = (-1) n-1
Definicja Jeśli p jest nieparzystą liczbą pierwszą a a liczbą całkowita pierwszą do p, definiujemy (a/p) mającą wartość +1 lub -1 zgodnie z tym a jest resztą kwadratową modulo p; jest to nazywane symbolem Legendre′a >kiedy dane jest p , symbol (a/p) zależy tylko od klasy kongruencji a modulo p. Definicja ta implikuje ,ze (a2/p) = q dla wszystkich a pierwszych do p. Jeśli r jest ponownie pierwotnym pierwiastkiem modulo p i jeśli a ≡ rx (mod p), tj. x = indr(a), mamy (a/p) = (-1)x; tu odnotujmy ,że nie zależy to od wybranego x, ponieważ x jest dobrze zdefiniowanym modułem parzystej liczby całkowitej p-1. Z podstawowej właściwości indeksu, wynika ,że symbol Legendre′a ma własność
(ab/p) = (a/p) * (b/p) dla wszystkich a ,b pierwszych do p.
Twierdzenie XI.2, jego następstwa i twierdzenie XII.1 dają odpowiednio:
a(p-1)/2 ≡ (a/p) (mod p), (-1/p) = (-1)(p-1)/2, (2/p) = (-1)()p2 -1)/8 .
Co do ostatniej formuły, zauważmy ,że p2 -1 / 8 jest zawsze liczbą całkowitą, nawet jeśli p ≡ 1 lub 7(mod 8) i nieparzystą jeśli p ≡ 3 lub 5 (mod 8). Twierdzenie powyższe jest znane jako "prawo reszt kwadratowych":
Twierdzenie XII.2 Jeśli p i q są różnymi liczbami pierwszymi nieparzystymi, wtedy
(p/q)*(q/p) = (-1)[(p-1)/2]*[(q-1)/2]
Wstawmy p = 2n+1 , q - 2m=1. Zastosujemy lemat Gaussa do a = q i do "zbioru Gaussowego" {1,2...,n} modulo p. Dla 1 ≤ x ≤ n, musimy zapisać qx ≡ exu (mod p) z ex = ± 1 i 1 ≤ u ≤ n; może to być zapisane jako qx = ex + py, gdzie ex, u ,y są jednoznacznie określone przez te warunki kiedy dane jest x. W szczególności, ex ma wartość -1 jeśli i tylko jeśli mamy qx = py - u, lub równoważnie py = qx + u, z 1 ≤ u ≤ n. To implikuje y > 0 i również
y ≤ 1/p * (q+1)n < q+1/2 = m+1
Innymi słowy, mamy ex = -1 jeśli i tylko jeśli możemy znaleźć y takie ,że para (x,y) spełnia warunki
1 ≤ x ≤ n , 1 ≤ y ≤ m, 1 ≤ qx - py ≤ m
W konsekwencji, jeśli N jest liczbą takich par (x,y), lemat Gaussa daje (q/p) = (-1)N. Podobnie, (p/q) ma wartość (-1)M ,jeśli M jest liczba par (x,y) spełniających
1 ≤ x ≤ n , 1 ≤ y ≤ m, 1 ≤ qx - py ≤ m
Ponieważ qx-py nie może być 0 jeśli x jest liczbą pierwszą do p i w szczególności jeśli 1 ≤ x &le, n, pokazuje to ,że lewa strona wzoru w naszym twierdzeniu ma wartość (-1)M+N, gdzie M+N jest liczbą par (x,y) spełniających warunki
1 ≤ x ≤ n , 1 ≤ y ≤ m, -n ≤ qx - py ≤ m
Teraz niech S będzie liczbą par (x,y) spełniających
1 ≤ x ≤ n , 1 ≤ y ≤ m, qx - py < -n
i niech T będzie liczbą par (x′y′) spełniających
1 ≤ x′ ≤ n , 1 ≤ y′ ≤ m, qx′ - py′ > m
Między tymi ostatnimi dwoma zbiorami, jest odpowiedniością wzajemnie jednoznaczną zdefiniowaną przez
x′ = n+1-x, y′=m+1-y
faktycznie, kiedy tak jest ,mamy
qx′ - py′ - m = -(qx-py+n)
Dlatego też S = T. Z drugiej strony,M+N+S+T jest całkowitą liczbą par (x,y) z 1 ≤ x ≤ n, 1 ≤ y ≤m, i dlatego jest równe mn. W końcu mamy
(p/q)*(q/p) = (-1)M+N = (-1)M+N+S+T = (-1)mn, co było do udowodnienia.

ĆWICZENIA
XII.1 Niech p będzie nieparzystą liczbą pierwszą; niech f(a) będzie funkcją, zdefiniowaną dla a pierwszej do p, nie pobierającą innej wartości niż ± 1 i taką ,że
f(ab) = f(a)f(b); f(a) = f(b) jeśli a ≡ b (mod p)
Wykaż ,że albo f(a) = 1 dla wszystkich a lub f(a) = (a/p) dla wszystkich a
XII.2 Jeśli p jest nieparzystym dzielnikiem a2 + 2b2, gdzie a,b są liczbami całkowitymi, wykaż ,że p jest kongruentne do i lub do 3 modulo 8 chyba ,że jest podzielne przez a i b
XII.3 Jeśli p i q są liczbami pierwszymi takimi ,że p = 2q+1 i q ≡ 1 (mod 4) wykaż ,że 2 jest pierwotnym pierwiastkiem modulo p
XII.4 Używając tylko lematu Gaussa, znajdź wszystkie wartości liczby pierwszej p > 3 dla których 3 jest resztą kwadratową
XII.5 Niech a będzie niezerową liczbą całkowitą. Udowodnij ,że jeśli p i q są nieparzystymi liczbami pierwszymi, nie podzielnymi przez a, takimi ,że p ≡ q (mod 4|a|), wtedy (a/p) = (a/q).

XIII

Przypomnijmy sobie pojęcie liczby złożonej. Jest to liczba w postaci x+iy, gdzie x,y są liczbami rzeczywistymi; i spełnia warunek i2 = -1, a zasady dodawania i odejmowania są dobrze znane. Mnożenie jest podane w ten sposób
(x+iy)(x′+iy′) = (xx′ - yy′) + i(yx′ + xy′)
Dla dodawania i odejmowania, zbiór C liczb złożonych tworzy pierścień jednostkowy, z elementem jednostkowym 1 = 1+i0. Jeśli a = x+iy, zapisujemy a^ = x - iy, i nazywamy a^ sprzężeniem urojonym al sprzężenie urojone z a^ to a. Przekształcenie a → a^ jest odwzorowaniem wzajemnie jednoznacznym C na samego siebie, zachowują operacje dodawania i mnożenia; jest zatem "automorfizmem" C tj. izomorfizmem C na samego siebie. Piszemy N(a) =aa^ i nazywamy to normą z a . Z zasady mnożenia, jeśli a = x + iy, N(a) = x2 + y2, z przemienności mnożenia mamy N(ab) = N(a)N(b).Normą z a jest 0 jeśli i tylko jeśli a jest 0; w przeciwnym razie jest to liczba rzeczywista > 0. W konsekwencji, dla a = x +iy ≠ 0, możemy wstawić
a′ = N(a)-1 a^ = x/N(a) -i*y/N(a)
a zatem aa′ = 1 , i dla każdego b ,a(a′b) = b; odwrotnie, jeśli az = b, mamy a′(az) = a′b, zatem,przez łączność, z = a′b. Pokazuje to ,że C jest faktycznie polem. Jak zwykle łączymy,z liczbą zespoloną a = x+iy, punkt (x,y) na płaszczyźnie; Odległość Euklidesa od "początkowego" 0 jest wtedy |a| = N(a)1/2; jest to również nazywane "wartością bezwzględną" a. Dla naszego celu, rozważymy zamiast pola C, podzbiór C składa się z liczby zespolonej x+iy gdzie x,y są w Z tj. zwyczajne liczby całkowite, Można od razu sprawdzić ,że jest to pierścień; jest nazwany pierścieniem Gaussa a ego elementami są tzw, liczby całkowite Gaussa. Wyraźnie a → a^ jest automorfizmem tego pierścienia. Jeśli s jest dowolną liczbą całkowitą Gaussa, N(a) = aa^ jest dodatnią liczbą całkowitą w Z Sporadycznie rozważymy liczby x +iy gdzie x,y są w Q tj. liczbami wymiernymi; podobnie jak powyżej widać ,że tworzą pole ("pole Gaussa"). Jeśli a,b,x to liczby całkowite Gaussa, a b = ax to mówimy ,że b jest wielokrotnością a; a dzieli się przez b lub jest dzielnikiem b, wtedy N(a) dzieli się przez N(b). Każda liczba całkowita Gaussa dzieli się przez swoją norę, Dzielnik 1 jest nazywany jednością; jeśli a = x + iy jest jednością, N(a) musi dzielić się przez 1 i musi być 1; jeśli x,y są jednościami, implikuje to ,że jedna z nich to ± 1 a druga 0. Dlatego jednostki Gaussa to ± 1, ± i. dwie niezerowe liczby całkowite Gaussa a,b dzieli się jedna przez drugą jeśli i tylko jeśli różnią się tylko przez współczynnik który jest jednością, tj. jeśli b = ea z e ±1 lub ±i l wtedy są one nazywane sprzężonymi. Wśród czterech sprzężeń danej liczby całkowitej a ≠ 0, jest jedna i tylko jedna, powiedzmy b = x+iy, spełniająca x > 0, y ≥ 0; która będzie nazywana znormalizowaną . Na przykład, wśród sprzężeń i ±1, ±i z 1 + i, 1+i i nie ma innych normalizacji. Geometrycznie, punkty na płaszczyźnie, odpowiadają sprzężeniom a , są tymi wydedukowanymi z a przez rotację wokół zwiera o kąt πn/2 z n = 0,1,2,3; znormalizowany punkt jest punktem , który leży albo nqa osi dodatniej rzeczywistej lub w "pierwszej ćwiartce". Norma liczby całkowitej Gaussa > 1 jest nazywana liczbą pierwszą Gaussa jeśli nie ma innych dzielników niże jedności i swojego własnego sprzężenia. Można powiedzieć ,że q jest liczbą pierwszą Gaussa jeśli nie jest 0 lub jednością i nie ma dzielnika, którego norma jest > 1 i < N(q). Porządkowe liczby całkowite które są pierwsze w poprzednio zdefiniowanym sensie będą nazywane wymiernymi liczbami pierwszymi. Jeśli q jest liczbą całkowitą Gaussa a N(q) jest liczbą pierwszą wymierną, wtedy q jest liczbą pierwszą Gaussa; jak zobaczymy, konwersja nie jest prawdziwa Sprzężenia liczby pierwszej Gaussa są liczbami pierwszymi; jak zobaczymy, jest jedna i tylko jedna która jest "znormalizowana" w powyższym zdefiniowanym sensie. Jeśli w jest dowolna liczbą pierwszą, więc jest q^, Jeśli a jest dowolną liczbą całkowitą Gaussa, ani 0 ani jednością ,wtedy jej dzielnik najmniejszej normy > 1 musi być liczbą pierwszą Gaussa. Gauss, który wprowadził liczby całkowite Gaussa do teorii liczb, odkrył ,że mogą być (szczególnie jednoznacznie) rozłożone na liczby pierwsze Gaussa w ścisłej analogii ze zwykłymi liczbami całkowitymi. Teraz to udowodnimy. Metoda jest taka sama jak w II,III,IV i IX. Najpierw udowodnimy lemat, podobny do tego w II i IX.
Lemat.Niech a,b będą liczbami całkowitymi Gaussa, z b ≠ 0. Wtedy jest wielokrotność bq z b taka ,że
N(a-bq) ≤ 1/2 N(b).
Dla dowolnej liczby rzeczywistej t, jest największą liczba całkowita m ≤ t, i mamy m ≤ t < m+1; przez najbliższą liczbę całkowitą m′ do t, zrozumiemy albo m albo m+1 zgodnie z t - m to ≤ m+1 - t lub nie wtedy mamy |t-m′| ≤ 1/2. Teraz niech z = x+iy będzie dowolną liczbą zespoloną; wywołamy m najbliżej liczby całkowitej x, n najbliżej liczby całkowitej y i wstawimy q = m+n. Wtedy q jest liczbą całkowitą Gaussa i mamy2 + (y-n)2 ≤ 1/2
Zastosujemy to z = a/b , gdzie a,b sa liczbami całkowitymi w lemacie. Liczba całkowita Gaussa q zdefiniowana przez powyższą konstrukcję ma wtedy wymaganą właściwość
Twierdzenie XIII.1. Niech ℜ będzie niepustym zbiorem liczby całkowitej Gaussa, zamknięta pod względem dodawania i taki ,że jeśli a jest w ℜ wszystkie wielokrotności a są w ℜ. Wtedy ℜ składa się ze wszystkich wielokrotności pewnej liczby całkowitej Gaussa d, jednoznacznie określoną do czynnika jednostkowego
jeśli ℜ = {0} twierdzenie jest prawdziwe dla d = 0. Jeśli nie , bierzemy w ℜ element d z najmniejszą normą > 0. Jeśli a jest w ℜ możemy zastosować lemat i zapisać a = dq+r z N(r) ≤ 1/2 *N(d).Wtedy r = a-dq jest w ℜ, co zaprzecza definicji d chyba ,że r = 0, a = dq. Przy jedności, jeśli d′ ma te samą właściwości jak d, d i d′ muszą być wielokrotnościami dla siebie wzajemnie, więc d′ jest łączny z d
. Podobnie jak w II (i w IX) możemy teraz zastosować twierdzenie XIII.1 do zbioru wszystkich liniowych kombinacji ax+by+...+cz, gdzie a,b,...,c są danymi liczbami całkowitymi Gaussa a x,y,...,z są arbitralnymi liczbami Gasussa a więc definiujemy g.c.d (a,b,c...,c); będzie to jednoznacznie określone jeśli przepiszemy to aby było "znormalizowane" (w sensie zdefiniowanym powyżej). Jeśli jest to 1, mówimy ,że a,b,...,c są wzajemnie względnie pierwsze. Możemy teraz powtórzyć zawartość III i IV, z wyjątkiem tego ,że dowodzimy twierdzenia IV.2 przez indukcję na liczbie całkowitej a w tym twierdzeniu, podczas gdy teraz używamy indukcji na N(a). Konkluzja:
Twierdzenie XIII.2 Każda niezerowa liczba całkowita Gaussa może być zapisana "szczególnie jednoznacznie" jako iloczyn jedności i liczb pierwszych Gaussa.
Tu słowa "szczególnie jednoznaczne" mają następujące znaczenie. Niech
a = eq1q2...qr = e′q′1q′2...q′s
będą dwoma iloczynami wymaganego typu dla pewnych a ≠ 0, gdzie e,e′ są jednościami a qj i q′k są liczbami pierwszymi Gaussa. Wtedy twierdzenie powinno być zrozumiane aby powiedzieć ,że r = s i ,że q′k może być przeporządkowane tak aby q′j było sprzężone az qj dla 1 ≤ j ≤ r; jeśli a jest jednością , r = 0. Jeśli przepiszemy tak ,że współczynniki pierwsze a powinny być "znormalizowane", wtedy iloczyn jest jednoznacznie określony w porządku współczynników. Liczby całkowite zwykłe są również liczbami całkowitym Gaussa; aby uzyskać ich dekompozycję do liczb pierwszych Gaussa, jest to wystarczające aby zrobić to dla "zwykłych" liczb pierwszych
Twierdzenie XIII.3. Niech p będzie nieparzystą liczbą pierwszą wymierną. Wtedy jest to albo liczba pierwsza Gaussa lub normą liczby pierwszej q Gaussa; w drugim przypadku p = qq^, q i q^ nie są sprzężone, a p nie ma innych dzielników pierwszych Gaussa niż q,q^ i ich sprzężeń.
Wstawiamy p=eq1q2....qr jak w twierdzeniu XIII.2. Biorąc normę, znajdujemy ,że p2 jest iloczynem N(qj). Jeśli jedna z N(qj) jest p2 wtedy r = 1, p= eq a samo p jest liczbą pierwszą Gaussa. W przeciwnym razie każda N(qj) jest p i możemy zapisać p = N(q) = qq^ , z q jako liczbą pierwszą Gaussa, q^ jest wtedy również liczbą pierwszą Gaussa. Wstawiamy q = x+iy; jeśli q^ było sprzężone z q, będzie ± q lub 7plusmn;iq; to daje albo y = 0, p = x2 lub x = 0, p = y2 , lub y = ±x, p = 2x2; tak nie może być ponieważ p jest nieparzystą liczbą pierwszą. Przy p = 2, jej dekompozycja może być dana przez
2=N(1+i) = (1+i)(1-i) = i3(1+i)2.
Twierdzenie XIII.4 Niech p będzie nieparzystą liczbą pierwszą wymierną. Wtedy p jest liczbą pierwszą Gaussa lub normą liczby pierwszej Gaussa zgodnie z jej kongruencją do 3 lub do 1 modulo 4
Jeśli jest to norma q = x+iy, mamy p = x2 = y2, gdzie jedna z liczb całkowitych x,y musi być nieparzysta a druga parzysta. wtedy jeden z kwadratów x2, y2 jest kongruentny do 1 a drug do 0 modulo 4, tak więc p ≡ 1 (mod 4). Odwrotnie, jeśli jest tak, następstwo twierdzenia XI.2 wykazuje ,że -1 jest resztą kwadratową modulo p, tak więc jest x taki ,że x2+1 jest wielokrotnością p. Jeśli x2+1 = (x+1)(x-1), to ,jeśli p będzie liczbą pierwszą Gaussa, zaimplikuje to ,że p dzieli się albo przez x+1 lub x-1. Oczywiście tak nie może być.
Następstwo 1Każda liczba pierwsza Gaussa jest albo ±1 ±i lub skojarzona z kongruencją liczby pierwszej wymiernej do 3 modulo 4, lub jeśi w przeciwnym razie jest normą, jest kongruencją liczby pierwszej wymiernej do 1 modulo 4
Faktycznie, każda liczba pierwsza Gaussa q musi być podzielna przez jakiś pierwszy wymierny współczynnik p swojej normy qq^; zastosujemy twierdzenie XIII.4 jeśli p jest nieparzyste a powyższe spostrzeżenie jeśli p = 2, otrzymamy naszą konkluzję.
Następstwo 2 Liczba pierwsza wymierna może być zapisana jako suma dwóch kwadratów jeśli i tylko jeśli jest to 2 lub kongruencja do 1 modulo 4
Faktycznie, jeśli p = x2 + y2, p nie może być liczbą pierwszą Gaussa, ponieważ ma dzielniki x ± iy
ĆWICZENIA
XIII.1 jeśli dodatnia liczba całkowita jest zapisana jako n2a gdzie a jest > 1 i wolnym kwadratem, wykaż ,że może być zapisana jako suma dwóch kwadratów jeśli i tylko jeśli każdy nieparzysty pierwszy dzielnik a to ≡ 1 (mod 4).Jeśli tak jest, a ma r pierwszych dzielników,znajdź liczbę reprezentacji a jako suma dwóch kwadratów.
XIII.2 Jeśli liczba całkowita jest sumą dwóch względnych pierwszych kwadratów, wykaż,że to samo jest prawdziwe dla każdego dzielnika tej liczby całkowitej
XIII.3 Używając reprezentacji liczb zespolonych jako punktów na płaszczyźnie, wykaż ,że jeśli z jest liczbą zespoloną, jest liczbą całkowitą Gaussa q której odległość od z to ≤ √2 / 2; wykaż ,że wśród wszystkich liczb całkowitych, jest co najmniej jedna , której odległość od z jest najmniejsza i ,ze jest nie więcej niż cztery z tą właściwością.
XIII.4 Kongruencja relacji będzie będąca zdefiniowaną dla liczb całkowitych Gaussa w ten sam spsoób jak dla zwykłych liczb całkowitych, wywołaj f(m) dla dowolnej liczby całkowitej Gaussa m ≠ 0; liczba różnych klas kongruencji Gaussa modulo m; wykaz ,że f(mn) = f(m)f(n) dla dowolnych dwóch niezerowych liczb całkowitych Gaussa m,n
XIII.5 Użyj ćwiczenia XIII.4 aby wykazać ,że f(m) = mm^ dla każdego m
XIII.6 Wykaż ,że jeśli m jest liczbą całkowitą Gaussa z norma > 1, klasa kongruencji Gaussa modulo m tworzy pole jeśli i tylko jeśli m jest liczbą pierwszą Gaussa. Wykaż ,że jeśli N(m) jest liczbą pierwszą wymierną, każda liczba całkowita Gaussa jest kongruentna do pewnej liczby całkowitej wymiernej modulo m.
XIII.7 Jeśli ω = - 1/2 + i √3/2, wykaż ,że liczba zespolona x + yω, gdzie x i y są zwykłymi liczbami całkowitymi, tworzy pierścień R, którego jednostki to ±1, ±ω, ±ω2. Udowodnij ,że jeśli z jest liczbą zespoloną, jest element q pierścienia R , taki ,że N(z-q) ≤ 1/3
XIII.8 Użyj ćwiczenia XIII.7 aby wykazać ,że wymierna liczba pierwsza > 3 może być zapisana jako x2+xy+y2, z liczbami całkowitymi x,y, jeśli i tylko jeśli jest ≡ 1 (mod 3)