Rules of thumb for divisibility

Given a number presented in decimal form $n=\sum_{k=0} d_k10^k$ there are some nice thumb rules to decide whether it is divisible with a prime number $p\in\{7,11,13,17,19,23,29\}$.

For each of this numbers there is a number $a_p$ such that $p|n\iff p|(a_p\cdot d_0+\sum_{k=0} d_{k+1}10^k)$.

$a_7=-2,\;a_{11}=-1,\;a_{13}=4,\;a_{17}=-5,\;a_{19}=2,\;a_{23}=7,\;a_{29}=3$

E.g. $\;19\cdot 17=323$ and $32+2\cdot 3=38=2\cdot 19$ and $32-5\cdot 3=17$.

Is there a number $a_{31}$ that works the same way? Or $a_p,\;p\ge37$?

Solution 1:

Yes, there is. For all primes $p$ other than $2$ and $5$ the rule $a_p=1/10$ works. The arithmetic is to be done in $\Bbb{Z}_p$ (or, modulo $p$):

• With $p=7$ we have $10=3$, so $a_7=1/10=1/3=-2$.
• With $p=11$ we have $10=-1$, so $a_{11}=1/(-1)=-1$.
• With $p=31$ we have $10\cdot(-3)=-30=1$, so $a_{31}=1/10=-3$.

The reason is that when $10a_p\equiv1\pmod p$ we have $$ n=\sum_{k\ge0}d_k10^k\equiv 10\left(d_0a_p+\sum_{k>0} d_k10^{k-1}\right)\pmod p. $$ Therefore $n$ is divisible by $p$ if and only if $10(d_0a_p+\sum_{k>0}d_k10^{k-1})$ is. Because $\gcd(10,p)=1$ cancelling that factor $10$ won't change divisibility by $p$, and we get that $n$ is divisible by $p$ if and only if the number $$ a_pd_0+\sum_{k>0}d_k10^{k-1}=a_pd_0+\lfloor\frac n{10}\rfloor $$ is divisible by $p$.