Dzielnik

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Ten artykuł dotyczy pojęcia w matematyce. Zobacz też: miejscowość o tej nazwie.

Dzielnik w matematyce ma dwa różne znaczenia.

Spis treści

1 Dzielnik jako operand w dzieleniu
2 Dzielnik jako przeciwieństwo wielokrotności
3 Zobacz też
4 Linki zewnętrzne:

[edytuj] Dzielnik jako operand w dzieleniu

Dzielnikiem przy dzieleniu nazywa się liczbę, przez którą się dzieli. Na przykład w dzieleniu 12 / 4 = 3 liczba 4 jest dzielnikiem.

[edytuj] Dzielnik jako przeciwieństwo wielokrotności

Dzielnikiem dowolnej liczby całkowitej x nazywa się liczbę całkowitą y, dla której istnieje takie z należące do liczb całkowitych, że $y z = x$ . Innymi słowy, y jest dzielnikiem x, gdy przy dzieleniu x przez y otrzymuje się resztę 0. Dzielnik jest synonimem podwielokrotności będącej liczbą całkowitą.

Badaniem podzielności w zakresie liczb całkowitych zajmuje się teoria liczb. Często przez dzielnik liczby rozumie się dzielnik dodatni; wówczas przy wymienianiu dzielników nie pisze się liczb ujemnych (zobacz wyjaśnienie niżej), mówi się np. że liczba pierwsza jest liczbą posiadającą dokładnie 2 dzielniki; w rzeczywistości każda liczba pierwsza posiada 4 dzielniki: 1, p, -1, -p.

W teorii liczb liczbę wszystkich dzielników dodatnich oznacza się przez funkcję sigma $d (n)$ , np. $d (10) = 4$ (10 ma 4 dzielniki dodatnie).

[edytuj] Rozszerzenie na dowolne pierścienie

Definicję dzielnika można łatwo rozszerzyć na dowolne pierścienie całkowite. Jeżeli x jest dzielnikiem y a y jest dzielnikiem x wówczas liczby x i y nazywa się stowarzyszonymi. Relacja stowarzyszenia jest relacją równoważności. Jeżeli x jest dzielnikiem y to każda liczba stowarzyszona z x jest też dzielnikiem y. Dlatego też w zbiorze dzielników tradycyjnie wyróżnia się pewne elementy (np. liczby dodatnie w pierścieniu Z) aby jeden z dzielników reprezentował inne, stowarzyszone z nim.

Badaniem podzielności w pierścieniach zajmuje się teoria podzielności.

Największy dzielnik elementu x, który jest równocześnie dzielnikiem y nazywa się największym wspólnym dzielnikiem liczb x i y. Jest on określony z dokładnością do stowarzyszenia.

[edytuj] Cechy podzielności

Aby zbadać podzielność wielkich liczb, nie trzeba wykonywać żmudnego dzielenia. Wystarczy sprawdzić odpowiednie cechy podzielności. W systemie dziesiętnym następujące warunki (konieczne i dostateczne) pozwalają stwierdzić podzielność znacznie mniejszym nakładem pracy:

Każda liczba całkowita jest podzielna przez 1.
Liczba jest podzielna przez 2 (jest liczbą parzystą), jeśli ostatnia z jej cyfr jest parzysta, czyli jest jedną z liczb: 2, 4, 6, 8 lub jest 0.
Liczba jest podzielna przez 3, jeśli suma cyfr tej liczby jest podzielna przez 3. Przykład: 104628: suma cyfr 1+0+4+6+2+8=21, 21: 2+1=3, jest podzielna przez 3.
Liczba jest podzielna przez 4, jeśli liczba tworzona przez jej dwie ostatnie cyfry jest podzielna przez 4.
Liczba jest podzielna przez 5, jeśli jej ostatnią cyfrą jest 0 lub 5.
Liczba jest podzielna przez 6, jeśli jest podzielna zarówno przez 2, jak i przez 3.
Liczba jest podzielna przez 7, jeśli suma jej cyfr mnożonych (od prawej) przez kolejne potęgi 3 (włącznie z potęgą zerową: 3⁰=1) jest podzielna przez 7.

Przykład:

