Divisibility Rule for 2 and Powers of 2

A number is divisible by by if and only if the last digits of the number are divisible

. Thus, in particular, a number is divisible by 2 if and only if its units digit is

divisible by 2, i.e. if the number ends in 0, 2, 4, 6 or 8. Proof

Divisibility Rule for 3 and 9

A number is divisible by 3 or 9 if and only if the sum of its digits is divisible by 3 or 9, respectively. Note that this does not work for higher powers of 3. For instance, the sum of the digits of 1899 is divisible by 27, but 1899 is not itself divisible by 27. Proof

Divisibility Rule for 5 and Powers of 5

A number is divisible by Proof if and only if the last digits are divisible by that power of 5.

Divisibility Rule for 7

Rule 1: Partition alternating sum ( divisible by 7. Proof Rule 2: Truncate the last digit of the number (or vice-versa). Proof Rule 3: "Tail-End divisibility." Note. This only tells you if it is divisible and NOT the remainder. Take a number say 12345. Look at the last digit and add or subtract a multiple of 7 to make it zero. In this case we get 12380 or 12310 (both are acceptable; I am using the former). Lop off the ending 0's and repeat. 1238 - 28 ==> 1210 ==> 121 - 21 ==> 100 ==> 1 NOPE. Works in general with numbers that are relatively prime to the base (and works GREAT in binary). Here's one that works. 12348 - 28 ==> 12320 ==> 1232 +28 ==> 1260 ==> 126 + 14 ==> 14 YAY! , double that digit, and subtract it from the rest of into 3 digit numbers from the right ( ). The is

) is divisible by 7 if and only if

is divisible by 7 if and only if the result is divisible by 7.

Divisibility Rule for 10 and Powers of 10

If a number is power of 10, define it as a power of 10. The exponent is the number of zeros that should be at the end of a number for it to be divisible by that power of 10. Example: A number needs to have 6 zeroes at the end of it to be divisible by 1,000,000 because .

Divisibility Rule for 11

A number is divisible by 11 if and only if the alternating sum of the digits is divisible by 11. Proof

Divisibility Rule for 13

Rule 1: Truncate the last digit, multiply it by 4 and add it to the rest of the number. The result is divisible by 13 if and only if the original number was divisble by 13. This process can be repeated for large numbers, as with the second divisibility rule for 7. Proof Rule 2: Partition alternating sum ( divisible by 13. Proof into 3 digit numbers from the right ( ). The is

) is divisible by 13 if and only if

Divisibility Rule for 17

Truncate the last digit, multiply it by 5 and subtract from the remaining leading number. The number is divisible if and only if the result is divisible. The process can be repeated for any number. Proof

Divisibility Rule for 19

Truncate the last digit, multiply it by 2 and add to the remaining leading number. The number is divisible if and only if the result is divisible. This can also be repeated for large numbers. Proof

Divisibility Rule for 29

Truncate the last digit, multiply it by 3 and add to the remaining leading number. The number is divisible if and only if the result is divisible. This can also be repeated for large numbers. Proof

More general note for primes

For every prime number other than 2 and 5, there exists a rule similar to rule 2 for divisibility by 7. For a general prime is divisible by , there exists some number such that an integer and subtracting

if and only if truncating the last digit, multiplying it by

it from the remaining number gives us a result divisible by that for ,

. Divisibility rule 2 for 7 says . The

. The divisibility rule for 11 is equivalent to choosing

divisibility rule for 3 is equivalent to choosing

. These rules can also be found

under the appropriate conditions in number bases other than 10. Also note that these rules exist in two forms: if is replaced by then subtraction may be replaced with

addition. We see one instance of this in the divisibility rule for 13: we could multiply by 9 and subtract rather than multiplying by 4 and adding.

A very important one for Divisibility

More general note for composites
A number is divisible by , where the prime factorization of . is , if the

number is divisible by each of

Example
Is 55682168544 divisible by 36?

Solution
First, we find the prime factorization of 36 to be divisibility by 4 and 9 to see if it's divisible by 36. Since the last two digits, 44, of the number is divisible by 4, so is the entire number. To check for divisibility by 9, we look to see if the sum of the digits is divisible by 9. The sum of the digits is 54 which is divisible by 9. . Thus we must check for

Thus, the number is divisible by both 4 and 9 and must be divisible by 36.

Divisibility
Problem: Method: Is the number 621 prime or composite?

Unit 3 > Lesson 4 of 9

