Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We all know how to recognize numbers that are multiple of $2, 3, 4, 5$ (and other). Some other divisors are a bit more difficult to spot. I am thinking about $7$.

A few months ago, I heard a simple and elegant way to find multiples of $7$:

Cut the digits into pairs from the end, multiply the last group by $1$, the previous by $2$, the previous by $4$, then $8$, $16$ and so on. Add all the parts. If the resulting number is multiple of $7$, then the first one was too.

Example:

$21553$

Cut digits into pairs:

$2, 15, 53$

Multiply $53$ by $1, 15$ by $2, 2$ by $4$:

$8, 30, 53$

Add:

$8+30+53=91$

As $91$ is a multiple of $7$ ($13 \cdot 7$), then $21553$ is too.

This works because $100-2$ is a multiple of 7. Each hundreds, the last two digits are 2 less than a multiple of $7 (105 → 05 = 7 - 2, 112 → 12 = 14 - 2, \cdots)$

I figured out that if it works like that, maybe it would work if we consider $7=10-3$ and multiplying by $3$ each digit instead of $2$ each pair of digits.

Exemple with $91$:

$91$

$9, 1$

$9\cdot3, 1\cdot1$

$27, 1$

$28$

My question is: can you find a rule that works with any divisor? I can find one with divisors from $1$ to $19$ ($10-9$ to $10+9$), but I have problem with bigger numbers. For example, how can we find multiples of $23$?

share|improve this question
8  
You'll want to see this KCd blurb. –  J. M. Dec 8 '11 at 15:49
6  
I've seen the following method for 7: Take the last digit, double it, and subtract it from the first digits. So $21553$ leads to $2155-3*2=2149$. Next step is $214-2*9=196$. Next $19-2*6=7$. –  Thomas Andrews Dec 8 '11 at 16:04
1  
How can we find divisors of 23? Very easily: they are just $\pm 1$ and $\pm 23$. Presumably, you want to recognize multiples of 23? –  Arturo Magidin Dec 8 '11 at 16:11
    
For $23$, here is something fairly simple, for numbers that have $3$ or $4$ digits, say $abcd$. Take the number $ab$, add to it $3$ times the number $cd$. Call the result $t$. Then $abcd$ is a multiple of $23$ iff $t$ is. One could probably tweak this to be even simpler to execute. –  André Nicolas Dec 8 '11 at 16:16
    
@ArturoMagidin Yes, I meant multiples. It's corrected. –  Oltarus Dec 9 '11 at 8:46
add comment

6 Answers 6

up vote 6 down vote accepted

One needn't memorize motley exotic divisibility tests. There is a universal test that is simpler and much easier recalled, viz. evaluate a radix polynomial in nested Horner form, using modular arithmetic. For example, consider evaluating a $3$ digit radix $10$ number modulo $7$. In Horner form $\rm\ d_2\ d_1\ d_0 \ $ is $\rm\: (d_2\cdot 10 + d_1)\ 10 + d_0\ \equiv\ (d_2\cdot 3 + d_1)\ 3 + d_0\ (mod\ 7)\ $ since $\rm\ 10\equiv 3\ (mod\ 7)\:.\:$ So we compute the remainder $\rm\ (mod\ 7)\ $ as follows. Start with the leading digit then repeatedly apply the operation: multiply by $3$ then add the next digit, doing all of the arithmetic $\rm\:(mod\ 7)\:.\:$

For example, let's use this algorithm to reduce $\rm\ 43211\ \:(mod\ 7)\:.\:$ The algorithm consists of repeatedly replacing the first two leading digits $\rm\ d_n\ d_{n-1}\ $ by $\rm\ d_n\cdot 3 + d_{n-1}\:\ (mod\ 7),\:$ namely

$\rm\qquad\phantom{\equiv} \color{red}{4\ 3}\ 2\ 1\ 1$

$\rm\qquad\equiv\phantom{4} \color{green}{1\ 2}\ 1\ 1\quad $ by $\rm\quad \color{red}4\cdot 3 + \color{red}3\ \equiv\ \color{green}1 $

$\rm\qquad\equiv\phantom{4\ 3} \color{royalblue}{5\ 1}\ 1\quad $ by $\rm\quad \color{green}1\cdot 3 + \color{green}2\ \equiv\ \color{royalblue}5 $

$\rm\qquad\equiv\phantom{4\ 3\ 5} \color{brown}{2\ 1}\quad $ by $\rm\quad \color{royalblue}5\cdot 3 + \color{royalblue}1\ \equiv\ \color{brown}2 $

$\rm\qquad\equiv\phantom{4\ 3\ 5\ 2} 0\quad $ by $\rm\quad \color{brown}2\cdot 3 + \color{brown}1\ \equiv\ 0 $

Hence $\rm\ 43211\equiv 0\:\ (mod\ 7)\:,\:$ indeed $\rm\ 43211 = 7\cdot 6173\:.\:$ Generally the modular arithmetic is simpler if one uses a balanced system of representatives, e.g. $\rm\: \pm\{0,1,2,3\}\ \:(mod\ 7)\:.$ Notice that for modulus $11$ or $9\:$ the above method reduces to the well-known divisibility tests by $11$ or $9\:$ (a.k.a. "casting out nines" for modulus $9\:$).

share|improve this answer
add comment

