Divisibility rules

A number x is said to be divisible by y, written y | x (read y divides x), iff ∃ k ∈ Z: ky = x. Divisibility rules provide a way of determining whether a given (large) number is divisible by another (small) number without actually performing the division. They usually transform a number into a smaller number while preserving divisibility by a fixed divisor.

  • Divisibility by 2

A number is divisible by 2 iff its last digit is divisible by 2 i.e., its last digit is 0, 2, 4, 6 or 8.

  • Divisibility by 3

A number is divisible by 3 iff the sum of its digits is divisible by 3, e.g., 12123 (1+2+1+2+3=9) 9 is divisible by 3 and so is 12123.

  • Divisibility by 4

A number is divisible by 4 iff the number formed by its last 2 digits is divisible by 4, e.g., 4032 ends in 32, which is divisible by 4 and so is 4032.

  • Divisibility by 5

A number is divisible by 5 iff its last digit is 0 or 5, e.g., 5067805 ends in 5 and is divisible by 5.

  • Divisibility by 6

A number is divisible by 6 iff it is divisible by both 2 and 3 i.e., its last digit is even and sum of its digits is divisible by 3, e.g., 1458 (1+4+5+8=18) is divisible by 6 since the last digit (8) is even and the sum 18 is divisible by 3.

  • Divisibility by 7

It’s a little tricky to check divisibility by 7. There are several tests but here’s an easy one:

Multiply each digit beginning on the right hand side by the corresponding digit in this pattern [1,3,2,6,4,5] (or [1,3,2,-1,-3,-2]). Repeat the pattern as necessary. If the sum of the products is divisible by 7, then so is the original number.

Example: 2016 (6*1+1*3+0*2+2*6=21) is divisible by 7 since 21 is divisible by 7.

  • Divisibility by 8

A number is divisible by 8 iff the number formed by its last 3 digits is divisible by 8, e.g., 6008 is divisible by 8 since 8 is divisible by 8.

  • Divisibility by 9

A number is divisible by 9 iff the sum of its digits is divisible by 9, e.g., 43785 (4+3+7+8+5=27) is divisible by 9 since 27 is divisible by 9.

  • Divisibility by 10

A number is divisible by 10 iff its last digit is 0.

  • Divisibility by larger composite numbers

A number is divisible by a composite number iff it is divisible by the highest power of each of its prime factors e.g., we can check for divisibility by 252 (252=22*32*7) by checking for divisibility by 4, 9 and 7. Similarly, we can check for divisibility by 525 (525=3*52*7) by checking for divisibility by 3, 25 and 7.

  • Generalized divisibility rule

This rule lets us test divisibility by any divisor D which ends in 1, 3, 7 or 9. It works as follows: Find a multiple of D which ends in 9 (If D ends in 1, 3, 7 or 9, multiply by 9, 3, 7 or 1 respectively). Add 1 and divide by 10, call the result m. A given number N=10t+q is divisible by D iff mq+t is divisible by D.

Example: To check if 913 (10*91+3, t=91, q=3) is divisible by 11, find m=(11*9+1)/10=10. Now mq+t = 10*3+91=121 is divisible by 11 and so is 913.

See problems NITT2 and PUCMM025 which use these ideas.

References:

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s