In the last lesson, we learned to find all factors of a whole number to determine if it is prime or composite. We used the procedure listed below. To determine if a number is prime or composite, follow these steps:
1. 2. 3. Find all factors of the number. If the number has only two factors, 1 and itself, then it is prime. If the number has more than two factors, then it is composite.

The above procedure works very well for small numbers. However, it would be timeconsuming to find all factors of 621. Thus we need a better method for determining if a large number is prime or composite. Every number has one and itself as a factor. Thus, if we could find one factor of 621, other than 1 and itself, we could prove that 621 is composite. One way to find factors of large numbers quickly is to use tests for divisibility.
Definition Example

One whole number is divisible by another if, 18 is divisible by 9 since 18 9 after dividing, the remainderis zero. = 2 with a remainder of 0. If one whole number is divisible by another Since 18 is divisible by 9, 9 is a number, then the second number is a factor factor of 18. of the first number. A divisibility test is a rule for determining whether one whole number is divisible by another. It is a quick way to find factors of large numbers. Divisibility Test for 3: if the sum of the digits of a number is divisible by 3, then the number is divisible by 3.

We can test for divisibility by 3 (see table above) to quickly find a factor of 621 other than 1 and itself. The sum of the digits of 621 is 6+2+1 = 9. This divisibility test and the definitions above tell us that...

621 is divisible by 3 since the sum of its digits (9) is divisible by 3. Since 621 is divisible by 3, 3 is a factor of 621. Since the factors of 621 include 1, 3 and 621, we have proven that 621 has more than two factors. Since 621 has more than 2 factors, we have proven that it is composite.

Let's look at some other tests for divisibility and examples of each.
Divisibility Tests Example

A number is divisible by 2 if the last 168 is divisible by 2 since the last digit digit is 0, 2, 4, 6 or 8. is 8. A number is divisible by 3 if the sum 168 is divisible by 3 since the sum of of the digits is divisible by 3. the digits is 15 (1+6+8=15), and 15 is

divisible by 3. A number is divisible by 4 if the 316 is divisible by 4 since 16 is number formed by the last two digits divisible by 4. is divisible by 4. A number is divisible by 5 if the last 195 is divisible by 5 since the last digit digit is either 0 or 5. is 5. A number is divisible by 6 if it is 168 is divisible by 6 since it is divisible divisible by 2 AND it is divisible by 3. by 2 AND it is divisible by 3. A number is divisible by 8 if the number formed by the last three digits is divisible by 8. 7,120 is divisible by 8 since 120 is divisible by 8.

A number is divisible by 9 if the sum 549 is divisible by 9 since the sum of of the digits is divisible by 9. the digits is 18 (5+4+9=18), and 18 is divisible by 9. A number is divisible by 10 if the last digit is 0. 1,470 is divisible by 10 since the last digit is 0.

Let's look at some examples in which we test the divisibility of a single whole number. Example 1: Determine whether 150 is divisible by 2, 3, 4, 5, 6, 9 and 10. 150 is divisible by 2 since the last digit is 0. 150 is divisible by 3 since the sum of the digits is 6 (1+5+0 = 6), and 6 is divisible by 3. 150 is not divisible by 4 since 50 is not divisible by 4. 150 is divisible by 5 since the last digit is 0. 150 is divisible by 6 since it is divisible by 2 AND by 3. 150 is not divisible by 9 since the sum of the digits is 6, and 6 is not divisible by 9. 150 is divisible by 10 since the last digit is 0. Solution: 150 is divisible by 2, 3, 5, 6, and 10.

Example 2: Determine whether 225 is divisible by 2, 3, 4, 5, 6, 9 and 10. 225 is not divisible by 2 since the last digit is not 0, 2, 4, 6 or 8. 225 is divisible by 3 since the sum of the digits is 9, and 9 is divisible by 3. 225 is not divisible by 4 since 25 is not divisible by 4. 225 is divisible by 5 since the last digit is 5. 225 is not divisible by 6 since it is not divisible by both 2 and 3. 225 is divisible by 9 since the sum of the digits is 9, and 9 is divisible by 9. 225 is not divisible by 10 since the last digit is not 0. Solution: 225 is divisible by 3, 5 and 9.

Example 3: Determine whether 7,168 is divisible by 2, 3, 4, 5, 6, 8, 9 and 10. 7,168 is divisible by 2 since the last digit is 8.

