Prime Numbers Wiki
Register
(Remove pictures)
Tag: rte-source
(Make room)
Tag: rte-source
Line 6: Line 6:
   
 
Let's look at some divisibility rules:
 
Let's look at some divisibility rules:
= 1-20 =
+
== 1-20 ==
==Divisibility Rules 1-10==
 
   
 
===Divisibility by 1===
 
===Divisibility by 1===
Line 156: Line 155:
   
 
158375209580 is divisible by 10 because the last digit is 0.
 
158375209580 is divisible by 10 because the last digit is 0.
 
==Divisibility Rules 11-20==
 
   
 
===Divisibility by 11===
 
===Divisibility by 11===
Line 229: Line 226:
 
|
 
|
 
|}
 
|}
= Beyond 20 =
+
== Beyond 20 ==
 
== Divisibility Rules 21-30 ==
 
   
 
=== Divisibility by 21 ===
 
=== Divisibility by 21 ===
Line 242: Line 237:
   
 
To check if a number is divisible by 29, do the same as with 19 except when you take off the last digit, triple it rather than double it. This trick works with every number ending in 9. For 39 multiply it by 4, for 49 multiply it by 5, for 59 multiply it by 6 and so on.
 
To check if a number is divisible by 29, do the same as with 19 except when you take off the last digit, triple it rather than double it. This trick works with every number ending in 9. For 39 multiply it by 4, for 49 multiply it by 5, for 59 multiply it by 6 and so on.
 
== Divisibility Rules 31-40 ==
 
   
 
=== Divisibility by 32 ===
 
=== Divisibility by 32 ===

Revision as of 14:43, 8 May 2015

Please note that the divisibility rule 7 is tentative.   There is technically no shortcut.

-3primetime3-

Divisibility rules are shorthand ways of division to tell if one number is divisible or not.  They help tell whether the specific number you are looking for is prime or not. The many divisibililty rules help many mathematicians and geniuses determine prime numbers, even if the number is beyond big.

Let's look at some divisibility rules:

1-20

Divisibility by 1

Every number is divisible by one.  Example: 4623 is divisible by one, and even the greatest prime integer is greater than one.

Proof:

There is no need for a proof here.  Any number is divisible by one.  This rule does not apply to differentiate prime from consecutive numbers.

Divisibility by 2

Every number apart from 0 which ends with 0, 2, 4, 6 or 8 is divisible by two.  Example:

65156151594 is divisible by two because the units digit is 4, and 1597534568852 is divisible by two because the units digit is 2.

Proof:

We have a base-10 number system so that when a number gets to 8 and we add two, it carries over and the last digit is 0 (because 8+2=10). Now the cycle repeats (0+2=2, 2+2=4, 4+2=6, 6+2=8) and we continue carrying over forever.

Fun Fact:

The number two is the only even and prime number that can be divided by two.

Divisibility by 3

There are two divisibility rules to see if numbers are divisible by three.

  • A number is divisible by 3 if the sum of its digits is divisible by 3.
  • If a number is a multiplication of 3 consecutive numbers then that number is always divisible by 3. In other words, if a number can be expressed in the form (x-1)(x)(x+1), then it is divisible by three.

Example:

Is 12423 divisible by 3?

  1. Add all the digits together, we get 1 + 2 + 4 + 2 + 3 = 12.
  2. 12 is divisible by 3, so 12423 is, too.

Proof:

This method works for divisors that are factors of 10 − 1 = 9.

First of all, 9 = 10 − 1, which means 10 ≡ 1 mod 3. Now, if we are able to raise everything to the nth power, then we get 10n≡ 1n≡1 (mod 3).  Since two things that are congruent modulo 3 are either both divisible by 3 or both not, we can interchange values that are congruent modulo 3. So, in a number such as the following, we can replace all the powers of 10 by 1. Afterwards, the equation gives us: 

100*a + 10*b + 1c ≡ 1a + 1b + 1c (mod 3), which is exactly the sum of the digits.

Divisibility by 4

A number is divisible by four if and only if its last two digits fo the number are divisible by four.

Example:

156128 is divisible by four, and 6416 is divisible by four. The last two digits are 28 and 16, respectively, both of which are divisible by 4.

Proof:

Since any number divisible by 4 that is divided by 4 has a remainder of 0, we can write the following, using that number as 100, let's say:

100≡ 0 (mod 4), 10k ≡ let's 0 (mod 4) for k=2, 3, 4 etc...

