Re:Divisible by 7 (2016)
by quercusa on Thursday May 20, 2021 @03:03PM
(#27225612)
Convert a base-10 number to octal. If the octal digits are divisible by 7, it's divisible by 7. IOW, 7 is octal's 9.
[ Parent
| on HN ]
Wait: Can you always test for divisibility by $n$ in base $n+1$ like that?
Yes.
A number in base $n$ is just $a*n^2+b*n^1+c$.
Because $n mod n-1 = 1$, you can replace every $n$ with $1$.
So $a*n^2+b*n^1+c mod n-1$ becomes $a+b+c mod n-1$
The trick for 11 generalizes for testing for divisibility by n+1 in base n, too