1757	:	1·27+7·9+5·3+7·1=112	1761	:	1·27+7·9+6·3+1·1=109
112	:	1·9+1·3+2·1=14	109	:	1·9+0·3+9·1=18
14	:	1·3+4·1=7	18	:	1·3+8·1=11
			11	:	1·3+1·1=4
Liczba 1757 oraz 112 i 14 są podzielne przez 7.			Liczba 1761 oraz 109, 18, 11 i 4 nie dzielą się przez 7.

Liczba jest podzielna przez 8, jeśli liczba tworzona przez jej trzy ostatnie cyfry jest podzielna przez 8.
Liczba jest podzielna przez 9, jeśli suma cyfr tej liczby jest podzielna przez 9.
Liczba jest podzielna przez 10, jeśli jej ostatnią cyfrą jest 0.
Liczba jest podzielna przez 11, jeśli po odjęciu od sumy cyfr stojących na miejscach parzystych, sumy cyfr stojących na miejscach nieparzystych otrzymamy liczbę podzielną przez 11. Przykład:

Liczba 854073 -> (8+4+7) - (5+0+3) = 19 - 8 = 11

854073 jest podzielna przez 11

Liczba jest podzielna przez 12, jeśli jest podzielna zarówno przez 3 i przez 4.
Liczba jest podzielna przez 13, jeśli różnica liczby złożonej z trzech ostatnich cyfr i liczby złożonej z pozostałych liczb jest podzielna przez 13, np. 85527 -> 527 - 85 = 442, 442 / 13 = 34, więc 85527 jest podzielna przez 13.
Liczba jest podzielna przez 14, jeśli jest podzielna zarówno przez 2 i przez 7.
Liczba jest podzielna przez 15, jeśli jest podzielna zarówno przez 3 i przez 5.
Liczba jest podzielna przez 18, jeśli jest podzielna zarówno przez 2 i przez 9.
Liczba jest podzielna przez 20, jeśli jest podzielna zarówno przez 4 i przez 5.

Skoro 20=2·10, to liczba jest podzielna przez 20, gdy jest podzielna przez 10 i potem jeszcze iloraz jest podzielny przez 2 – czyli gdy jej ostatnią cyfrą jest 0, zaś przedostatnią jest 0, 2, 4, 6 albo 8.

Reasumując, liczba jest podzielna przez 20 jeśli jej ostatnia cyfra jest równa 0 a przedostatnia cyfra jest parzysta.

Liczba jest podzielna przez 21, jeśli jest podzielna zarówno przez 3 i przez 7.
Liczba jest podzielna przez 22, jeśli jest podzielna zarówno przez 2 i przez 11.
Liczba jest podzielna przez 24, jeśli jest podzielna zarówno przez 3 i przez 8.
Liczba jest podzielna przez 25, jeśli jej dwie ostatnie cyfry to 00, 25, 50 lub 75.
Liczba jest podzielna przez 26, jeśli jest podzielna zarówno przez 2 jak i przez 13.
Liczba jest podzielna przez 28, jeśli jest podzielna zarówno przez 4 jak i przez 7.
Liczba jest podzielna przez 30, jeśli jest podzielna zarówno przez 2, 3 i 5. Inaczej - suma cyfr jest podzielna przez 3, a zapis dziesiętny liczby kończy się zerem.
Liczba jest podzielna przez 2ⁿ, jeśli liczba utworzona z n jej ostatnich cyfr jest podzielna przez 2ⁿ.
Liczba jest podzielna przez 5ⁿ, jeśli liczba utworzona z n jej ostatnich cyfr jest podzielna przez 5ⁿ.
Liczba jest podzielna przez 10ⁿ, jeśli n jej ostatnich cyfr jest zerami.

Inne zasady:

Liczba jest podzielna przez n, jeśli jest ona podzielna przez k i l, $n = k * l$ oraz k i l są liczbami wzglednie pierwszymi.
Zero jest podzielne przez każdą liczbę.

Zasady te można udowodnić używając kongruencji.

[edytuj] Cechy podzielności dla liczb pierwszych

