Mnożenie bez przeniesień jest specyficznym zapisem liczb, w którym na miejscu cyfr mamy liczby. Mnożenie tak wykonywane nie ma ostatniej czynności, w której sumuje się iloczyny cząstkowe, przenosząc nadmiary. Przypominam sposób mnożenia, np. 15*15:
[1 5] * [1 5] = [1 5+5 25] = [1 10 25]
Po wykonaniu przeniesień: 15*15= [1+1 0+2 5] = 225.
Niech s będzie podłogą z pierwiastka kwadratowego liczby N, oraz s nie dzieli N. Wtedy w systemie liczbowym o podstawie s liczba N ma postać:
[1 y r],
gdzie -1<y<2, 0<r<s.
Usuńmy przeniesienie cyfry setek uzyskując:
[1 y r] = [0 s+y r] .
Jest to równocześnie iloczyn [a b]*[0 d] = [ad bd].
Oznacza to, że dla liczby zlożonej N istnieje takie k, że największy wspólny dzielnik
gcd(s+y-k, r+sk) > 1
jest dodatni, a nawet bywa dzielnikiem.
Zmieniając k o pozycję, nasunęły mi się przedstawienia iloczynów ks jako cyfr jedności w systemie o podstawie (s-k).
I to rzeczywiście działa. Dla N=8934053 mamy postać [2989 2921], zaś szukając k rozwiazujemy kongruencje:
2921 + 2988k > 0 (mod 2989-k) .
Przyrost przy zmianie k o 1 ma drugą róznicę stałą, A do rozkładu interesuje nas tylko największy wspólny dzielnik reszty i podstawy systemu. Dla dużych wartości są one bliskie sobie.
Dodatkowo, k nie musi być dodatnie, może też być ujemne. W podanym przykładzie uzyskałem
k=-272 oraz gcd(2989+272, 2921-k*2988) \equiv gcd(3261, 1087) = 1087.
Ciąg reszt z r+ks (mod s-k): 67, 64, 59, 52, 43, 32, 19, 4, 2985, 2967, ...
Z drugiej strony
k=815 oraz gcd(2989-815, 2921+k*815) \equiv gcd(2174, 1087)=1087 . Ciąg reszt 2923, 2927, ...
