Elementarna teoria liczb/Elementy podzielności liczb
Elementy podzielności liczb
edytujPodzielność 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
edytujLiczbą 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
edytujZałóż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
edytujJeś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
edytujJeś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
edytujPodstawowe 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
edytujIstnieje 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
edytujDzielenie 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 .