4 ms·
Wait: Can you always test for divisibility by $n$ in base $n+1$ like that?
by petschge 5y ago
Wait: Can you always test for divisibility by $n$ in base $n+1$ like that?
- J-Kuhn 5y agoYes. 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$
- klyrs 5y agoThe trick for 11 generalizes for testing for divisibility by n+1 in base n, too
- ouid 5y agoyes, n^k-1 is always divisible by n-1.