Cecha podzielności

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Cecha podzielności – metoda umożliwiająca stwierdzenie, czy dana liczba jest podzielna bez reszty przez inną. Są one narzędziami pomocniczymi ułatwiającymi sprawdzenie czynników liczby bez uciekania się do dzielenia. Choć podobne reguły mogą być ułożone dla dowolnej podstawy, to niżej zawarto tylko reguły dotyczące systemu dziesiętnego.

Cechy podzielności[edytuj | edytuj kod]

  • 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:3=7, 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ą: 30=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.
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 mniejszą od podstawy.
  • 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 50, jeśli jej przedostatnia cyfra to 5 lub 0, a ostatnia to 0.
  • Liczba jest podzielna przez 100, jeśli jej ostanie dwie cyfry to 00.
  • Liczba jest podzielna przez 10101, jeśli jest podzielna zarówno przez 111 (czyli 3 i 37), przez 13 jak i przez 7.
  • Liczba jest podzielna przez 2n, jeśli liczba utworzona z n jej ostatnich cyfr jest podzielna przez 2n.
  • Liczba jest podzielna przez 5n, jeśli liczba utworzona z n jej ostatnich cyfr jest podzielna przez 5n.
  • Liczba jest podzielna przez 10n, 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\;liczbami względnie pierwszymi.
  • Liczba jest podzielna przez 2,5 i 10 jeśli jej ostatnia cyfra to 0

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

Liczby pierwsze[edytuj | edytuj kod]

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

{| border=1

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

Wyznaczanie[edytuj | edytuj kod]

Jedną z metod wyznaczania cech podzielności przez n\;, gdzie n\; jest liczbą pierwszą lub potęgą takowej, jest zbadanie odwrotności owej liczby. 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.

Dowody podzielności przez 9 i 11[edytuj | edytuj kod]

Information icon.svg Zobacz też: kongruencja.

Jeżeli w(x)\; jest wielomianem całkowitym względem x o współczynnikach całkowitych, to kongruencja a\equiv b \pmod m pociąga za sobą w(a)\equiv w(b) \pmod m.

Niech A_{0} x^{n} + A_{1} x^{n-1} + A_{2} x^{n-2} + \ldots + A_{n-1} x + A_{n}\quad będzie wielomianem całkowitym n-tego stopnia o współczynnikach całkowitych (wielomian ten oznaczamy krótko przez w(x)), m będzie danym modułem, zaś a i b liczbami całkowitymi przystającymi według modułu m. Zapiszemy ciąg kongruencji następująco:

A_{0} a^{n}\equiv A_{0} b^{n} \pmod m,
A_{1} a^{n-1}\equiv A_{1} b^{n-1}\pmod m,
A_{n-1} a \equiv A_{n-1} b \pmod m,
A_{n}\equiv A_n \pmod m.

Dodajemy stronami,

A_{0} a^{n} + A_{1} a^{n-1} +\dots + A_{n-1} a + A_{n}\equiv A_{0} b^{n} + A_{1} b^{n-1} +\dots + A_{n-1} b + A_{n} \pmod m, czyli
w(a)\equiv w(b) \pmod m.

Niech N \in \mathbb N, a C_1,C_2,C_3,\dots ,C_n\quad jej kolejnymi cyframi w układzie dziesiętnym.

 N= C_{1}10^{n-1} + C_{2}10^{n-2} + \ldots + C_{n-1}10 +C_{n}\quad.

Niech

  • \quad w (x)= C_{1} x^{n-1} + C_{2} x^{n-2} + \ldots + C_{n-1} x + C_n\quad

i

  • \quad w(10)=N.\quad.

Podzielność przez 9[edytuj | edytuj kod]

Z lematu i wobec kongruencji 10\equiv1 \pmod 9\quad mamy

\quad w(1)= C_1 + C_2 + \ldots + C_{n-1} + C_n\quad, zatem
N\equiv C_1 + C_2 + C_3 + \ldots + C_{n-1} + C_n \pmod 9,

co dowodzi, że każda liczba naturalna przystaje według modułu 9 do sumy swoich cyfr. Dla podzielności liczby N przez 9 wystarcza, by suma jej cyfr była podzielna przez 9.

Podzielność przez 11[edytuj | edytuj kod]

Wobec lematu oraz kongruencji 10\equiv -1 \pmod {11}, mamy

w(10)\equiv w(-1) \pmod {11} ,

czyli

N \equiv C_1 - C_2 + C_3 - C_4 + \dots \pmod {11}.

Co oznacza podzielność przez 11: liczba jest podzielna przez 11, jeśli po odjęciu sumy cyfr stojących na miejscach nieparzystych od sumy cyfr stojących na miejscach parzystych otrzymamy liczbę podzielną przez 11.

Zobacz też[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

  1. Witryna Math Forum @Drexel (ang.)
  2. Cechy podzielności. [dostęp 28 września 2008].