26 lutego 2015

Cechy podzielności w systemach niedziesiątkowych

Znane są cechy podzielności przez 2, 3, 4, 5, 9, 10, 11 w systemie dziesiątkowym.

Okazuje się, że w systemie o podstawie n cechy podzielności są równie łatwe do wyprowadzenia.
W szczególności, traktując kolejne cyfry liczby w systemie o podstawie n jako współczynniki wielomianu, znajdujemy resztę z dzielenia przez n-x obliczając wartość tego wielomianu dla x modulo (n-x).
Wynika to z tych sposobów mnożenia i dzielenia, w których dowodach korzystamy z konwersji na inny system.   
Sposoby te są przenośne na wszystkie systemy, w których rozpisaniu kolejne cyfry są przy potęgach liczby naturalnej większej od 1.

Przykładowo mając liczbę w systemie o podstawie 20, np 13 7 2 8 10, daje ona w wyniku dzielenia przez 19 resztę 2, bo cecha podzielności to wartość wielomianu w 1:
13+7+2+8+10 = 22_{19} (dziesiętnie 40) = 2 (mod 19)