# Generalization of digit-wise divisibility lemmas [duplicate]

This question already has an answer here:

## Background

In undergraduate Abstract Algebra homework, for an integer $$n$$ with decimal representation $$a_m a_{m-1} ... a_1 a_0$$, I proved that

1. $$3$$ divides $$n \iff 3$$ divides $$\sum_{i = 0}^{m} a_i$$, and
2. $$11$$ divides $$n \iff 11$$ divides $$\sum_{i = 0}^{m} (-1)^i a_i$$.

Proofs of these facts can be found here and here, respectively.

## My Question

For an arbitrary prime $$p$$, can we deterministically formulate a non-vacuous statement of the form

$$\forall n \text{ expressible as } n = a_m a_{m-1} ... a_0 \in \mathbb{N}, \text{ we have that } p \mid n \iff p \mid \sum_{i = 0}^{m} b_i a_i$$

(... where the trick of formulating this statement is coming up with the sequence $$(b_i)_0^m$$)? I am interested in additive structure to the primes, and I am wondering if this type of exercise could show some interesting structure.

## marked as duplicate by José Carlos Santos, Daniele Tampieri, Mars Plastic, Community♦Aug 21 at 16:20

The type of thing I am asking for is called a divisibility rule. The previously linked Wikipedia article gives a general rule to test for divisibility by $$D$$ when $$D$$ ends in 1, 3, 7, or 9, as well as a general rule for $$D$$ when $$D$$ is prime.
It remains to be shown how we can handle $$D$$ ending in 0, 2, 4, 5, 6, or 8. But this is easy.
• $$D$$ ends in 0: Let $$k$$ be the number of times that $$10$$ divides $$D$$. Check that $$n$$ is divisible by both $$10^k$$ and $$D * 10^{-k}$$.
• $$D$$ ends in 2, 4, 6, or 8: Check that $$n$$ is even and is divisible by $$D / 2$$. This recurses at most twice since $$2 = 2, 4 = 2 * 2, 6 = 3 * 2, 8 = 2 * 2 * 2$$.
• $$D$$ ends in 5: Check that $$n$$ ends in 0 or 5, and $$n$$ is divisible by $$D / 5$$.
• divisibility by 1024 might challenge that, but divisibility by 4 can literally check the last 2 digits, if they don't form a number that's divisible by 4 then the number isn't divisible by 4. Likewise divisibility by 8, can be checked using the last 3 digits. 16 the last 4, 32 the last 5, $2^n$ the last n. – Roddy MacPhee Aug 21 at 12:08
• 1024 $\to$ 2, 512 $\to$ 2, 2, 256 $\to$ 2, 2, 128 $\to$ 2, 2, 2, 64 $\to$ 2, 2, 2, 2, 32 $\to$ 2, 2, 2, 2, 16 $\to$ 2, 2, 2, 2, 2, 8 $\to$ 2, 2, 2, 2, 2, 2, 2, 2 ... yeah you're right, Roddy, that is not anywhere near as convenient as I'd like. This issue can just be generalized to things of the form $2^n$. On the bright side, left-shifting is computationally easy, so I think we can deal with this problem with $\mathcal{O}(\log n)$ shifts. – Max von Hippel Aug 21 at 16:24
• same thing goes to powers of 5, $5^n$ needs the last n. Don't get started on different bases. – Roddy MacPhee Aug 21 at 16:38