Ułamki egipskie oraz algorytm faktoryzacji zwrócily moja uwagę na systemy niedziesiątkowe. Na razie system binarny oraz systemy o podstawie będące potęgą 2.
Występują bardzo proste cechy podzielności dla liczb będących postaci 2^n +- 1.
Dzieląc liczbę w systemie o podstawie 2^n na paczki binarne długości n-1 znaków, liczba jest podzielna przez 2^n-1 gdy suma wartości poszczególnych paczek binarnych też jest podzielna. (por. cecha podzielności przez 9).
Dla liczb postaci 2^n+1 reszta jest równa reszcie sumy naprzemiennej tych paczek (por. cecha podzielności przez 11.
Do odpowiednich liczb należą 3, 5, 7, 9, 15, 17, 31, 33 i wiele innych.
Wystarczy przekształcić liczbę do postaci np. oktagonalnej by już mieć postać równoważną binarnej i zastosować cechę.
Przykład: sprawdzimy resztę z dzielenia 3523432 przez 17 równe 10001 binarnie.
Przekształcamy 3523432 do systemu ósemkowego, dodając do każdej cyfry z wyjątkiem pierwszej przed '|' podwojoną wcześniejszą i 'naprawiając cyfry' przez przenoszenie nadmiarów 8:
3 5 | 2 3 4 3 2
4 3 2 | 3 4 3 2
5 4 0 3 | 4 3 2
6 7 0 3 4 | 3 2
1 0 4 6 4 2 3 | 2
1 2 6 0 1 2 7 2 |
1 5 3 4 1 5 5 0
Zatem w ósemkowym liczba wyglada 15341550 = binarnie 001 101 011 100 001 101 101 000 = 0011 0101 1100 0011 011 01000 = heksadecymalnie 3 5 12 3 6 8.
Według cechy podzielności, naprzemienna suma -3+5-12+3-6+8 = -5 = 12 (17) ma taką samą resztę. Istotne są tu znaki, ale rzeczywiście, wartość ta w dziesiatkowym przedstawi się jako 207260*17+12.
Algorytm dotyczący sposobu przechodzenia między systemami jest opublikowany w następnym poście.
