Cechy podzielności
-
- 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
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ą.
- Vax
- 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
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.
\(\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.