Wikipedia

Cecha podzielności: Różnice pomiędzy wersjami

Artykuł Dyskusja

Cecha podzielności (edytuj)

Wersja z 18:59, 4 maj 2021

Usunięte 15 001 bajtów ,  1 rok temu
nie
m (Wycofano edycje użytkownika 188.146.166.123 (dyskusja). Autor przywróconej wersji to Salicyna.)
Znacznik: Wycofanie zmian
(nie)
Znaczniki: Zastąpiono Wycofane VisualEditor usuwanie dużej ilości tekstu (filtr nadużyć)
{{Dopracować|źródła=2010-10}}
'''Cecha podzielności''' – metoda umożliwiająca stwierdzenie, czy dana liczba jest [[dzielnik|podzielna]] bez [[Twierdzenie o dzieleniu z resztą|reszty]] przez inną. Są one narzędziami pomocniczymi ułatwiającymi sprawdzenie czynników liczby bez uciekania się do [[dzielenie|dzielenia]]. Choć podobne reguły mogą być ułożone dla dowolnej [[system liczbowy|podstawy]], to niżej zawarto tylko reguły dotyczące [[dziesiętny system liczbowy|systemu dziesiętnego]].
 
== Cechy podzielności ==
Liczba całkowita jest podzielna:
* przez 1 – 1 jest zawsze dzielnikiem, więc mówienie o cesze podzielności jest niepotrzebne.
* przez 2 (jest [[Parzystość liczb|liczbą parzystą]]), jeśli ostatnia z jej [[cyfra|cyfr]] reprezentuje liczbę parzystą, czyli jest jedną z cyfr: 0, 2, 4, 6, 8.
* przez 3, jeśli suma cyfr tej liczby jest podzielna przez 3 – dzięki temu regułę można stosować [[Rekurencja|rekurencyjnie]] aż do osiągnięcia liczby jednocyfrowej. Przykład: 104628: suma cyfr 1+0+4+6+2+8=21, 2+1=3, jest podzielna przez 3.
* przez 4, jeśli liczba tworzona przez jej dwie ostatnie cyfry jest podzielna przez 4. Przykład: 52136 bo 36/4=9 więc liczba 52136 jest podzielna przez 4. Natomiast wśród liczb od 1 do 100 podzielne przez 4 są te liczby, których:
** pierwsza cyfra jest nieparzysta (1, 3, 5, 7 lub 9), a druga to 2 lub 6
** pierwsza cyfra jest parzysta (0, 2, 4, 6 lub 8), a druga to 0, 4 lub 8
* przez 5, jeśli jej ostatnią cyfrą jest 0 lub 5.
* przez 6, jeśli jest podzielna zarówno przez 2, jak i przez 3.
* przez 7, jeśli suma jej cyfr mnożonych (od prawej) przez kolejne potęgi 3 (włącznie z potęgą zerową: 3<sup>0</sup>=1) jest podzielna przez 7. Przykład:
{|
| align=right| 1757 || &nbsp;:&nbsp; || 1·27+7·9+5·3+7·1=112
| &nbsp;&nbsp;
| align=right| 1761 || &nbsp;:&nbsp; || 1·27+7·9+6·3+1·1=109
|-
| align=right| 112 || &nbsp;:&nbsp; || 1·9+1·3+2·1=14
|
| align=right| 109 || &nbsp;:&nbsp; || 1·9+0·3+9·1=18
|-
| align=right| 14 || &nbsp;:&nbsp; || 1·3+4·1=7
|
| align=right| 18 || &nbsp;:&nbsp; || 1·3+8·1=11
|-
| &nbsp; || &nbsp; || &nbsp;
|
| align=right| 11 || &nbsp;:&nbsp; || 1·3+1·1=4
|-
| align=center colspan=3| Liczba 1757 oraz 112 i 14<br />są podzielne przez 7.
|
| align=center colspan=3| Liczba 1761 oraz 109, 18, 11 i 4<br />nie dzielą się przez 7.
|}
* przez 8, jeśli liczba tworzona przez jej trzy ostatnie cyfry jest podzielna przez 8. Natomiast owa trzycyfrowa końcówka jest podzielna przez 8, jeśli składa się z następujących cyfr:
 
{| class="wikitable"
|+
!Cyfra setek
!Cyfra dziesiątek
!Cyfra jedności
|-
| rowspan="4"| 0, 2, 4, 6 lub 8
|0, 4 lub 8
|0 lub 8
|-
|1, 5 lub 9
|6
|-
|2, 6
|4
|-
|3, 7
|2
|-
| rowspan="4"| 1, 3, 5, 7 lub 9
|0, 4 lub 8
|4
|-
|1, 5 lub 9
|2
|-
|2, 6
|0 lub 8
|-
|3, 7
|6
|}
 
