Teoria liczb

Teoria liczb jest dziedziną matematyki, zajmującą się badaniem własności liczb - początkowo tylko naturalnych. Obecnie należałoby powiedzieć: głównie naturalnych.

Jej początki sięgają starożytności. Zajmowali się nią Pitagoras, Euklides, Eratostenes, Diofantos i wielu innych. Bujny rozwój teorii liczb datuje się mniej więcej od czasów działalności Pierre'a Fermata (1601-1665), autora słynnego Wielkiego Twierdzenia Fermata. Ogromny wkład w rozwój teorii liczb miał słynny Carl Friedrich Gauss, zaś z polskich matematyków - Wacław Sierpiński.

Badania w zakresie teorii liczb przyczyniły się do znacznego rozwoju wielu gałęzi matematyki: algebry, teorii funkcji zmiennej zespolonej, rachunku prawdopodobieństwa, geometrii algebraicznej i innych.

Najstarszym działem teorii liczb jest elementarna teoria liczb, w której nie stosuje się metod analizy matematycznej. Jednym z najważniejszych osiągnięć elementarnej teorii liczb jest dowód Erdösa i Selberga pewnego twierdzenia o liczbach pierwszych. Teoria liczb zajmuje się również rozwiązywaniem równań w dziedzinie liczb naturalnych, całkowitych, wymiernych oraz (od niedawna) liczb p-adycznych.

Liczby naturalne

Liczby naturalne - liczby używane powszechnie do liczenia (na obiedzie były trzy osoby) i ustalania kolejności (był trzeci na liście). Pojęcie liczby jest jednym z najstarszych i najbadziej abstakcyjnych pojęć jakie wytworzyła ludzkość, wydaje się jednak, że niewiedza na temat czym liczby są nie przeszkadza nam sprawnie się nimi posługiwać.

Badaniem własności liczb naturalnych zajmuje się teoria liczb, badaniem problemów związanych z liczeniem - kombinatoryka.

Zazwyczaj mówiąc o liczbach naturalnych mamy na myśli liczby 1, 2, 3, 4..., czasem jednak wygodnie jest przyjąć, że liczba 0 jest również liczbą naturalną. Tak robi się na przykład w informatyce i teorii mnogości.

Historia

Liczby naturalne (bez zera) początkowo były stosowane wyłącznie do określania liczebności obiektów.

Pierwszy krok dla wyabstrahowania liczb naturalnych to stworzenie cyfr na określenie danych wartości liczb. Przykładowo w Babilonii stosowano cyfry o wartościach od 1 do 10, zaś o wartości liczby decydowała pozycja kolejnych cyfr w szeregu. W starożytnym Egipcie stosowano odpowiednie hieroglify o wartościach 1, 10 i kolejnych potęgach 10 aż do miliona.

Znacznie później pojawiło się zero jako oddzielna wartość. Już w siódmym wieku p.n.e. Babilończycy stosowali zero w zapisie pozycyjnym, ale nigdy nie występowało ono samodzielnie. W Cywilizacji Majów zero istniało jako liczba już w I w. p.n.e., ale Majowie nie rozprzestrzenili tej idei poza Amerykę Środkową. Współczesne pojęcie zera przypisuje się Hindusowi Brahmagupcie, który stworzył je w 628. Zero stosowano w średniowieczu, ale nie miało ono swojej reprezentacji w cyfrach rzymskich - stosowano łacińskie słowo nullae.

Pierwsze systematyczne, abstrakcyjne studia nad liczbami przypisuje się Greckim filozofom: Pitagorasowi i Archimedesowi. Poza Grecją niezależne rozważania prowadzono w rejonie Indii, Chin i Ameryki Środkowej.

Dopiero w XIX w. pojawiła się ścisła, teoriomnogościowa definicja zbioru liczb naturalnych. Zgodnie z nią, zero jako odpowiednik zbioru pustego jest najmniejszym elementem tego zbioru. Wielu matematyków, szczególnie w teorii liczb jednak wyłącza tę liczbę ze zbioru liczb naturalnych.

Określenie formalne

Postulaty Peano

Podanie ścisłej definicji zbioru liczb naturalnych nie było proste i zajęło matematykom wiele czasu. Giuseppe Peano zaproponował następujące warunki (tzw. postulaty lub aksjomaty Peano), które musi spełniać zdefiniowany zbiór liczb naturalnych, aby ta definicja była prawidłowa:

• Istnieje liczba naturalna 0;

• Każda liczba naturalna ma swój następnik, oznaczany S(a);

• Zero nie jest następnikiem żadnej liczby naturalnej;

• Różne liczby naturalne mają różne następniki:
  ;

• Jeśli zero ma daną własność i następnik dowolnej liczby naturalnej ma tę własność, to każda liczba naturalna ma tę własność (zasada indukcji matematycznej).

Ostatnia z własności oznacza, że każda liczba naturalna poza zerem jest następnikiem jakiejś liczby naturalnej.

Okazuje się, że powyższe postulaty pozwalają wprowadzić arytmetykę. Dodawanie definiujemy jak operację spęłniającą następujace warunki:

• 
  

• 
  

To wystarczy do wyliczenia sumy liczb np. 2+2 (dwa oznacza skrótowy zapis liczby S(S(0))). kolejno otrzymujemy:

• 2+2

• 2+S(1) bo 2 jest następnikiem 1

• S(2)+1 z definicji

• 3+1 następnik 2 oznaczamy symbolem 3

• 3+S(0) 1 jest następnikiem 0

• S(3)+0=S(3) z definicji

• S(3)=4 następnik 3 oznaczamy symbolem 4

Podobnie definiujemy mnożenie jako operację spełniającą warunki:

• a*0=0

• a*S(b)=(a*b)+a

Powyższe postulaty mówią jakie własności powinny mieć liczby naturalne. Pozostaje pytanie czy taki "twór" istnieje. Okazuje się, że przy założeniu aksjomatów teorii mnogości można skonstruować zbiór liczb naturalnych. Taką konstrukcję przedstawia poniższa

Konstrukcja von Neumanna

Jest to przykład możliwej konstrukcji zbioru liczb naturalnych, nie jedynej, ale jednej z ważniejszych. Tak skonstruowany zbiór oczywiście spełnia aksjomaty Peano. Amerykański matematyk John von Neumann zaproponował następujący sposób konstrukcji liczb naturalnych:

Niech X - zbiór induktywny.

Niech
.
to zbiór induktywny (dowód przy aksjomacie nieskończoności). Pokażmy, że jest to najmniejszy w sensie inkluzji zbiór induktywny.

Niech Z - zbiór induktywny. To
też jest zbiorem induktywnym, bo to przecięcie zbiorów induktywnych.
(z własności iloczynu)
. Skoro tak, to
- co kończy dowód.

Zbiór ten istotnie jest najmniejszy, jest więc jedyny. Nazwiemy go liczbami naturalnymi i oznaczymy przez
.

Korzystając z faktu induktywności
:

• 
  - oznaczamy jako 0;

• 
  - oznaczamy jako 1;

• 
  - oznaczamy jako 2;

i tak dalej.

W teorii mnogości na każdą liczbę naturalną patrzymy jak na zbiór zawierający wszystkie poprzednie liczby naturalne, np. 2 = {0,1}, 5 = {0,1,2,3,4} itp.

Podstawowe własności

Dla wszystkich liczb naturalnych:

• jeśli m < n to m <= n;

• ~(n < n);

• jeśli m <= n i ~(m = n) to m < n;

• jeśli S(m) = S(n) to m = n;

• jeśli n <= k <= S(n) to k=n lub k=S(n)

• m <= n lub n <= m (porządek);

• m = n lub n < m lub m < n.

Równania diofantyczne

Podstawowym problemem teorii równań diofantycznych, bo tak nazywa się ten dział matematyki, jest znalezienie efektywnych sposobów wyznaczenia rozwiązań danego równania. Okazało się, że nie istnieje algorytm, który w każdym przypadku prowadziłby do rozwiązania równania diofantycznego. Znane są tylko algorytmy rozwiązywania równań liniowych i kwadratowych wielu zmiennych oraz pewnych szczególnych przypadków równań wyższych stopni.

Często nie można nawet odpowiedzieć na podstawowe pytania: czy dane równanie diofantyczne ma choć jedno rozwiązanie, czy liczba tych rozwiązań jest skończona, czy jest ich nieskończenie wiele?

Do efektywnego rozwiązywania równań diofantycznych przydatna jest teoria kongruencji. Kongruencja to przystawanie liczb "modulo n": liczby a i b przystają modulo n, jeżeli ich różnica a-b dzieli się bez reszty przez n, co zapisuje się: a ≡ b (mod n).