x ≡ a0 + a1 (10) + a2(0) + ... + ak0 (mod 4) ≡ a0 + a1 (10) mod 4

Therefore, x is divisible by 4 if and only if the number is divisible by 4 where a0 + a1 (10) mod 4 is the number formed by the last two digits of x.

Divisibility by 5

A number is divisible by 5 if and only if the last digit is a 0 or 5.

Proof:

Let's say that every number ending in 0 or 5 is not divisible by five. Let's take the equation: y=5x where x is any integer constant.  Therefore, the value 5x ends with 0 or 5, since 5 multiplied by an integer constant ends with 0 or 5.   Dividing both sides by five, we get y/5 = x, an integer constant.  Therefore, even if we take the limit when x approaches infinity, we still get an integer constant.  This contradicts the given that every number ending in 0 or 5 is not divisible by 5.

Divisibility by 6

[ Because its prime factorization is 2 x 3, it should be divisible by those two numbers.

Example:

Is 4,044 divisible by 6?

  1. 4,044 is even, so it is divisible by 2.
  2. 4 + 4 + 4 is 12, so it is divisible by 3.
  3. Therefore, 4,044 is indeed a multiple of 6.

Divisibility by 7

There are two ways to check if the number is divisible by 7. The former one is tentative and a lot easier to apply, while the latter is more complicated and require some calculations. 

There is no shortcut for testing divisibility of this particular number, unfortunately. Both methods require a pencil and a piece of paper, as it cannot be determined at a simple glance. 

Method 1

The first method is to take the last digit of the number, multiply it by two, then subtract it to the remaining digits of the number. Repeat the process until the result can be easily identified.

Proof:

Every number can be expressed in the form , where y is the units digit. We are trying to prove that if is divisible by 7, then is also divisible by 7.

If is divisible by 7, we can write: , where p is a natural number. Multiply both sides by 10:

Add 21y to both sides:

Since is divisible by 7, we have concluded that is divisible by 7 if is divisible by 7.

Example:

Is 3409 is divisible by 7?

  1. Take 9 from 3409.
  2. Multiply 9 by 2 (9*2=18)
  3. Subtract the doubled digit to the remaining number (340-18=322)
  4. Repeat the progress, this time take 2 from 322.
  5. Multiply 2 by 2 (2*2=4)
  6. Subtract the doubled digit to the remaining number (32-4=28)
  7. 28 is divisible by 7, so 3409 is divisible by 7. (The real answer is 487)

Method 2 (advanced)

Sort the numbers in blocks of three. Then, add the first group from the right, subtract the second group, then add the third, subtract the fourth, and so on. This is called alternating sum. If the result number is the multiple of 7, then the number is divisible by 7. [1]

Example:

Is 1702906247 divisible by 7?

  1. Group the numbers into blocks of three: 247, 906, 702, 1
  2. Form the alternating sum: 247 - 906 + 702 - 1 = 42
  3. Since 42 = 7 * 6, 42 is divisible by 7, thus 1702906247 is, too.

Divisibility by 8

It is very simple, check whether the last three digits of the number is divisible by 8, if it is, then the number is divisible by 8.

Examples:

A. Is the number 7,377,473,496 divisible by 8?

  1. Take the last three digits of the number.
  2. The last three digit is 496, so check whether it is divisible by 8.
  3. 496 is divisible by 8, So the number 7,377,473,496 is divisible by 8.

B. Is the number 546,632,318 divisible by 8?

  1. The last three digit is 318.
  2. However, 318 is not divisible by 8, so the number 546632318 is not divisible by 8.[2]

Divisibility by 9

Add all the digits together. The only step different is to check if it is the multiple of 9 instead of 3.

Example:

Is 14625 divisible by 9?

  1. Add all the digits together: 1 + 4 + 6 + 2 + 5 = 18
  2. 18 is divisible by 9, so 14625 is, too.

Proof:

9 = 10 − 1, which means 10 ≡ 1 mod 9. Any number which is one less than an integer power of ten is divisible by 9. This can be proved by expressing each number in this group as a term in the sequence Tn=T(n-1)*9+9. If T(n-1) is divisible by 9, Tn will be also. The first term in this sequence is 0 (10^0-1) which is divisible. Therefore, if each digit of a number is expressed as its actual place value as a sum of terms where a is the first digit, b is the second, etc. it is congruent to the sum of the digits as shown:

1000a + 100b + 10c + 1d ≡ (1000-999)a + (100-99)b + (10-9)c (1-0)d ≡ a+b+c+d mod 9, which is the sum of the digits.

Divisibility by 10

If the last digit of the number is 0, it is divisible by 10.

Example:

158375209580 is divisible by 10 because the last digit is 0.

Divisibility by 11

Check the number, if the difference of sum of digits at odd places and sum of digits at even places is 0 or divisible by 11, then the number is divisible by 11.

Example: Is 527901 divisible by 11?

  1. First, check the number.
  2. Add the digits at odd places (in this case, 5+7+0=12)
  3. Add the digits at even places (in this case, 2+9+1=12)
  4. Subtract the sum of digits at odd places and sum of digits at even places (12-12=0)
  5. The result is 0, so 527901 is divisible by 11. (The real answer is 47991)

Divisibility by 12

Because its prime factorization is 2^2 x 3, it needs to be divisible by 4 and 3.

Example:

Is 9,180 divisible by 12?

  1. 9,180 ends in 80 (4*20), so it is divisible by 4.
  2. 9 + 1 + 8 + 0 is 18, so it is divisible by 3.
  3. Therefore, 9,180 is a multiple of 12.

Divisibility by 13

There is no shortcut for testing divisibility of this particular number, either.

Method 1

The first method is to take the last digit of the number, multiply it by four, then add it to the remaining digits of the numbers. Repeat the process until the result can be easily identified. This is similar to divisibility of 7.

Example:

Take 85969 for example.

  1. Take out 9 from 85969.
  2. Multiply if by four. (9 x 4 = 36)
  3. Add it to the remaining digits. (8596 + 36 = 8632)
  4. Take out 2 from 8632 and multiply it by four. (2 x 4 = 8)
  5. Add it to the remaining digits. (863 + 8 = 871)
  6. Take out 1 from 871 and multiply it by four. (1 x 4 = 4)
  7. Add it to the remaining digits. (87 + 4 = 91)
  8. 91 is divisible by 13, so 85969 is also divisible by 13.

Method 2

The second method, also similar to divisibility of 7, is use the alternating sums. After sorting the numbers in blocks of three, add the first group from the right, subtract the second group, then add the third, subtract the fourth, and so on. At last, check if the result is the multiple of 13 (If needed, use Method 1 to further reduce down a 3-digit number).

Example:

  1. Take 3,692,513,279 for example,
  2. After that, use Method 1 to determine if 455 is a multiple of 13.
  3. Take out 5 from 455 and multiply it by 4. (5 x 4 = 20)
  4. Add it to the remaining digits. (45 + 20 = 65)

65 is divisible by 13. Therefore, 3,692,513,279 is also divisible by 13.

Divisibility by 14

As 14 is the product of 2 and 7, perform divisibility checks of both 2 and 7.

Divisibiltiy by 15

Check if the number is divisible by 3 and 5.

Divisibility by 16

Same as divisibility by 8, except check if the last 4 digits are divisible by 16 rather than the last 3.

Divisibility by 18

Check if the number is divisible by 2 and 9.

Divisibility by 19

To check if a number is divisible by 19, take off the last digit and double it. Add it to the remaining digits. If that number is divisible by 19, so is the original number.

Example:

209. Take off the last digit (9) and double it (18). Add 18 to the remaining digits (20) to get 38. You can do the process again. Take off the last digit (8) and double it (16). Add 16 to the remaining digits (3) to get 19. 209 is divisible by 19.

Divisibility by 20

If the last digit of the number is 0 and the tens place is even, it's divisible by 20.

Beyond 20

Divisibility by 21

Method 1

21 ends in 1, so you can take the last digit, multiply it by 2, and subtract it from the remaining digits of the number just like 7.

Method 2

Do the test for 3 and the test for 7. It the number is divisible by both, it's divisible by 21.

Divisibility by 29

To check if a number is divisible by 29, do the same as with 19 except when you take off the last digit, triple it rather than double it. This trick works with every number ending in 9. For 39 multiply it by 4, for 49 multiply it by 5, for 59 multiply it by 6 and so on.

Divisibility by 32

Do the same as with 16, but check that the last 5 digits are divisible by 3 rather than the last 4.

Divisibility by 39

Method 1

39 ends in 9, so you can do the test for 29 but this time multiply the last digit by 4 rather than 3.

Method 2

Do the test for 13 and the test for 3. If they both turn out positive, then the original number is divisible by 39.

References