Jakas reklama 

 

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

Dzielnik w matematyce ma dwa różne znaczenia.

Spis treści

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.:

  1. 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.
  2. 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:

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 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.

Inne zasady:

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.

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:

  1. 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)
  2. Wówczas, jak łatwo sprawdzić, 10\cdot (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 (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:

  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 podzielna przez 7 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 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

edytuj Zobacz też

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

edytuj Linki zewnętrzne

Teksty piosenek Akustycznie suplement Sax and Dance egipt last minute Teksty piosenek