* 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.
* przez 10, jeśli jej ostatnią cyfrą jest 0.
* przez 11, jeśli po odjęciu od sumy cyfr stojących na miejscach nieparzystych, sumy cyfr stojących na miejscach parzystych otrzyma się 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.
* przez 12, jeśli jest podzielna zarówno przez 3, jak i przez 4.
* 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 liczba 85527 jest podzielna przez 13.
* przez 14, jeśli jest podzielna zarówno przez 2, jak i przez 7.
* przez 15, jeśli jest podzielna zarówno przez 3, jak i przez 5.
* przez 16, jeśli liczba tworzona przez jej cztery ostatnie cyfry jest podzielna przez 16.
* przez 18, jeśli jest podzielna zarówno przez 2, jak i przez 9.
* przez 20, jeśli jej ostatnia cyfra jest równa 0 a przedostatnia cyfra jest parzysta.
* przez 21, jeśli jest podzielna zarówno przez 3, jak i przez 7.
* przez 22, jeśli jest podzielna zarówno przez 2, jak i przez 11.
* przez 24, jeśli jest podzielna zarówno przez 3, jak i przez 8.
* przez 25, jeśli jej dwie ostatnie cyfry to 00, 25, 50 lub 75.
* przez 26, jeśli jest podzielna zarówno przez 2, jak i przez 13.
* przez 28, jeśli jest podzielna zarówno przez 4, jak i przez 7.
* przez 30, jeśli suma cyfr jest podzielna przez 3, a zapis dziesiętny liczby kończy się zerem.
* przez 32, jeśli cyfra tworzona przez jej pięć ostatnich cyfr jest podzielna przez 32.
* przez 50, jeśli jej przedostatnia cyfra to 5 lub 0, a ostatnia to 0.
* przez 100, jeśli jej ostatnie dwie cyfry to 00.
* przez 2<sup>n</sup>, jeśli liczba utworzona z ''n'' jej ostatnich cyfr jest podzielna przez 2<sup>n</sup>.
* przez 5<sup>n</sup>, jeśli liczba utworzona z ''n'' jej ostatnich cyfr jest podzielna przez 5<sup>n</sup>.
* przez 10<sup>n</sup>, jeśli ''n'' jej ostatnich cyfr jest zerami.
 
