1
$\begingroup$

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.

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

0
$\begingroup$

Although, as Iab pointed out, this question turns out to be a duplicate, I think it is helpful to coalesce information from multiple sources into one clear answer. (At least, it is helpful to me.) This is my attempt to do that.

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$.
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Roddy MacPhee Aug 21 at 12:08
  • $\begingroup$ 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. $\endgroup$ – Max von Hippel Aug 21 at 16:24
  • 1
    $\begingroup$ same thing goes to powers of 5, $5^n$ needs the last n. Don't get started on different bases. $\endgroup$ – Roddy MacPhee Aug 21 at 16:38

Not the answer you're looking for? Browse other questions tagged or ask your own question.