Wróć do informacji o e-podręczniku Wydrukuj Pobierz materiał do PDF Pobierz materiał do EPUB Pobierz materiał do MOBI Zaloguj się, aby dodać do ulubionych Zaloguj się, aby skopiować i edytować materiał Zaloguj się, aby udostępnić materiał Zaloguj się, aby dodać całą stronę do teczki

W poniższych przykładach prezentowane są pomysły na dowodzenie podzielności liczb całkowitych za pomocą własności współczyników dwumianowychwspółczynnik dwumianowywspółczyników dwumianowych, jak również z użyciem wzoru dwumianowegowzór dwumianowywzoru dwumianowego.

Istotną część przedstawionych poniżej wniosków można zapisać używając do tego celu kongruencji liczbowych, jednak – z zasady – nie będziemy tego sposobu stosowali.

Chętnym do utrwalenia swoich umiejętności z podstaw arytmetyki modularnej polecamy zredagowanie poniższych rozwiązań metodą kongruencji, co byłoby – jak uważamy – pouczającym ćwiczeniem.

Przykład 1

Obliczymy:
a) dwie ostatnie cyfry zapisu dziesiętnego liczby 75236,
b) resztę z dzielenia przez 1000 liczby 71122.

Rozwiązanie

a) Korzystając ze wzoru dwumianowegowzór dwumianowywzoru dwumianowego zapisujemy
75236=750+236=75036+361·75035·2++3635·750·235+236.
Zauważmy, że ponieważ 7502=752·102=100·752 oraz 2·750=1500=100·75, więc każdy spośród 36 początkowych wyrazów powyższego rozwinięcia dzieli się przez 100. Wobec tego 75236=100n+236, dla pewnej liczby naturalnej n.
Zauważmy następnie, że
236=2123=40963=4100-43=41003-3·41002·4+3·4100·42-43=
=41003-3·41002·4+3·4100·42-100+36.
Ponieważ każdy z czterech wyrazów w nawiasie dzieli się przez 100, więc liczba 236 przy dzieleniu przez 100 daje resztę 36.
Wynika stąd, że dwie ostatnie cyfry zapisu dziesiętnego liczby 75236 to 3 (cyfra dziesiątek) oraz 6 (cyfra jedności).

b) Zauważamy, że 71122=72561=49561.
Następnie, korzystając ze wzoru dwumianowegowzór dwumianowywzoru dwumianowego zapisujemy
50-1561=50561+5611·50560·-1++561558·503·-1558+
+561559·502·-1559+561560·50·-1560+-1561.
Zauważmy, że ponieważ 503=53·103=1000·53 oraz 561559·502=561·5602·2500=1000·561·280·25, więc każdy spośród 560 początkowych wyrazów powyższego rozwinięcia dzieli się przez 1000. Wobec tego 71122=1000n+561560·50·-1560+-1561, dla pewnej liczby naturalnej n.
Obliczamy, że 561560·50·-1560+-1561=561·50-1=28049=28·1000+49, skąd wynika, że szukana reszta z dzielenia przez 1000 jest równa 49.

Przykład 2

Wykażemy, że liczba 5121212-2151515 dzieli się przez 7.

Rozwiązanie

Dla dowodu wystarczy pokazać, że liczby 5121212 oraz 2151515 dają tę samą resztę z dzielenia przez 7.

Zauważmy, że:

  1. 2151515=2350505=7+150505.
    Korzystając ze wzoru dwumianowegowzór dwumianowywzoru dwumianowego możemy zatem zapisać, że
    7+150505=750505+505051·750504++5050550504·7+1=
    =7·750504+505051·750503++5050550504+1,
    skąd wynika, że liczba 2151515 przy dzieleniu przez 7 daje resztę 1.

  1. 5121212=7+-2121212.
    Korzystając ze wzoru dwumianowegowzór dwumianowywzoru dwumianowego możemy zatem zapisać, że
    7+-2121212=7121212+1212121·7121211·-21++
    +121212121211·7·-2121211+-2121212=
    =7·(7121211+1212121·7121210·-21++
    +121212121211·-2121211)+2121212,
    skąd wynika, że liczba 5 121212 przy dzieleniu przez 7 daje taką samą resztę, jak liczba 2121212.
    Ponieważ 2121212=2340404=7+140404, więc (rozumując podobnie, jak w przypadku liczby 7+150505) otrzymujemy, że resztą z dzielenia tej liczby przez 7 jest 1, zatem również liczba 5121212 przy dzieleniu przez 7 daje resztę 1.

