Elementarna teoria liczb/Elementy podzielności liczb

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  .


« Aksjomaty dla liczb całkowitych