0
$\begingroup$

I'm looking for a divisibility test for numbers of the form $10n \pm1$

I need the test to be a summation across digits like the one for $11$, that being, a number $\overline{d_n \ldots d_1 }$ is divisible by 11 if $$ \sum_{i \; even} d_{i+1} - d_i \pmod{11} = 0 $$

I'm after a similarly styled test for all $10n \pm1$. Is there a nice way to generate them?

Thanks in advance for your help!

$\endgroup$
6
  • 1
    $\begingroup$ @Peter Neither. I want a rule for 19, 21, 29, 31, 39, 41, ... $\endgroup$ – Ben Crossley Jun 18 '19 at 7:51
  • $\begingroup$ Sorry, I somehow read $10^n$ instead of $10n$ $\endgroup$ – Peter Jun 18 '19 at 7:52
  • $\begingroup$ @Peter So then $10n \equiv -9n \pmod{19}$ would give us sum of even digits minus 9 times the odd digits? Or $100n \equiv 5n \pmod{19}$ So 10 times even + 5 times odd digits. $\endgroup$ – Ben Crossley Jun 18 '19 at 8:04
  • $\begingroup$ The divisibility rule for $11$ only works because the residue of $10^n$ switches between $-1$ and $1$. For $19$, the rule is much more complicated. $\endgroup$ – Peter Jun 18 '19 at 8:09
  • $\begingroup$ I see, is that why the rule for 7 involves 142857? I noticed that 10^6-1 =999999, and 999999/7 = 142857. I'm assuming it's to do with the first 10^n-1 that the divisor goes into. $\endgroup$ – Ben Crossley Jun 18 '19 at 8:12
0
$\begingroup$

Example for the number $19$ : The order of $10$ modulo $19$ is $18$, therefore you can divide the given number into $18$-digit-blocks from behind. The first block usually will have less than $18$ digits. Then, you can sum up the residues modulo $19$ of those blocks (considered as a natural number) and the given number is divisible by $19$ if and only if the sum is divisible by $19$.

A bit easier to use is the following rule : Divide the number into $9$-digit blocks from behind, the first block usually will have less than $9$ digits. Then, begin with residue modulo $19$ of the first block, then subtract the residue of the next, then add and so on. The given number is divisible by $19$ , if and only if the final result is divisible by $19$.

Example : $$5645012950185238747288629$$

Dividing gives $$5645012\ 950185238747288629$$

$5645012$ has redisue $17$ and $950185238747288629$ has redisue $2$ , the sum is $19$. Hence , the given number is disible by $19$

$$5645012\ 950185238\ 747288629$$

If we divide in $9$-digit - blocks, we get the residues $17,7,9$ and $17-7+9=19$ which is divisible by $19$, hence the given number is disivible by $19$.

$\endgroup$
3
  • 1
    $\begingroup$ Thank you. Do you know of a method for 1-digit blocks / if one exists? $\endgroup$ – Ben Crossley Jun 18 '19 at 10:13
  • $\begingroup$ Within the $18$-digit blocks and with the suitable "weights". we could construct a formula using the single digits, but this would even be more messy and moreover, we would not have considered the first block. $\endgroup$ – Peter Jun 18 '19 at 10:15
  • $\begingroup$ An analogue to $11$ does not exist. $\endgroup$ – Peter Jun 18 '19 at 10:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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