Klasycznym przykładem równania diofantycznego, rozwiązanego w liczbach naturalnych już przez samego Diofantosa (to od jego nazwiska ukuto nazwę tego działu matematyki), jest problem trójkątów pitagorejskich. Szukamy rozwiązań w liczbach naturalnych równania: x² + y² = z². Przykładowe rozwiązania to następujące trójki pitagorejskie: (3, 4, 5), (5, 12, 13),.... Rozwiązania nie będące wielokrotnościami innych rozwiazań to tzw. "rozwiązania właściwe".

Takich trójkątów pitagorejskich (o bokach całkowitej długości) jest nieskończenie wiele. Wszystkie rozwiązania właściwe równania Pitagorasa w liczbach naturalnych (x, y, z) można uzyskać ze wzorów, które znał już Diofantos: x = k² − l², y = 2kl, z = k² + l²; gdzie k, l to liczby naturalne, przy czym k > l. Jeśli k i l są względnie pierwsze uzyskuje się rozwiązania właściwe, nie będące wielokrotnością innych rozwiązań. W ten sposób można uzyskać wszystkie rozwiązania właściwe. Inaczej: jeśli długości boków trójkąta pitegorejskiego nie mają wspólnego dzielnika, to istnieje tak liczba zespolona całkowita z, że boki trójkąta to: Re(z²), Im(z²), |z²|.

Istnieje też geometryczna konstrukcja Vogelera umożliwiająca znajdowanie trójkątów pitagorejskich, ale nie ma znaczenia praktycznego. Sposób Vogelera pozwala również skonstruować wszystkie ułamki pitagorejskie: każda znaleziona trójka pitagorejska generuje trzy następne.

Podział teorii liczb

Teoria liczb podzielona jest obecnie na wiele mniejszych działów. Można w niej wyodrębnić m. in. część algebraiczną, analityczną i probabilistyczną.

Można też podzielić ten dział matematyki na addytywną i multiplikatywną teorię liczb. Pierwsza zajmuje się dodawaniem i odejmowaniem, a druga mnożeniem i dzieleniem liczb całkowitych. Te wydawałoby się proste operacje arytmetyczne prowadzą nierzadko do trudnych i wciąż nierozwiązanych problemów, takich jak problem Collatza czy słynna hipoteza Goldbacha, która jest przykładem nie udowodnionego przez wieki twierdzenia o sumach liczb pierwszych (addytywna teoria liczb).

Kongruencja

Kongruencja to relacja określona w zbiorze liczb całkowitych. Kongruencja modulo n nazywana jest też przystawaniem liczb "modulo n".

Liczby całkowite a i b przystają modulo n (pozostają w kongruencji modulo n), co zapisuje się: a ≡ b (mod n), jeżeli ich różnica a-b dzieli się bez reszty przez n. Równoważnie: jeśli liczby a i b dają w dzieleniu przez n tę samą resztę.

Przykład:

Liczby 5 i 11 przystają modulo 3:

11 ≡ 5 (mod 3)

ponieważ ich różnica, czyli 6, dzieli się bez reszty przez 3. Równoważnie, w dzieleniu z resztą obu liczb przez 3 otrzymujemy tę samą resztę 2:

11 : 3 = 3 r 2

5 : 3 = 1 r 2

Własności kongruencji:

• zwrotność:

dla każdej liczby całkowitej a: a ≡ a (mod n).

• symetria:

jeżeli dla liczb całkowitych a i b: a ≡ b (mod n), to: b ≡ a (mod n).

• przechodniość:

jeżeli dla liczb całkowitych a, b i c: a ≡ b (mod n) i b ≡ c (mod n), to: a ≡ c (mod n).

Kongruencja jest zatem relacją równoważności

Własności kongruencji:

• kongruencja sumy

Jeżeli a ≡ p (mod n) i b ≡ q (mod n), to (a+b) ≡ (p+q) (mod n)

• kongruencja iloczynu

Jeżeli a ≡ p (mod n) i b ≡ q (mod n), to a·b ≡ p·q (mod n)

Powyższe dwie własności są podstawą m.in. obliczeń kontrolnych w rachunkach pisemnych, np. "reguły dziewiątek".

Kongruencje można też określać w dowolnych pierścieniach.

---