7,168 is not divisible by 3 since the sum of the digits is 22, and 22 is not divisible by 3. 7,168 is divisible by 4 since 168 is divisible by 4. 7,168 is not divisible by 5 since the last digit is not 0 or 5. 7,168 is not divisible by 6 since it is not divisible by both 2 and 3. 7,168 is divisible by 8 since the last 3 digits are 168, and 168 is divisible by 8. 7,168 is not divisible by 9 since the sum of the digits is 22, and 22 is not divisible by 9. 7,168 is not divisible by 10 since the last digit is not 0 or 5. Solution: 7,168 is divisible by 2, 4 and 8.

Example 4: Determine whether 9,042 is divisible by 2, 3, 4, 5, 6, 8, 9 and 10. 9,042 is divisible by 2 since the last digit is 2. 9,042 is divisible by 3 since the sum of the digits is 15, and 15 is divisible by 3. 9,042 is not divisible by 4 since 42 is not divisible by 4. 9,042 is not divisible by 5 since the last digit is not 0 or 5. 9,042 is divisible by 6 since it is divisible by both 2 and 3. 9,042 is not divisible by 8 since the last 3 digits are 042, and 42 is not divisible by 8. 9,042 is not divisible by 9 since the sum of the digits is 15, and 15 is not divisible by 9. 9,042 is not divisible by 10 since the last digit is not 0 or 5. Solution: 9,042 is divisible by 2, 3 and 6.

Example 5: Determine whether 35,120 is divisible by 2, 3, 4, 5, 6, 8, 9 and 10. 35,120 is divisible by 2 since the last digit is 0. 35,120 is not divisible by 3 since the sum of the digits is 11, and 11 is not divisible by 3. 35,120 is divisible by 4 since 20 is divisible by 4. 35,120 is divisible by 5 since the last digit is 0. 35,120 is not divisible by 6 since it is not divisible by both 2 and 3. 35,120 is divisible by 8 since the last 3 digits are 120, and 120 is divisible by 8. 35,120 is not divisible by 9 since the sum of the digits is 11, and 11 is not divisible by 9. 35,120 is divisible by 10 since the last digit is 0. Solution: 35,120 is divisible by 2, 4, 5, 8 and 10.

Example 6: Is the number 91 prime or composite? Use divisibility when possible to find your answer. 91 is not divisible by 2 since the last digit is not 0, 2, 4, 6 or 8. 91 is not divisible by 3 since the sum of the digits (9+1=10) is not divisible by 3.

91 is not evenly divisible by 4 (remainder is 3). 91 is not divisible by 5 since the last digit is not 0 or 5. 91 is not divisible by 6 since it is not divisible by both 2 and 3. 91 divided by 7 is 13. Solution: The number 91 is divisible by 1, 7, 13 and 91. Therefore 91 is composite since it has more than two factors.

Summary: Divisibility tests can be used to find factors of large whole numbers quickly, and thus determine if they are prime or composite. When working with large whole numbers, tests for divisibility are more efficient than the traditional factoring method.

Problem
Mr. Jones has eight children of different ages. On a family trip his oldest child, who is 9, spots a license plate with a 4-digit number in which each of two digits appears two times. "Look, daddy!" she exclaims. "That number is evenly divisible by the age of each of us kids!" "That's right," replies Mr. Jones, "and the last two digits just happen to be my age." Which of the following is not the age of one of Mr. Jones's children?

Solution
Let be the set of the ages of Mr. Jones' children (in other words years old). Then and or . Let if Mr. Jones has

a child who is

be the positive integer seen , we have .

on the license plate. Since at least one of We would like to prove that that . Then

is contained in

, so for the sake of contradiction, let us suppose so the units digit of is . Since the number has two must be . Since Mr. Jones can't must be of the form ,

distinct digits, each appearing twice, another digit of be where by years old, the last two digits can't be is a digit. Since

. Therefore

is divisible by , the sum of the digits of which implies . But

must be divisible is not

(see Divisibility rules for 9). Hence and

divisible by , contradiction. So

is not the age of one of Mr. Jones' kids. . If is

(We might like to check that there does, indeed, exist such a positive integer

not an age of one of Mr. Jones' kids, then the license plate number must be a multiple of . Since and is the only digit

multiple of

that fits all the conditions of the license plate's number, the license .)

plate's number is

Q The number 10^30 is divisible by all of the following EXCEPT a) 250 b) 125 c) 32 d) 16 e) 6 The number 10^30 is divisible by all of the following EXCEPT a) 250 b) 125 c) 32 d) 16 e) 6 break 10^30 as 2^29*(2*5^3)*(5^27) clearly divisible by 250 hence also by 125, also divisible by 2^5 = 32 hence also by 16 not divisible by 3 hence also not divisible by 6 bcos to be divisible by 6, it has to be divisible by both 2 &3