One approach is to find some higher multiple that makes it easy. For your example of $23$, note that $3*23+1=70$, so $a(70-1)$ will be a multiple of $23$. Now you have a single digit multiply followed by a subtraction. If you pick $a=301, a(70-1)=301(70-1)=301*70-301=2107-301=1806$, which is a multiple of $23$

share|improve this answer
    
I generally find this method much easier than the standard modular divisibility test. It does require that you memorize a starting list of multiples, but it's not so bad because you can just multiply them by powers of $10$. –  Qiaochu Yuan Dec 8 '11 at 18:28
    
@QiaochuYuan: It seemed the OP's request was to find multiples, not do a divisibility test. But this generalizes. In the spirit of the test for $7$, to test divisibility by $23$, you can take off the last digit, multiply the rest by $7$ and add the last digit. Keep going until you have only two digits left. You just have to find a multiple that ends in $1$ or $9$ to do this. –  Ross Millikan Dec 8 '11 at 18:40
add comment

In general, if you are doing things by dividing the number into groups of $k$ digits, you can think of it as looking at the number in base $10^k.$

More generally, if $B$ is a base, and $n$ is a number with no common factors with $B$, then you can always find an $m$ such that $Bm\equiv 1\pmod n$. Then $X\equiv 0\pmod n$ if and only if $Xm\equiv 0\pmod n$. But if $X=Bu+v$, then $Xm\equiv u+mv\pmod n$. So if we take the last digit, base B, multiply it by $m$ and add it to the other digits, the result is divisible by $n$ if and only if the original number was divisible by $n$.

In the case of $n=23$ base $B=10$, you get $m=7$, so you can take the last digit, multiply it by seven, and add it to the rest.

Or, if you use $B=100$, you get $m=3$, and you can take the lsat two digits, multiply by 3, and add to the other digits.

In general, you can always find a $k$ such that $10^k=1\pmod n$ if $n$ is not even or divisible by 5. Then if you take base $B=10^k$, you get $m=1$, and you can separate $m$ into groups of $k$ digits and add them. That's hardly useful when $k$ is large. For example, the smallest $k$ for $n=23$ is $k=22$, so this part only helps if your starting number was more than 23 digits long.

Usually, you want to find a relatively small pair $(m,k)$ so that $m10^k\equiv \pm 1\pmod n$. Then you take the last $k$ digits, multiplied by $m$, and add to or subtract from the other digits, depending on whether $+1$ or $-1$.

share|improve this answer
add comment

The following is a simple method to check divisibility by $7$ or $13$:

Cut the digits in pairs of 3 and calculate their alternating sum. If this is a multiple of 7 or 13, the original number is.

For example

$12345631241$ leads to

$$241-639+345-12=-65 \,.$$

Thus our number is a multiple of $13$, but not a multiple of $7$.

This works because $1001=7*11*13$ meaning that any number of the form $abcabc$ is a multiple of $7, 11$ and $13$...The trick also works for 11, but there is another simple trick.


Method 2 If the number is relatively prime to 10 (if it is not, you can make it), look for a multiple on $n$ which ends in 1.

Let say that this multiple is $a_1..a_k1$.

Then you simply pick the large number and subtract $a_1...a_k*$last digit from the remaining digits.

The trick works because $a_1...ak1$*last digit is always a multiple of $n$, and subtracting this from the original number you get a multiple of 10..Since $n$ is relatively prime to 10, you can erase the 0 at the end...

A simple such example, for $7$ the smalest such desires multiple is ... 21, which leads to the criteria posted by Thomas Andrews .

Also, for small numbers the following

share|improve this answer
add comment

I will try to explain a general rule using modular congruence. We can show that any integer in base $10$ can be written as $$ z = a_0 + a_1 \times 10 + a_2 \times 10^2 + a_3 \times10^3 + \cdots + a_n \times 10^n$$

Lets say we have to find a divisibility rule of $7$,Hence for congruence modulo $7$ have,

$$ 10 \equiv 3, 10^2 \equiv 2, 10^3 \equiv -1, 10^4 \equiv -3, 10^5 \equiv -2, 10^6 \equiv 1,$$

The successive remainder then repeat. Thus our integer $z$ is divisible by $7$ iff if the remainder expression $$ r= a_0 + 3a_1 +2a_2 -a_3-3a_4-2a_5+a_6+3a_7+\cdots$$ is divisible by $7$

To understand why the divisibility of $r$ indicate the divisibility of $z$, find $z-t$ which is given by :$$z-t = a_1 \times (10-3) + a_2 \times (10^2-2) + a_3 \times (10^3+1) + \cdots + a_6 \times (10^6-1) + \cdots $$ Since all this numbers $ (10-3),(10^2-2),(10^3+1),\cdots$ are congruent to 0 modulo $7,z-t$ is also, and therefore $z$ leaves the same remainder on division by $7$ as $r$ does.

Using this approach we can derive divisibility of any integer.

share|improve this answer
add comment

This can be explained using Horner's method as below. z=a0 + a1 ×10 + a2 ×102 + a3 × 10^3+⋯+ an × 10^n

i.e. Z = ((((...(an × 10 + an-1)*10 + an-2 )*10 + an-3).....)*10 + a0

                           ( Shift-add representation of number)

Z % 7 =  ((((...(an × 3 + an-1)*3 + an-2 )*3 + an-3).....)*3 + a0  (Mod 7)

Now evaluate from left to right using modulo algebra.

To know more about shift- add representation of number and its application in interbase conversion and divisibility refer tinyurl.com/mlxk8pw .

                         Regard,
                            Vitthal Jadhav
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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