Na podstawie przedostatniego stwierdzenia z poprzedniej sekcji wiemy, że aby sprawdzić np. podzielność liczby 25116 przez 84, należy sprawdzić podzielność przez każdy z czynników dzielnika, tj. liczba badana powinna dzielić się przez każdą z liczb: 4, 3 i 7 (bo rozkład dzielnika na czynniki pierwsze ma postać: 84=2²·3·7) W tym kontekście ważne staje się ustalenie cech podzielności dla liczb pierwszych. Dość ogólną metodę konstruowania takich cech podzielności podaje Stephen Froggatt w serwisie Math Forum. Oto algorytm budowania cechy podzielności dla dowolnej liczby pierwszej p:

Szukamy najmniejszej liczby naturalnej m, dla której 10·m - 1 jest podzielne przez p (inaczej: dla pewnego k liczba k·p+1 = 10·m)
Wówczas, jak łatwo sprawdzić, 10·(p-m)+1 także dzieli się przez p.
Mamy do wyboru dwa sposoby postępowania:

a) od badanej liczby x oddzielamy cyfrę jedności, mnożymy przez m i dodajemy do pozostałej części liczby x albo

b) od x oddzielamy cyfrę jedności, mnożymy ją przez (m-p) i odejmujemy od pozostałej części liczby x.

Jeśli otrzymana (mniejsza) liczba dzieli się przez p, to i x dzieli się przez p. Jeśli otrzymana liczba jest jeszcze zbyt duża, można to postępowanie stosować wielokrotnie.

Zbudujmy np. cechę podzielności przez 7 (inną, niż opisana powyżej).

Ponieważ 10·5-1=49 dzieli się przez 7, więc m=5 i aby zbadać, czy liczba 25116 dzieli się przez 7 postępujemy następująco: Oddzielamy cyfrę jedności: 6 i obliczamy: 2511+6·5 = 2541. Powtarzamy ten krok jeszcze dwukrotnie:254+1·5 = 259; 25+9·5 = 70, co oczywiście dzieli się przez 7. Zatem liczba 25116 dzieli się przez 7 ( a jak łatwo sprawdzić, dzieli się też przez 4 i 3, więc dzieli się przez 84). Analogicznie działa wersja (b): m-p=7-5=2, więc: 2511-6·2=2499; 249-9·2=231; 23-1 ·2=21, co dzieli się przez 7, więc badana liczba 25116 dzieli się przez 7. Poniższa tabelka podaje czynniki m oraz (p-m) dla liczb pierwszych z zakresu 6 < p < 100.

dzielnik pierwszy p	czynnik m	czynnik p-m	zalecany algorytm
7	5	2	(+5c)
11	10	1	(+10c)
13	4	9	(+4c)
17	12	5	( -5c)
19	2	17	(+2c)
23	7	16	(+7c)
29	3	26	(+3c)
31	28	3	(-3c)
37	26	11	( -11c)
41	37	4	(-4c)
47	33	14	( -14c) lub (+33c)
53	16	37	(+16c)
59	6	53	(+6c)
61	55	6	(-6c)
67	47	20	( -20c)
71	64	7	(-7c)
73	22	51	( +22c)
79	8	71	(+8c)
83	25	58	( +25c)
89	9	80	(+9c) lub (–80c)
97	68	29	(+68c) lub (–29c)

itd. W kolumnie „zalecany algorytm” zapis: ( +6c) oznacza: „pomnóż ostatnią cyfrę przez 6 i dodaj do pozostałej części liczby”, a (–7c) – „pomnóż ostatnią cyfrę przez 7 i odejmij od pozostałej części liczby”. Zalecany wybór wariantu algorytmu podyktowany jest przede wszystkim wygodą wykonania jednego z wariantów mnożenia.

Odrębnym, znacznie trudniejszym zagadnieniem jest badanie podzielności i rozkładanie na czynniki, czyli faktoryzacja bardzo dużych liczb (to znaczy liczb stucyfrowych i większych). Tego typu rozkłady znalazły zastosowanie w kryptografii. Jednak zadanie rozkładu na czynniki pierwsze liczb o 100 i więcej cyfrach jest trudne ("obliczeniowo złożone") – nie są znane żadne algorytmy o zadowalającej sprawności mimo, że nowe algorytmy wykorzystują wiele głębokich rezultatów teorii liczb.