Inne zasady:
* Inna cecha podzielności przez 7, 11 lub 13, oparta na równości <math>7\cdot 11 \cdot 13 = 1001{:}</math>
 
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 <math>n,</math> jeśli jest ona podzielna przez <math>k</math> i <math>l, n = k \cdot l</math> oraz <math>k</math> i <math>l</math> są [[liczby względnie pierwsze|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 [[Arytmetyka modularna#Przystawanie|kongruencji]].
 
== Liczby pierwsze ==
Z twierdzenia, że liczba jest podzielna przez <math>n,</math> jeśli jest ona podzielna przez <math>k</math> i <math>l, n = k \cdot l</math> oraz <math>k</math> i <math>l</math> są [[liczby względnie pierwsze|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 [[czynnik pierwszy|czynniki pierwsze]] ma postać: <math>84=2^2\cdot 3\cdot 7</math>)
W tym kontekście ważne staje się ustalenie cech podzielności dla [[liczba pierwsza|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 <math>m,</math> dla której <math>10\cdot m-1</math> jest podzielne przez <math>p</math> (inaczej: dla pewnego <math>k</math> liczba <math>k\cdot p+1=10\cdot m</math>)
# Wówczas, jak łatwo sprawdzić, <math>10\cdot (p-m)+1</math> także dzieli się przez <math>p.</math>
# Mamy do wyboru dwa sposoby postępowania:
:: a) od badanej liczby <math>x</math> oddzielamy cyfrę jedności, mnożymy przez <math>m</math> i dodajemy do pozostałej części liczby <math>x</math> albo
:: b) od <math>x</math> oddzielamy cyfrę jedności, mnożymy ją przez <math>m-p</math> i odejmujemy od pozostałej części liczby <math>x.</math>
 
Jeśli otrzymana (mniejsza) liczba dzieli się przez <math>p,</math> to i <math>x</math> dzieli się przez <math>p.</math>
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 <math>m</math> oraz <math>p-m</math> dla liczb pierwszych z zakresu <math>6 < p < 100.</math>
{| class="wikitable"
! dzielnik pierwszy <math>p</math>
! czynnik <math>m</math>
! czynnik <math>p-m</math>
! 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 [[Rozkład na czynniki|faktoryzacja]] bardzo dużych liczb (to znaczy liczb stucyfrowych i większych). Tego typu rozkłady znalazły zastosowanie w [[Kryptologia|kryptografii]]. Jednak zadanie rozkładu na czynniki pierwsze liczb o 100 i więcej cyfrach jest trudne ([[złożoność obliczeniowa|złożone obliczeniowo]]) – nie są znane żadne [[algorytm]]y o zadowalającej szybkości, mimo że nowe algorytmy wykorzystują wiele głębokich rezultatów teorii liczb.
 
== Wyznaczanie ==
Jedną z metod wyznaczania cech podzielności przez <math>n,</math> gdzie <math>n</math> jest liczbą pierwszą lub potęgą takowej, jest zbadanie odwrotności owej liczby. Zachodzą tu dwie możliwości:
# otrzymujemy ułamek okresowy o długości okresu <math>k</math> cyfr. Dana liczba jest podzielna przez <math>n,</math> gdy suma <math>k</math>-cyfrowych grup dzieli się przez <math>n.</math>
#: Np. niech <math>n = 7;</math> odwrotność <math>1/n = 0{,}(142857)</math> – długość okresu <math>k = 6</math>
#: Liczba 864197523713913580247 jest podzielna przez 7 bo: 000864 + 197523 + 713913 + 580247 = 1492547, dalej: 000001 + 492547 = 492548 i 492548 / 7 = 70364
# otrzymujemy liczbę o <math>k</math> cyfrach po przecinku. Dana liczba jest podzielna przez <math>n,</math> gdy liczba z <math>k</math> ostatnich cyfr tej liczby dzieli się przez <math>n.</math>
#: Np. niech <math>n = 8,</math> odwrotność <math>1/n = 0{,}125</math> – 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:
: <math>1 / 5 = 0{,}2 = 0{,}(0011)_2</math> – długość okresu <math>k = 4,</math> 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:
: <math>1 / 4 = 0{,}4_{16}</math> – 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 ==
{{zobacz też|kongruencja (algebra)}}
Jeżeli <math>w(x)</math> jest wielomianem całkowitym względem <math>x</math> o współczynnikach całkowitych, to kongruencja <math>a\equiv b \pmod m</math> pociąga za sobą <math>w(a)\equiv w(b) \pmod m.</math>
 
Niech <math>A_0 x^n + A_1 x^{n-1} + A_2 x^{n-2} + \ldots + A_{n-1} x + A_n</math> będzie [[wielomian]]em całkowitym <math>n</math>-tego stopnia o współczynnikach całkowitych (wielomian ten oznaczamy krótko przez <math>w(x)</math>), <math>m</math> będzie danym modułem, zaś <math>a</math> i <math>b</math> liczbami całkowitymi przystającymi według modułu <math>m.</math>
Zapiszemy ciąg kongruencji następująco:
: <math>A_0 a^n \equiv A_0 b^n \pmod m,</math>
: <math>A_1 a^{n-1}\equiv A_1 b^{n-1}\pmod m,</math>
: <math>A_{n-1} a \equiv A_{n-1} b \pmod m,</math>
: <math>A_n\equiv A_n \pmod m.</math>
 
Dodajemy stronami,
: <math>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,</math> czyli
: <math>w(a)\equiv w(b) \pmod m.</math>
 
Niech <math>N \in \mathbb N,</math> a <math>C_1, C_2, C_3,\dots, C_n\quad{}</math> jej kolejnymi cyframi w układzie dziesiętnym.
: <math>N = C_1 10^{n-1} + C_2 10^{n-2} + \ldots + C_{n-1}10 + C_n.</math>
 
Niech
* <math>w (x)= C_1 x^{n-1} + C_2 x^{n-2} + \ldots + C_{n-1} x + C_n</math>
 
i
* <math>w(10)=N.</math>
 
=== Podzielność przez 9 ===
Z lematu i wobec kongruencji <math>10\equiv1 \pmod 9\quad{}</math> mamy
: <math>w(1)= C_1 + C_2 + \ldots + C_{n-1} + C_n,</math>
 
zatem
: <math>N\equiv C_1 + C_2 + C_3 + \ldots + C_{n-1} + C_n \pmod 9,</math>
 
co dowodzi, że każda liczba naturalna przystaje według modułu <math>9</math> do sumy swoich cyfr. Dla podzielności liczby <math>N</math> przez <math>9</math> wystarcza, by suma jej cyfr była podzielna przez <math>9.</math>
 
=== Podzielność przez 11 ===
Wobec lematu oraz kongruencji <math>10\equiv -1 \pmod {11},</math> mamy
: <math>w(10)\equiv w(-1) \pmod {11},</math>
 
czyli
: <math>N \equiv C_1 - C_2 + C_3 - C_4 + \dots \pmod {11}.</math>
 
Co oznacza podzielność przez <math>11{:}</math> 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ż ==
* [[dzielnik]]
 
== Bibliografia ==
* [http://mathforum.org/dr.math/faq/faq.divisibleto50.html Witryna Math Forum @Drexel] {{lang|en}}
* {{cytuj stronę| url =http://www.math.us.edu.pl/~pgladki/faq/node54.html |tytuł =Cechy podzielności |data dostępu = 28 września 2008}}
 
[[Kategoria:Teoria liczb]]
[[Kategoria:Arytmetyka]]
Anonimowy użytkownik
Źródło: „https://pl.wikipedia.org/wiki/Specjalna:Różnica_mobilna/63203297”