Interesting. I will make a few observations and offer a recoding.
(1) Working in base 10 is computationally inefficient. If the digit length is n, then the algorithmic complexity of IntegerDigits/FromDigits becomes n log(n) whereas is is just n in base power-of-2 (because the underlying storage is base 2).
(2) Another advantage to working in a power-of-2 base is that now the prime 5 is not disallowed. Also there is no restriction to primes, the only restriction is that the putative divisor not be even.
(3) It is not necessary to convert to/from a digit string in the main loop. One can let the hex (or base 10) digits become negative. The issue we want to avoid from these conversions is that each iteration then has more work to do.
Here is my recoding using hex.
divisibleQ2[s_, primo_] :=
Module[{factor = ModularInverse[-16, primo], numero = s, digits, plen, diff},
digits = IntegerDigits[numero, 16];
plen = Length[IntegerDigits[primo, 16] + 1];
While[
Length[digits] > plen + 1,
diff = IntegerDigits[factor*Last[digits], 16, Length[digits] - 1];
digits = Most[digits] - Sign[Last[digits]]*diff;
];
numero = FromDigits[digits, 16];
If[numero < 0, While[numero < 0, numero = numero + primo],
While[numero > 0, numero = numero - primo]];
If[numero == 0, True, False]]
I have not thoroughly tested it but I believe it works correctly. Or at least could be made to.
The down side: it is still algorithmically O(n^2) because it needs O(n) iterations and each operates on lists of length O(n). So it does not beat "schoolkid" (used to be "schoolboy") division by more than a constant factor. Still, it's interesting.
