Elementarna teoria liczb/Elementy podzielności liczb

Z Wikibooks, biblioteki wolnych podręczników.

Spis treści

[edytuj] Elementy podzielności liczb

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 123456=643\cdot192\,.

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

[edytuj] Liczby pierwsze

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 numer 1 nie jest uważany za liczbę pierwszą chociaż nie posiada innych dzielników niż siebie. Przyczyny tego będą omówione później.

[edytuj] Twierdzenie 1

Załóżmy, że a,b,d,r,\, i s\, są liczbami całkowitymi i d|a,d|b \,. Wtedy d|(ra+sb) \,.

Dowód
Istnieje e \, i f \, taki, że a=de \, i b=df \,. Dlatego:

ra+sb=rde+sdf =d (re+sf) .\,

Wiemy, że re + sf \, jest także liczbą całkowitą, stąd d|(ra+sb) \,.

Wniosek
Załóżmy, że a,b,d\, i r \, są liczbami całkowitymi i d|a,d|b\,. Wtedy d|(a+b), d|(a-b), \, i d|ra \,.

[edytuj] Twierdzenie 2

Jeśli a, b, c \, są liczbami całkowitymi i a|b, b|c \, wtedy a|c \,.

Dowód
Zapiszmy b jako b=ad \, i c jako c=be \, dla kilku liczb całkowitych d\, i e\, .

Wynika z tego, że:
c=ade=a\left(de\right) \, , więc a|c \, .

[edytuj] Twierdzenie 3

Jeśli a,b,c \, są liczbami całkowitymi i c \neq 0 , a następnie a|b \, wtedy i tylko wtedy, gdy ac|bc \, Dowód:

a|b \, implies that there exists an integer d such that

b=ad \,

Więc wynika z tego, że

bc=\left(ac\right)d i stąd ac|bc \,.

Z drugiej strony możemy zauważyć, że ac|bc \, implies there exists an integer d \, such that

bc=\left(ac\right)d.

Wiemy, że c ma być różne od zera, stąd

b=ad \,.

Twierdzenie udowodnione.

[edytuj] Twierdzenie 4

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

1 < a,b < N.

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

a=p_1p_2\cdots p_k

i liczby q_1,q_2,\dots,q_l takie, że

b=q_1q_2\cdots q_l.

Stąd

N = ab = p_1p_2\cdots p_kq_1q_2\cdots q_l,

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 k \le N

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

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

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

Wynika z tego, że twierdzenie jest prawdziwe dla wszystkich k \le N+1 i przez indukcję matematyczną dla wszystkich liczb \N .

[edytuj] Twierdzenie 5

Istnieje nieskończenie wiele liczb pierwszych.

Dowód:

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

Oznaczmy te liczby pierwsze jako: p_1,p_2,...,p_k \,.

Niech n=p_1p_2...p_k+1. \, . Wtedy, albo n jest liczbą pierwszą, albo iloczynem liczb pierwszych. Jeśli jest iloczynem liczb pierwszych to musi być podzielna przez liczbę pierwszą pi dla niektórych i. Jednakże, \frac{n}{p_i} = \frac{p_1p_2...p_k+1}{p_i} = p_1p_2...p_{i-1}p_{i+1}...p_k + \frac{1}{p_i} co oczywiście nie jest liczbą całkowitą: n nie jest podzielna przez pi.

Stąd, n \, 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 n \, jest liczbą pierwszą, albo jest podzielna przez pewną liczbą pierwszą większa od p_k \, .

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

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

[edytuj] Twierdzenie 6

Dzielenie z najmniejszą nieujemną resztą

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

a = bq + r

i 0\leq r < b.

Dowód:

Określmy zbiór

M = \{x\in \Z \mid x \leq \frac{a}{b} \}

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

Przekształćmy: r = a − bq. Jest to r = a - bq \geq a - b \frac{a}{b} = a-a = 0 i r < b, ponieważ inaczej

b \leq r = a-bq.

Oznacza to

q+1 \leq \frac{a}{b}

co jest sprzeczne z maksymalnym q w zbiorze M.

Udowodnimy teraz unikalność q i r:

Niech q' i r' będą dwoma liczbami całkowitymi, które spełniają a = bq' + r' i 0\leq r'<b. Jest to

| b(q − q') | = | r' − r | < b

dlatego | q − q' | < 1 który oznacza q = q'. To również pokazuje r = r'.


Spis treści
Źródło „http://pl.wikibooks.org/wiki/Elementarna_teoria_liczb/Elementy_podzielno%C5%9Bci_liczb”