Kiedyś pokazałem, że resztę z dzielenia można przetrzymywać nie na cyfrze najmniej znaczącej, lecz na najbardziej znaczącej podczas przekształceń liczby.
Kolejne przekształcenie też znajduje dzielnik, w nim niezmiennikiem jest wartość
n = a*b + reszta
w którym a zwiększamy stale o 1, zaś b maleje, co wynika z odpowiedniego rozszerzenia wzoru
(a+1)*(b-1) = a*b + b-(a+1)
brane modulo (a+1), gdy a*b jest znane. Wartość b maleje o około b/a z dokładnością do plus minus jeden oraz tłumi się geometrycznie. Reszta się stale dopasowywuje -1< reszta < a.
Zatem można bezpośrednio przechodzić z a*b na wartość (a+1)*b' + reszta' też równe n, korzystając początkowo z dzielenia, potem to dzielenie degraduje się do odejmowania/dodawania odpowiedniej wielokrotności a+1.
Czy można to zastosować do systemów niedziesiątkowych, szybko znajdując resztę (cecha podzielności przez odpowiednik 11)? Parę przykładów i odpowiedź: NIE.
Chodzi o to, że jeśli n nie jest wielokrotnością podstawy, to nie istnieją rozwiązania odpowiednich kongruencji, by dopasować cyfrę najmniej znaczącą. A dlaczego wspomniany na początku sposób zadziałał?
Odpowiedź: wybrane n było nieparzyste, które zawsze modulo 2 daje resztę 1, co wystarczyło. Uzyskujemy postać binarną jednego z dzielników, który na najmniej znaczącej pozycji ma 1. I to było przyczyną powodzenia.
