Dzielnik

Z Wikipedii

Dzielnik w matematyce ma dwa różne znaczenia.

Spis treści 1 Dzielnik jako operand w dzieleniu 2 Dzielnik jako przeciwieństwo wielokrotności 2.1 Rozszerzenie na dowolne pierścienie 2.2 Cechy podzielności 2.3 Cechy podzielności dla liczb pierwszych 3 Znajdywanie cech podzielności 4 Zobacz też 5 Linki zewnętrzne:

[edytuj] Dzielnik jako operand w dzieleniu

Dzielnikiem przy dzieleniu nazywa się liczbę, przez którą się dzieli. Na przykład w działaniu 12 / 5 = 2.4 liczba 5 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 yz = 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. W praktyce należy wziąć liczbę tworzoną przez trzy ostatnie cyfry, podzielić ją przez dwa i sprawdzić podzielność przez cztery.
• Liczba jest podzielna przez 9, jeśli suma cyfr tej liczby jest podzielna przez 9. Jeśli wynik sumowania jest wielocyfrowy sumowanie należy powtarzać dla wyniku sumowania.
• 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 cyfr 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 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 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 względnie pierwszymi.
• Zero jest podzielne przez każdą liczbę.

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

[edytuj] Cechy podzielności dla liczb pierwszych

Z twierdzenia, że liczba jest podzielna przez n, jeśli jest ona podzielna przez k i l, n = k * l oraz k i l są liczbami względnie pierwszymi, wiemy że aby sprawdzić podzielność liczby, należy sprawdzić podzielność przez każdy z czynników dzielnika, tj. np. podzielność 25116 przez 84 oznacza, że liczba ta 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:

1. 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)
2. Wówczas, jak łatwo sprawdzić, 10·(p-m)+1 także dzieli się przez p.
3. 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.

[edytuj] Znajdywanie cech podzielności

Jedną z metod wyznaczania cech podzielności przez n jest zbadanie odwrotności liczby n. Zachodzą tu dwie możliwości:

1. otrzymujemy ułamek okresowy o długości okresu k cyfr. Dana liczba jest podzielna przez n gdy suma k-cyfrowych grup dzieli się przez n.

Np. niech n = 7; odwrotność 1/n = 0,(142857) – długość okresu k = 6

Liczba = 864197523713913580247 jest przez 7 podzielna bo: 000864 + 197523 + 713913 + 580247 = 1492547, dalej: 000001 + 492547 = 492548 i 492548 / 7 = 70364

2. otrzymujemy liczbę o k cyfrach po przecinku. Dana liczba jest podzielna przez n gdy liczba z k ostatnich cyfr tej liczby dzieli się przez n.

Np. niech n = 8; odwrotność 1/n = 0,125 – mamy trzy cyfry po przecinku czyli liczba dzieli się przez 8 gdy liczba z jej trzech ostatnich cyfr się dzieli.

Ten przepis funkcjonuje we wszystkich potęgowych systemach pozycyjnych.

Np. cechę podzielności przez 5 w dla liczb w zapisie dwójkowym wyznaczamy:

1 / 5 = 0,2 = (BIN) 0,(0011) – długość okresu k = 4, więc dana liczba jest podzielna przez 5 gdy suma 4-cyfrowych grup dzieli się przez 5.

A cechę podzielności przez 4 dla liczb w zapisie szesnastkowym:

1 / 4 = (HEX) 0,4 – mamy jedną cyfrę po przecinku czyli liczba dzieli się przez 4 gdy liczba zapisana jej ostatnią cyfrą się dzieli.

[edytuj] Zobacz też

• przegląd zagadnień z zakresu matematyki,
• czynnik pierwszy,
• Z modulo n,
• ciało Zp
• liczby doskonałe

[edytuj] Linki zewnętrzne:

witryna Math Forum @Drexel