TWORZENIE CECH PODZIELNOŚCI DLA DOWOLNEGO N
Żeby umieć to zrobić należy znać:
a) podstawy zapisu w systemie liczbowym
b) kongruencje (niech nazwa licealistów nie odstraszy - to rzecz naprawdę prosta)
Podstawy zapisu w systemie liczbowym
Liczbę \(\displaystyle{ 6458}\) w systemie dziesiątkowym zapisujemy jako:\(\displaystyle{ 6 458=6\cdot 10^3+4\cdot 10^2+5\cdot 10^1+8\cdot 10^0}\)
Zapisując to znaczkami dowolną liczbę k-cyfrową można zapisać jako:
\(\displaystyle{ a=a_k\cdot 10^k+a{k-1}\cdot 10^{k-1}+... +a_1\cdot 10^1+a_0\cdot 10^0}\)
gdzie \(\displaystyle{ a_0}\) to liczba jedności, \(\displaystyle{ a_1}\) dziesiątek itd.
Kongruencja
Kongruencja to taka relacja która dzieli zbiór na klasy abstrakcji o tej samej reszcie przy dzieleniu przez jakąś liczbę. A teraz po ludzku Wybieramy sobie jakąś liczbę przez którą będziemy dzielić (np 7) - to będzie to tajemnicze "modulo"...
...a teraz wprowadźmy sobie nowy znaczek \(\displaystyle{ \equiv}\) który będzie oznaczał że dwie liczby przy dzieleniu przez 7 dają tą samą liczbę, czyli np:
\(\displaystyle{ 3 \equiv 10 (mod 7)}\)
...co oznacza tyle ze 3 i 10 dają tę samą resztę przy dzieleniu przez siedem (konkretnie resztę 3).
W kongruencjach możemy podmieniać liczby ktore dają tę samą resztę
Możemy odejmować do woli od którejkolwiek ze stron (taktak można też tylko od jednej) dowolną ilość razy naszą liczbę "modulo"
CECHA PODZIELNOŚCI PRZEZ DOWOLNĄ LICZBĘ
Co to znaczy że liczba jest podzielna przez inną? Tzn. że daje resztę 0, czyli przystaje do 0 modulo n.Zróbmy to na przykładzie podzielności przez 11:
\(\displaystyle{ a_k\cdot 10^k+a{k-1}\cdot 10^{k-1}+... +a_1\cdot 10^1+a_0\cdot 10^0 \equiv 0 (mod 11)}\)
Nasz cel: pozbyć się dziesiątek
Zauważmy że:
\(\displaystyle{ 10 \equiv -1 (mod 11)}\)
\(\displaystyle{ 10^2 \equiv 1 (mod 11)}\)
\(\displaystyle{ 10^3 \equiv -1 (mod 11)}\)
\(\displaystyle{ 10^4 \equiv 1 (mod 11)}\)
...czyli każdą nieparzystą potęge 10-tki możemy "wymienić" za -1 a parzystą za 1
Otrzymujemy ultra-odstraszającą kongruencje
\(\displaystyle{ a_k\cdot(-1)^k+...-a_3+a_2-a_1+a_0 \equiv 0 (mod 11)}\)
Stąd wynika nasza cecha podzielności przez 11: liczba jest podzielna przez 11 jezeli różnica liczb będących sumą cyfr na miejscach parzystych i nieparzystych dzieli się przez 11
Przykład: 723456789
7+3+5+7+9=31
2+4+6+8=20
31-20=11 a 11 dzieli sie przez 11
Czyli liczba 723456789 jest podzielna przez 11
istotnie 723456789:11=65768799.