Determine the divisibility of a given number without performing full division

My question is slightly more complicated than what's implied on the title, so I will start with an example. Given any number $N$ on base $10$, we can easily determine whether or not $N$ is divisible by any $d\in[2,9]$, except for $d=7$:

• $N$ is divisible by $2$ if $N\bmod10$ is divisible by $2$


• $N$ is divisible by $3$ if $N$'s digit-sum is divisible by $3$


• $N$ is divisible by $4$ if $N\bmod100$ is divisible by $4$


• $N$ is divisible by $5$ if $N\bmod10$ is divisible by $5$


• $N$ is divisible by $6$ if $N$ is divisible by $2$ and $3$


• $N$ is divisible by $8$ if $N\bmod1000$ is divisible by $8$


• $N$ is divisible by $9$ if $N$'s digit-sum is $9$

In the case of $d=7$, we pretty much have to perform a full division (at least for some values of $N$).

I believe that the general rule for base $B$ and $d\in[2,B-1]$ is the following:

[We can easily determine $d|N_B]\iff[\gcd(B,d)>1]\vee[gcd(B-1,d)>1]$

Is there an easy way to prove or refute this?

---

Partial answers will also be appreciated:

• [We can easily determine $d|N_B]\impliedby[\gcd(B,d)>1]$


• [We can easily determine $d|N_B]\impliedby[[gcd(B-1,d)>1]$


• [We can easily determine $d|N_B]\implies[\gcd(B,d)>1]\vee[gcd(B-1,d)>1]$

The $1^{st}$ one is pretty trivial, I believe that the $2^{nd}$ one also holds, but I'm not sure about the $3^{rd}$ one.

Answer

Just to summarise some of the material in the comments and expand it slightly.

There is a well-known test for 7. $a_k\dots a_1a_0$ is divisible by 7 iff $(a_2a_1a_0)-(a_5a_4a_3)+(a_8a_7a_6)-\dots$ is divisible by 7. For example 12383. We divide the digits into groups 12 383 and subtract to get 371. That is divisible by 7, so 12383 is divisible by 7.

This approach can be used for divisors outside the range 2-9. The idea is to look for divisors of $B^k+1$. It also works for $B^k-1$ (but you add the groups instead of alternately adding and subtracting them. Since $1001=7\times11\times13$ the test for 7 can be used for 11 and 13 at the same time. For example, 371 is not divisible by 11 or 13, so 12383 is also not divisible by 11 or 13.