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

Usunięte 168 bajtów ,  3 lata temu
m
drobne redakcyjne
(Anulowanie wersji 54613997 autora 83.27.138.24 (dyskusja), zobacz lemat)
Znacznik: Anulowanie edycji
m (drobne redakcyjne)
 
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.
 
'''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>.
 
{| border=1
! dzielnik pierwszy <math>p\;</math>
! czynnik <math>m\;</math>
! czynnik <math>p-m\;</math>
! zalecany algorytm
|-
 
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.
 
 
== 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}A_0 x^{n} + A_{1}A_1 x^{n-1} + A_{2}A_2 x^{n-2} + \ldots + A_{n-1} x + A_{n}\quadA_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_0 a^{n} \equiv A_{0}A_0 b^{n} \pmod m,</math>,
: <math>A_{1}A_1 a^{n-1}\equiv A_{1}A_1 b^{n-1}\pmod m,</math>,
: <math>A_{n-1} a \equiv A_{n-1} b \pmod m,</math>,
: <math>A_{n}A_n\equiv A_n \pmod m.</math>.
 
Dodajemy stronami,
: <math>A_{0}A_0 a^{n} + A_{1}A_1 a^{n-1} + \dots + A_{n-1} a + A_{n}A_n \equiv A_{0}A_0 b^{n} + A_{1}A_1 b^{n-1} + \dots + A_{n-1} b + A_{n}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}C_1 10^{n-1} + C_{2}C_2 10^{n-2} + \ldots + C_{n-1}10 +C_{n}\quad C_n.</math>.
 
Niech
* <math>\quad w (x)= C_{1}C_1 x^{n-1} + C_{2}C_2 x^{n-2} + \ldots + C_{n-1} x + C_n\quad</math>
 
i
* <math>\quad w(10)=N.\quad</math>.
 
=== Podzielność przez 9 ===
Z lematu i wobec kongruencji <math>10\equiv1 \pmod 9\quad</math> mamy
: <math>\quad w(1)= C_1 + C_2 + \ldots + C_{n-1} + C_n\quad,</math>, zatem
 
zatem
: <math>\quad w(1)= C_1 + C_2 + \ldots + C_{n-1} + C_n\quad</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>.
 
: <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.
 
== 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]]