Oznacza to, że liczba 5121212-2151515 dzieli się przez 7.

Można też zauważyć, że 56=15625=7·2232+1, skąd 5121212=5620202=7·2232+120202.
Rozwinięcie otrzymanej sumy za pomocą wzoru dwumianowego i wykazanie, że liczba 5121212 przy dzieleniu przez 7 daje resztę 1 pozostawiamy jako nietrudne ćwiczenie.

Uwaga.
Można wykazać, że dla każdej dodatniej liczby całkowitej n liczba 512n-215n jest podzielna przez 7.
Wystarczy w tym celu następująco przekształcić tę różnicę 512n-215n=562n-235n=7·2232+12n-7+15n
i wykorzystać pomysły omówione w powyższym przykładzie.

Przykład 3

Wykażemy, że współczynik dwumianowywspółczynnik dwumianowywspółczynik dwumianowy n=16831410 to liczba, która:
a) dzieli się przez 5, ale nie dzieli się przez 25,
b) dzieli się przez 9, ale nie dzieli się przez 27.

Rozwiązanie

Zauważmy, że 16831410=1683!1410!·273!, zatem będziemy obliczali wykładnik, z jakim liczba ustalona w każdym z podpunktów wchodzi do rozkładu każdej z liczb: 1683!, 1410! oraz 273!.

Do tego celu wykorzystamy funkcję podłoga, która zaokrągla w dół liczby rzeczywiste do liczb całkowitych (fx=x)

a) Ponieważ:

  • 54=625<1683<55=3125, więc liczba 5 w rozkładzie liczby 1683! pokazuje się z wykładnikiem równym
    168351+168352+168353+168354=336+67+13+2=418,

  • 54=625<1410<55=3125, więc liczba 5 w rozkładzie liczby 1410! pokazuje się z wykładnikiem równym
    141051+141052+141053+141054=282+56+11+2=351,

  • 53=125<273<54=625, więc liczba 5 w rozkładzie liczby 273! pokazuje się z wykładnikiem równym
    27351+27352+27353=54+10+2=66.

Oznacza to, że liczba 5 w rozkładzie liczby 16831410=1683!1410!·273! występuje z wykładnikiem równym 418-351+66=1.

Zatem liczba n dzieli się przez 5, ale nie dzieli się przez 25.

b) Ponieważ:

  • 36=729<1683<37=2187, więc liczba 3 w rozkładzie liczby 1683! pokazuje się z wykładnikiem równym
    168331+168332+168333+168334+168335+168336=
    = 561+187+62+20+6+2=838,

  • 36=729<1410<37=2187, więc 3, więc liczba 3 w rozkładzie liczby 1410! występuje z wykładnikiem równym
    141031+141032+141033+141034+141035+141036=
    =470+156+52+17+5+1=701,

  • 35=243<273<36=729, więc liczba 3 w rozkładzie liczby 273! występuje z wykładnikiem równym
    27331+27332+27333+27334+27335=
    =91+30+10+3+1=135.

Oznacza to, że liczba 3 w rozkładzie liczby 16831410=1683!1410!·273! pokazuje się z wykładnikiem równym 838-701+135=2.

Zatem liczba n dzieli się przez 9, ale nie dzieli się przez 27.

Przykład 4

Wykażemy, że dla każdej dodatniej liczby całkowitej n liczba 106n-3+1 dzieli się przez każdą z liczb: 7, 11, 13.

Rozwiązanie

I sposób:

Zauważmy, że 7·11·13=1001 oraz 106n-3=1032n-1=1001+-12n-1.

Korzystając ze wzoru dwumianowegowzór dwumianowywzoru dwumianowego otrzymujemy:

1001+-12n-1=10012n-1+2n-11·10012n-2·-1+
+2n-12·10012n-3·-12++
+2n-12n·1001·-12n-2+-12n-1

Zatem w rozwinięciu tej sumy każdy spośród 2n-2 początkowych składników jest podzielny przez 1001, natomiast ostatni wyraz, -12n-1 (jedyny niepodzielny przez 1001), dla dowolnej liczby całkowitej n ma wartość -1.

Oznacza to, że liczba 1001+-12n-1+1 dzieli się przez 1001=7·11·13. To spostrzeżenie kończy dowód.

