Easy ways of finding small prime divisors

Question

Are there any "relatively simple" ways of seeing whether a number is divisible by a small prime not 3. For example, one simply sums the digits of n modulo 3 and if they sum to zero, then n is divisible by 3, or that if it ends in a 5 or a 0 then $5|n$. Are there any similarly "easy" ideas for primes like 7, 11 etc.

The motivation for this is factorisation algorithms, nothing new or groundbreaking but just trying some things with some existing (and fairly rubbish by modern standards) algorithms.

Answer 1

All those "easy" ideas come from expanding in base $10$ and take the powers of $10$ mod $n$.

For instance If you have a number $\overline{abcdefg}$ and want to check if is multiple of $7$, what you do is \begin{align}\overline{abcdefg}&=g+10f+10^2e+10^3d+10^4c+10^5b+10^6a\\ &=1g+3f+2e-1d-3c-2b+1a\mod 7 \end{align} Note the pattern $1,3,2,-1,-3,-2,1,3,2,-1,-3,-2,\dots$ appearing as coefficients.

If you want to check mod $11$, what you do is \begin{align}\overline{abcdefg}&=g+10f+10^2e+10^3d+10^4c+10^5b+10^6a\\ &=g-f+e-d+c-b+a\mod 11 \end{align} So, you get an easier pattern $1,-1,1,-1,1,-1,\dots $ as coefficients.

Answer 2

Depends on what you call small,as:

Largest multiple of $7$ lower than some $78$-digit number?

shows. If by small you mean less than 79 then , This method would work usefully (79 and above doesn't split the number up, without 10 having a smaller than maximal order mod the prime). It probably doesn't count as simple though. However, it is the basis of the "relatively simple" methods used most often, besides long division.

Factoring out (related to distributivity of multiplication over addition/subtraction), and the subtracting 0 does nothing rule ( additive identity rule) is what long division works on.

Addendum This actually works in any base, the rules for individual numbers change though. Like in base 5041 all 60 divisors of $5040=2^43^25^17^1$ have the sum of digits has to be a multiple rule. All divisors of $5042 = 2^12521$ (sadly only 1 that hasn't got a rule already) would have the alternating add and subtract digits rule. And 71 would have the last digit rule that 5 or 2 have in base 10.