Divisibility rule for large primes

Question

I've got a large prime $p$. Let's say $$ p = 2137 $$ Is there a simpler way to determine whether $p\mid n : n \in \mathbb{Z}$ than factorizing $n$? Divisibility rules are uncommon for integers larger than 30, let alone primes.

Answer 1

We can assess which primes $p$ give relativy small orders for $10\bmod p$ and thus allow testing with sums or alternating sums of relatively small digit blocks. Here are the ground rules:

• If $p$ divides $10^k+1$, then divisibility by $p$ is tested using the alternating sum of$k$-digit blocks. This corresponds to $10$ having order $2k$.

• If $p$ divides $10^k-1$ for odd $k$, then divisibility by $p$ is tested using the sum of$k$-digit blocks. This corresponds to $10$ having order $k$. The rule also works for even $k$, but in that case we could use one of the two rules for half the value of $k$.

If we are willing to sum blocks up to four digits, then we can test prime factors of $9, 11, 101, 999, 1001, 10001$ (using $10^k-1$ only for odd $k$). Let us look at these cases in turn:

$9=\color{blue}{3}^2$: This is the familiar sum of digits test for divisibility by 3 (or 9)

$\color{blue}{11}=\text{ prime}$: This gives the alternating sum of digits test for divisibility by 11.

$\color{blue}{101}=\text{ prime}$: The alternating sum of two-digut blocks, rather anticlimactically, gives only a test for divisibility by 101. Things get more interesting when $10^k+1$ is composite.

$999=3^3×\color{blue}{37}$: The sum of three-digit blocks provides a divisibility test for 37. Although this is the only new prime factor, the same test can be used for the composite factor 27. The next power of 3, however, would require nine-digit blocks and is out of this answer's scope.

$1001=\color{blue}{7}×11×\color{blue}{13}$: So you want a divisibility test for 7, a popular subject around here. The alternating sum of three-digit groups does that and throws 13 in to boot. We generally get a three-digit result for which we likely would want a supplemental test. My preference here, still applicable to both 7 and 13, is to multiply the last digit by 9 and take the difference with the remaining two digits. Thus is based on the sub-product $7×13=91$, or reckoning with the difference of cubes factorization $7×13=10^2-10+1$.

$10001=\color{blue}{73}×\color{blue}{137}$. Divisibility by 73 and by 137 is tested with alternating sums of four-digit groups. The number 137 is the largest prime that can be tested using simple sums of alternating sums involving four or fewer digits.

If we include a multiplier like the supplemental test for 7 and 13, then we can access factors of $m(10^k)\pm 1$ where $m$ is the multiplier. For instance, $2×10^3+1=3×\color{blue}{23}×\color{blue}{29}$ give a test for divisibility by both 23 and 29 by doubling the last three digits and taking the difference with the remaining digits.

Answer 2

This is a variation of the repeated subtraction algorithm:

Let $p\nmid 10$ be a prime number, $a_0>0$ and consider the sequence defined recursively by $$a_{n+1}=\frac{a_n-(p^3a_n\bmod 10)p}{10}$$ The sequence $a_n$ for $n\in\Bbb N$ is decreasing and $p\mid a_0$ if and only if $a_n=0$ for some $n\in\Bbb N$.

Remark: Note that $p^3a_n\bmod 10$ depends only on the right-most digit of $a_n$ and $p$. Moreover, the number of step required to get $0$ is the difference between the number of digits of $a_0$ with the number of digits of $p$. Thus the number of steps decreases as $p$ increases.

Proof. Clearly, $a_n\equiv 10a_{n+1}\pmod p$, hence $p\mid a_n$ if and only if $p\mid a_{n+1}$. Thus if $a_n=0$ for some $n$, then $p\mid a_0$. Conversely, assume $p\mid a_0$ and let $a_n$ be the last positive term, that's $a_{n+1}\leq 0<a_n$. Since $p\mid a_n$ we have $a_n=qp$ for some $q$, hence $p^3a_n\equiv p^4q\equiv q\pmod{10}$. Since $a_{n+1}\leq 0$, we have $q\leq 9$, hence $a_{n+1}=(a_n-qp)/10=0$.

---

For example, for $p=2137$, the recurrence can be written as $$a_{n+1}=\frac{a_n-2137(3a_n\bmod 10)}{10}$$