1
$\begingroup$

I was studying this page Divisibility by prime numbers under 50 to check for the divisibility by 7, 11, 13, 17, 19 etc. Is there any way to recognise whether to add or sub the given times of unit digit from the truncated number and to know how many times do I have to multiply with the unit digit.

For example:

to check for the divisibility by 7: subtract 2 times the unit digit from truncated number.

for 11: subtract 1 times

for 13: add 4 times the unit digit etc.

$\endgroup$
  • $\begingroup$ Do you know modular arithmetic (congruences)? $\endgroup$ – Bill Dubuque Jan 24 '15 at 22:45
3
$\begingroup$

Yes, we can. Suppose we want to test a number $n$ for divisibility by $d$. Notice that we can expand $n$ with a result of $x$ after truncating the last digit $y$: $$n=10x+y.$$ And we want to find some number $n'$ of the form $n'=x+\alpha y$ such $n'$ is divisible by $d$ exactly when $n$ is. For numbers not divisible by $2$ or $5$, there is an elegant solution to this; in particular, there is some number $\alpha$ such that $d$ divides $10\alpha - 1 $. Why this matters is then we can write $$n'=\alpha n = 10\alpha x + \alpha y$$ which will be divisible by $d$ exactly when $n$ was ($\alpha$ and $d$ must be coprime, meaning that $k\alpha$ is divisible by $d$ exactly when $k$ was) but since $10\alpha = cd + 1$ for some integer $c$ (because $10\alpha -1$ is a multiple of $d$), we can write this as: $$n'=(cd+1)x + \alpha y$$ and we can get rid of the $cd$ term, since it is divisible by $d$ and clearly if $n$ is divisible by $d$, so is $n-kd$ for any integer $k$. Thus, for our purposes, we can replace $n$ by $x+\alpha y$, getting rid of the $cdx$ term, without changing issues of divisibility by $d$.

This $\alpha$ term is the multiplicative inverse of $10$ mod $d$, which can be computed either by the Extended Euclidean algorithm, as described on the Wikipedia page. Trial and error would work too (you just need to find the first positive multiple of $d$ with a $9$ in the one's place or a negative multiple with a $1$ in the one's place). Notice that your existing identities follow this pattern; for $d=7$, we choose $\alpha=-2$, and $10\cdot (-2) - 1 = -21$, which is a multiple of $7$. Similarly, for $11$, we have $\alpha=-1$ and $10\cdot (-1) - 1 = -11$, which is a multiple of $11$ and, for $13$, we have $10\cdot 4 - 1 = 39$, which is a multiple of $13$.

So, for instance, to find a rule for $17$, we would notice that $-3\cdot 17= -51 = 10\cdot -5-1$. Thus, to compute divisibility by $17$, we chop off the unit digit $y$, and subtract $3y$ from the remaining number. To be very explicit, we can give the following general rules for divisibility tests of this form:

  • If $d=10k + 1$, then subtract $k$ times the unit digit from the rest.
  • If $d=10k + 3$, then add $3k+1$ times times the unit digit to the rest.
  • If $d=10k + 7$, then subtract $3k+2$ times the unit digit from the rest.
  • If $d=10k + 9$, then add $k+1$ times the unit digit to the rest.
$\endgroup$
  • $\begingroup$ excellent answer. thank you. $\endgroup$ – JerryGoyal Jan 24 '15 at 23:11
1
$\begingroup$

You can know what it should be by understanding where these formulas come from in the first place. As far as I am aware, there is no easy mnemonic device to memorize them by, but here is an explanation for why it works for 7 (The same or similar method works for proving the other cases as well).

For the purposes of this discussion, I will write numbers in the form $X = 10x_1 + x_0$. That is to say, $x_0$ represents the ones digit of the number $X$ and $x_1$ represents the rest of the number. (For example, $568 = 10\cdot 56 + 8$)

So, $X\mod 7 \equiv 10x_1 + x_0 \mod 7\equiv 10x_1 +x_0 - 7\cdot(3x_0)\mod 7$

(by properties of modular arithmetic, we may always multiply by "one" or add "zero", which in this sense means multiplying by one more than a multiple of 7 or adding a multiple of seven)

$\equiv 10x_1 - 20x_0 \mod 7\equiv 10(x_1 - 2x_0)\mod 7\equiv 3(x_1-2x_0)\mod 7$

This is then equivalent to zero if and only if $(x_1-2x_0)$ is equal to zero (since gcd(3,7)=1).

That is to say, $10x_1 + x_0$ is a multiple of 7 if and only if $x_1-2x_0$ is a multiple of 7.


Note, there is nothing particularly unique about the choice of doing $x_1 - 2x_0$. It was suggested as such because it will definitely make the number smaller and the numbers are relatively easy to work with, however we could also have chosen $x_1 + 5x_0$

$\endgroup$

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.