One stackoverflow question asks how to check divisibility of a natural number $n$ by 3 with a processor using binary arithmetic mod $2^8$, no divide/modulus instruction (some models not supporting multiplication).
(More fluent with the two's complement, shift&mask notation, below $D\div
d$ is $\lfloor D/d\rfloor$.)
Revisiting computation of a number $s<2^4, s \equiv n \mod (2^4-1)$, it occurred to me that computing $h = n\div 2^4, l = n\mod 2^4, S' = ((h+l)*2^4+(l+h)\mod2^8$, $S'\div 2^4$ already is one such $s$.
I tinkered around wanting to repeat that trick, and found (by exhaustive test) that not just
$(S' + S'\div 2^2)\div2^4\mod 4\equiv n \mod 3$, but
$5S'\div2^6\mod 4$, too (more convenient later on).
Why does $S'\mod 2^4$ not interfere?
How to understand/argue/prove this?
I spent hours to no avail.