II sposób:

Rozpatrzmy wielomian Wx=x2n-1+1, gdzie n jest dodatnią liczba całkowitą.
Ponieważ W-1=-12n-1+1=-1+1=0, więc wielomian W dzieli się przez x+1.
Przyjmując x=103 otrzymujemy, że liczba W103=1032n-1+1 dzieli się przez 103+1=1001=7·11·13, co oznacza, że dla każdej dodatniej liczby całkowitej n liczba ( 10 3 ) 2 n 1 + 1 dzieli się przez każdą z liczb 7, 11, 13. W ten sposób dowód został zakończony.

Przykład 5

a) Wykażemy, że dla każdej liczby całkowitej n liczba n·n+1·n+2 dzieli się przez 6.

Rozwiązanie

Załóżmy, że liczba n jest dodatnia.
Ponieważ dla dowolnej dodatniej liczby całkowitej n liczba n+23 określa liczbę trzyelementowych podzbiorów zbioru n+2–elementowego, więc jest to liczba całkowita. Wynika stąd, że liczba 6·n+23 jest podzielna przez 6.
Zatem podzielna przez 6 jest liczba
6·n+23=6n+2!3!·n-1!=6n-1!·nn+1n+26n-1!=nn+1n+2,
co dowodzi tezy w przypadku, gdy n jest liczbą dodatnią.

Jeżeli iloczyn nn+1n+2 jest równy zero (co zachodzi dla n=0 lub n=-1 lub n=-2), to jest, oczywiście, liczbą podzielną przez 6.

Pozostaje więc rozpatrzyć przypadek, gdy liczba nn+1n+2 jest ujemna.
Zauważmy, że wtedy każdy z jej czynników jest ujemny. Rozpatrzmy więc dodatnią liczbę t=-n-2. Wówczas liczba t·t+1·t+2 jest podzielna przez 6 (co stwierdzamy na podstawie wniosku sformułowanego powyżej), a więc przez 6 dzieli się również liczba do niej przeciwna, czyli liczba
-tt+1t+2=--n-2-n-1-n=n+2n+1n.

Oznacza to, że dla każdej liczby całkowitej n liczba nn+1n+2 dzieli się przez 6.

Uwaga. Z powyższego spostrzeżenia wynika np., że:

  • dla każdej liczby całkowitej n liczba n3-n=nn2-1=n-1nn+1 dzieli się przez 6,

  • dla każdej liczby całkowitej n i każdej liczby całkowitej k liczba kn3-nk3=kn3-kn+kn-nk3=kn3-n-nk3-k jest podzielna przez 6.

b) Wykażemy, że dla każdej liczby całkowitej n liczba n5-n dzieli się przez 30.

Rozwiązanie

Zauważmy, że
n5-n=nn4-1=nn2-1n2+1=n-1nn+1n2+1=
=n-1nn+1n2-4+5=n-2n-1nn+1n+2+
+5n-1nn+1.

Ponieważ:

  • n-2n-1nn+1n+2=30·n-2n-1nn+1n+25!=
    =30·n+25, więc rozumując podobnie jak w poprzednim podpunkcie stwierdzamy, że dla dowolnej liczby całkowitej n liczba n-2n-1nn+1n+2 dzieli się przez 30,

  • dla dowolnej liczby całkowitej n liczba n-1nn+1 dzieli się przez 6, co oznacza, że liczba 5·n-1nn+1 dzieli się przez 30.

Wobec tego suma n-2n-1nn+1n+2+5n-1nn+1 również dzieli się przez 30, a to właśnie należało udowodnić.

Uwaga. Z powyższego spostrzeżenia wynika np., że dla każdej liczby całkowitej n i każdej liczby całkowitej k liczba kn5-nk5=kn5-kn+kn-nk5=kn5-n-nk5-k jest podzielna przez 30.

Słownik

współczynnik dwumianowy
współczynnik dwumianowy

w rozwinięciu dwumianu współczynnik liczbowy zapisany przy wyrazie tego rozwinięcia; w szczególności k–tym współczynnikiem dwumianowym w rozwinięciu a+bn jest liczba:

nk
wzór dwumianowy
wzór dwumianowy

dla dowolnych liczb a, b oraz dowolnej dodatniej liczby całkowitej n prawdziwy jest wzór:

a+bn=n0an+n1an-1·b+n2an-2·b2+
++nkan-k·bk++nnbn