Wikipedia - Dzielnik

Wikipedia - kopia Wikipedii, wolnej encyklopedii

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
- 2.1 Cechy podzielności
  - 2.1.1 Cechy podzielności dla liczb pierwszych
  - 2.1.2 Znajdowanie cech podzielności
- 2.2 Rozszerzenie na dowolne pierścienie
3 Źródła
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 $\tfrac{12}{5} = 2,4$ liczba 5 jest dzielnikiem.

[edytuj] Dzielnik jako przeciwieństwo wielokrotności

W dowolnym zbiorze $S\;$ , w którym zdefiniowano mnożenie (w półgrupie) można wprowadzić relację podzielności, oznaczaną symbolem : $y|x\;$ wtedy i tylko wtedy, gdy istnieje element $z\in S$ taki, że $y\cdot z=x$ . Wówczas element x można nazwać wielokrotnością y, a element y - dzielnikiem x. Przy takim określeniu, jeżeli w zbiorze S istnieje element zerowy, to każdy element jest jego dzielnikiem (na przykład w zbiorze liczb całkowitych 0 jest wielokrotnością każdej liczby i każda liczba jest dzielnikiem 0). W zależności od potrzeb powyższą definicje uzupełnia się dodatkowymi warunkami, np.:

jeśli chcemy zdefiniować działanie dzielenia, to jego wynik powinien być określony jednoznacznie, wówczas dodajemy warunek $y\not= 0$ (patrz dzielenie przez zero).Tę definicje przyjmuje się zazwyczaj w teorii pierścieni. Wówczas definicję dzielnika można sformułować inaczej: $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ą. W tym sensie w ciele liczb rzeczywistych jedynym dzielnikiem zera jest zero.
jeśli pożądane jest, aby w zbiorze liczb całkowitych rozpatrywać tylko dzielniki dodatnie, dodaje się warunek $y>0\;$ , wówczas przy wymienianiu dzielników nie pisze się liczb ujemnych, mówi się np. że liczba pierwsza jest liczbą posiadającą dokładnie 2 dzielniki, gdy przy poprzedniej definicji każda liczba pierwsza posiada 4 dzielniki: $1,p,-1,-p.\;$

W teorii liczb liczbę wszystkich dzielników dodatnich liczby $n\;$ oznacza się przez $\sigma_0(n)\;$ (patrz funkcja sigma, inne stosowane oznaczenia: $\sigma_0(n)=d(n)=\tau(n)\;$ ), a sumę dzielników przez $\sigma (n)\;$ , na przykład $d(10) = 4\;$ oraz $\sigma (10)= 18\;$ (10 ma 4 dzielniki dodatnie, a ich suma jest równa 18).

[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 reprezentuje liczbę parzystą, czyli jest jedną z cyfr: 0, 2, 4, 6, 8.
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 łatwiej 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 można 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. Nie ma znaczenia, czy miejsca parzyste i nieparzyste liczymy od lewej, czy od prawej. Przykład:

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

854073 jest podzielna przez 11

Przepis ten funkcjonuje nie tylko w zapisie dziesiętnym ale również dla zapisów o innych niż 10 podstawach, jako kryterium podzielności przez liczbę o 1 większą od podstawy.

Liczba jest podzielna przez 12, jeśli jest podzielna zarówno przez 3 jak 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. dla 85527 mamy 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 jak i przez 7.
Liczba jest podzielna przez 15, jeśli jest podzielna zarówno przez 3 jak i przez 5.
Liczba jest podzielna przez 18, jeśli jest podzielna zarówno przez 2 jak 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 jak i przez 7.
Liczba jest podzielna przez 22, jeśli jest podzielna zarówno przez 2 jak i przez 11.
Liczba jest podzielna przez 24, jeśli jest podzielna zarówno przez 3 jak 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 10101, jeśli jest podzielna zarówno przez 111, przez 13 jak i przez 7.
Liczba jest podzielna przez 31704225257, jeśli jest podzielna zarówno przez 2251 jak i przez 6257.
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:

Inna cecha podzielności przez 7, 11 lub 13, oparta na równości $7\cdot 11 \cdot 13 = 1001\;$ :

grupujemy cyfry po 3 od końca i każdą taką grupę poczynając od pierwszej z prawej oznaczamy przez a1, a2, a3, ... . Dana liczba dzieli się przez 7, 11, 13 jeśli suma S = a1 - a2 + a3 - ... jest podzielna przez 7, 11, 13. Np. dla liczby x = 111220336444 mamy: 444-336+220-111=217, co dzieli się przez 7, a nie dzieli przez 11 i 13, zatem x dzieli się przez 7, a nie dzieli przez 11 ani przez 13.

Liczba jest podzielna przez $n\;$ , jeśli jest ona podzielna przez $k\;$ i $l, n = k \cdot l\;$ oraz $k\;$ i $l\;$ są liczbami względnie pierwszymi.

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 \cdot l$ oraz $k\;$ i $l\;$ są względnie pierwsze, wiemy że aby sprawdzić podzielność liczby, należy sprawdzić podzielność przez każdy z czynników dzielnika, 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^2\cdot 3\cdot 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\cdot m-1\;$ jest podzielne przez $p\;$ (inaczej: dla pewnego $k\;$ liczba $k\cdot p+1=10\cdot m$ )
Wówczas, jak łatwo sprawdzić, $10\cdot (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 (złożone obliczeniowo) – nie są znane żadne algorytmy o zadowalającej szybkości, mimo że nowe algorytmy wykorzystują wiele głębokich rezultatów teorii liczb.

[edytuj] Znajdowanie cech podzielności

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

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 podzielna przez 7 bo: 000864 + 197523 + 713913 + 580247 = 1492547, dalej: 000001 + 492547 = 492548 i 492548 / 7 = 70364
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 dla liczb w zapisie dwójkowym wyznaczamy następująco:

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

Cechę podzielności przez 4 dla liczb w zapisie szesnastkowym wyznaczamy podobnie:

$1 / 4 = 0,4_{16}\;$ – mamy jedną cyfrę po przecinku czyli liczba dzieli się przez 4 gdy liczba zapisana jej ostatnią cyfrą się dzieli.

[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 liczb całkowitych) aby jeden z dzielników reprezentował inne, stowarzyszone z nim.

Dzielniki jedynki (elementu neutralnego mnożenia) zwane są jednościami. W pierścieniu liczb całkowitych jednościami są liczby -1 i 1. Dzielnik, który nie jest stowarzyszony i nie jest jednością, zwany jest dzielnikiem właściwym.

Dzielnik nierozkładalny to taki dzielnik, który nie jest jednością i nie posiada dzielników właściwych.

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 $x\;$ i $y\;$ . Jest on określony z dokładnością do stowarzyszenia.

[edytuj] Źródła

F. Reinhardt, H. Soeder: Atlas matematyki. Warszawa: Prószyński i S-ka. ISBN 83-7469-189-1.
A. Mostowski, M. Stark: Elementy algebry wyższej. Wyd. 7. Warszawa: Państwowe Wydawnictwo Naukowe, 1974.
R. L. Graham, D. E. Knuth, O. Patashnik: Matematyka konkretna. Wyd. 4. Warszawa: Państwowe Wydawnictwo Naukowe, 2006. ISBN 83-01-14764-4.

[edytuj] Zobacz też

Zobacz w Wikiźródłach Tablica liczb pierwszych i rozkładów na czynniki pierwsze

[edytuj] Linki zewnętrzne

Witryna Math Forum @Drexel
Cechy podzielności. [dostęp 28 września 2008].