Cechy podzielności

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Kanodelo
Użytkownik
Użytkownik
Posty: 1267
Rejestracja: 1 kwie 2011, o 11:37
Płeć: Mężczyzna
Lokalizacja: Malbork
Podziękował: 419 razy
Pomógł: 114 razy

Cechy podzielności

Post autor: Kanodelo »

A jest może jakaś metoda na wyznaczanie cechy podzielności np. przez 7, albo przez jakąś inna prostą liczbę... Tak żeby było przy użyciu konkurencji. Jak ktoś pokaże taką najprostszą metodę to może uda mi się wyprowdazić jakąś trudniejszą.
Awatar użytkownika
Vax
Użytkownik
Użytkownik
Posty: 2913
Rejestracja: 27 kwie 2010, o 22:07
Płeć: Mężczyzna
Lokalizacja: Biała Podlaska / Warszawa
Podziękował: 4 razy
Pomógł: 612 razy

Cechy podzielności

Post autor: Vax »

Jeżeli chcesz znaleźć cechę podzielności np przez 9, to zauważ, że każdą liczbę całkowitą N można zapisać w postaci:

\(\displaystyle{ N = \overline{a_1a_2a_3...a_n} = \sum_{i=1}^{n} a_i\cdot 10^{n-i}}\)

Teraz zdefiniujmy sobie:

\(\displaystyle{ f(x) = \sum_{i=1}^{n}a_i \cdot x^{n-i}}\)

Zauważ, że każdą liczbą całkowitą można przedstawić jako \(\displaystyle{ f(10)}\) dla pewnych całkowitych \(\displaystyle{ a_i}\), skoro współczynniki \(\displaystyle{ a_i}\) są całkowite, to:

\(\displaystyle{ a \equiv b (mod \ c) \Rightarrow f(a) \equiv f(b) (mod \ c)}\)

Zauważ, że:

\(\displaystyle{ 10 \equiv 1 (mod \ 9) \Rightarrow f(10) \equiv f(1) = \sum_{i=1}^{n} a_i (mod \ 9)}\)

Z tego wynika, że jeżeli liczba N dzieli się przez 9, suma jej cyfr dzieli się przez 9, analogicznie możesz znaleźć cechę podzielności przez 3. Teraz zajmijmy się cechą podzielności przez 7, to jest trochę bardziej skomplikowane, zauważ, że każdą liczbę można przedstawić w postaci:

\(\displaystyle{ N = \overline{a_1a_2...a_n} = ... + 1000^2\overline{a_{n-8}a_{n-7}a_{n-6}}+1000\overline{a_{n-5}a_{n-4}a_{n-3}}+\overline{a_{n-2}a_{n-1}a_n}}\)

Definiujemy teraz \(\displaystyle{ h(x) = ... + x\cdot \overline{a_{n-5}a_{n-4}a_{n-3}}+\overline{a_{n-2}a_{n-1}a_n}}\)

Oczywiście każdą liczbę całkowitą N można przedstawić jako \(\displaystyle{ h(1000)}\), zauważ, że:

\(\displaystyle{ 1000 \equiv (-1) (mod \ 7) \Rightarrow h(1000) \equiv h(-1) = ...+(-1)\overline{a_{n-5}a_{n-4}a_{n-3}}+\overline{a_{n-2}a_{n-1}a_n} (mod \ 7)}\)

Czyli liczba całkowita jest podzielna przez 7, wtedy i tylko wtedy, gdy po ,,podzieleniu" tej liczby od końca na trójki, na zmianę dodając i odejmując te liczby otrzymamy liczbę podzielną przez 7, przykładowo 1879048192 dzieli się przez 7, ponieważ:

\(\displaystyle{ 7 | -1+879-048+192 = 1022 = 7\cdot 146}\)

Można zauważyć, że zachodzi również \(\displaystyle{ 1000 \equiv (-1) (mod \ 13)}\) więc identyczna jest cecha podzielności przez 13

Pozdrawiam.
ODPOWIEDZ