Elementarna teoria liczb/Elementy podzielności liczb

Z Wikibooks, biblioteki wolnych podręczników.
Przejdź do nawigacji Przejdź do wyszukiwania

Elementy podzielności liczb[edytuj]

Podzielność jest bardzo ważnym pojęciem w teorii liczb. Mówimy, że liczba całkowita a jest podzielna przez liczbę całkowitą b, jeśli istnieje liczba całkowita c taka, że a = b * c.

Na przykład: liczba 123456 jest podzielna przez 643, ponieważ istnieje liczba całkowita, czyli 192. Tak więc .

Podzielność zaznaczamy pionową kreską: a | b oznacza "a dzieli b". Na przykład możemy napisać

Liczby pierwsze[edytuj]

Liczbą pierwszą nazywamy liczbę naturalną, która ma dokładnie dwa dzielniki: jedynkę i samą siebie. Jedenaście pierwszych takich liczb to: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 i 31. Istnieje nieskończenie wiele liczb pierwszych o czym przekonamy się udowadniając poniższe twierdzenia. Powszechnie liczba 1 nie jest uważana za liczbę pierwszą chociaż nie posiada innych dzielników niż siebie. Przyczyny tego będą omówione później.

Twierdzenie 1[edytuj]

Załóżmy, że i są liczbami całkowitymi i . Wtedy .

Dowód
Istnieje i taki, że i . Dlatego:

Wiemy, że jest także liczbą całkowitą, stąd .

Wniosek
Załóżmy, że i są liczbami całkowitymi i . Wtedy i .

Twierdzenie 2[edytuj]

Jeśli są liczbami całkowitymi i wtedy .

Dowód
Zapiszmy b jako i c jako dla kilku liczb całkowitych i .

Wynika z tego, że:
, więc .

Twierdzenie 3[edytuj]

Jeśli są liczbami całkowitymi i , a następnie wtedy i tylko wtedy, gdy
Dowód:

implikuje istnienie takiej liczby całkowitej d, która

Więc wynika z tego, że

i stąd .

Z drugiej strony możemy założyć, że mamy taką liczbę n, że i , stąd:

,

stąd: , więc

Twierdzenie udowodnione.

Twierdzenie 4[edytuj]

Podstawowe twierdzenie arytmetyki
Każdą liczbę całkowitą dodatnią można jednoznacznie przedstawić w postaci iloczynu liczb pierwszych.

Dowód:
Twierdzenie udowodnimy za pomocą dowodu nie wprost.

Niech N będzie najmniejszą dodatnią liczbą całkowitą, że nie jest iloczynem liczb pierwszych. Ponieważ N musi liczbą złożoną to możemy zapisać jako N = a b gdzie a, b > 1. To jest

.

Wykazaliśmy, że twierdzenie jest prawdziwe dla a i b ponieważ N było kontrprzykładem. Stąd są to liczby takie, że

i liczby takie, że

.

Stąd

,

co jest sprzecznością.

Inny sposób udowodnienia twierdzenia

Za pomocą indukcji matematycznej.

Twierdzenie jest prawdziwe dla N = 2.

Załóżmy, że twierdzenie jest prawdziwe dla wszystkich

N + 1 jest albo liczbą pierwszą, albo złożoną. If N + 1 jest liczbą pierwszą, wtedy twierdzenie jest prawdziwe dla

Jeśli N + 1 jest liczbą złożoną, wtedy N + 1 jest podzielne przez pewną liczbę pierwszą , więc możemy zapisać jako iloczyn i pewnych liczb .

Stąd, N + 1 możemy zapisać jako iloczyn liczb pierwszych.

Wynika z tego, że twierdzenie jest prawdziwe dla wszystkich i przez indukcję matematyczną dla wszystkich liczb .

Twierdzenie 5[edytuj]

Istnieje nieskończenie wiele liczb pierwszych.

Dowód:

Załóżmy, że istnieje tylko liczb pierwszych.

Oznaczmy te liczby pierwsze jako: .

Niech . Wtedy, albo n jest liczbą pierwszą, albo iloczynem liczb pierwszych. Jeśli jest iloczynem liczb pierwszych to musi być podzielna przez liczbę pierwszą dla niektórych . Jednakże, co oczywiście nie jest liczbą całkowitą: nie jest podzielna przez .

Stąd, nie jest iloczynem liczb pierwszych.

Jest to sprzecznością, jako w twierdzeniu 4 wszystkie liczby mogą być wyrażone jako iloczyn liczb pierwszych.

Dlatego, albo jest liczbą pierwszą, albo jest podzielna przez pewną liczbą pierwszą większa od .

Wywnioskowaliśmy, że założenie, że istnieje tylko liczb pierwszych jest fałszywe.

W ten sposób udowodniliśmy, że istnieje nieskończenie wiele liczb pierwszych.

Twierdzenie 6[edytuj]

Dzielenie z najmniejszą nieujemną resztą

Niech a i b będą liczbami całkowitymi, gdzie . Wtedy będą istnieć liczby całkowite q i r takie, że

i .

Dowód:

Określmy zbiór

który jest niepusty i ograniczony z góry.Stąd maksymalny elementy oznaczyliśmy przez q.

Przekształćmy: . Jest to i , ponieważ inaczej

.

Oznacza to

co jest sprzeczne z maksymalnym q w zbiorze M.

Udowodnimy teraz unikalność q i r:

Niech i będą dwoma liczbami całkowitymi, które spełniają i . Jest to

dlatego który oznacza . To również pokazuje .