No edit summary Tag: rte-source |
No edit summary Tag: rte-source |
||
Line 2: | Line 2: | ||
Let's look at some divisibility rules: |
Let's look at some divisibility rules: |
||
+ | {| class="collapsible" style="margin:6px auto; width:100%; background:transparent; border:2px solid #AAA; padding:5px;" |
||
− | |||
+ | ! style="text-align:left;" | <h2 style="border:none;">Basic Rules</h2> |
||
− | ==Basic Rules== |
||
+ | |- |
||
+ | | |
||
The following rules are elementary checks: |
The following rules are elementary checks: |
||
− | + | <big> Divisibility by 1 </big> |
|
+ | |||
[[File:1.png|thumb|Divisibility Rule 1|100px]] |
[[File:1.png|thumb|Divisibility Rule 1|100px]] |
||
Line 14: | Line 17: | ||
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. |
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. |
||
− | + | <big>Examining the last ''n'' digits</big> |
|
+ | |||
[[File:Ending Digit.png|thumb|230px|right|Examining the last '''n''' digits]] |
[[File:Ending Digit.png|thumb|230px|right|Examining the last '''n''' digits]] |
||
Simply examine the last n digits if the divisor can divide 10<sup>n</sup> with no remainder. |
Simply examine the last n digits if the divisor can divide 10<sup>n</sup> with no remainder. |
||
Line 54: | Line 58: | ||
Due to this, a is divisible by '''d''' if and only if the last n digits of a is divisible by '''d'''.<ref>http://webspace.ship.edu/msrenault/divisibility/StupidDivisibilityTricks.pdf</ref> |
Due to this, a is divisible by '''d''' if and only if the last n digits of a is divisible by '''d'''.<ref>http://webspace.ship.edu/msrenault/divisibility/StupidDivisibilityTricks.pdf</ref> |
||
− | + | <big>Adding blocks of digits</big> |
|
+ | |||
[[File:Digit Sum.png|thumb|300px|right|Digit sum]] |
[[File:Digit Sum.png|thumb|300px|right|Digit sum]] |
||
Starting from the right to left, sum up all the digits in blocks of ''n'' digits. This works for the following numbers: |
Starting from the right to left, sum up all the digits in blocks of ''n'' digits. This works for the following numbers: |
||
Line 71: | Line 76: | ||
:*'''101''': Add up the digits in groups of four from right to left and check if the number is divisible by 37. |
:*'''101''': Add up the digits in groups of four from right to left and check if the number is divisible by 37. |
||
− | + | <big> Alternating Sum </big> |
|
+ | |||
[[File:Alt Sum.png|thumb|300px|right|Alt sum]] |
[[File:Alt Sum.png|thumb|300px|right|Alt sum]] |
||
First, sort the numbers in groups of ''n'' digits from right to left. Alternate between adding and subtracting them. In other words, after adding the first group, continue subtracting the second group, adding the third group, subtracting the fourth group, adding the fifth group, and so on. This is called the alternating sum.<ref>http://mathforum.org/k12/mathtips/ward2.html</ref> This works for the following numbers: |
First, sort the numbers in groups of ''n'' digits from right to left. Alternate between adding and subtracting them. In other words, after adding the first group, continue subtracting the second group, adding the third group, subtracting the fourth group, adding the fifth group, and so on. This is called the alternating sum.<ref>http://mathforum.org/k12/mathtips/ward2.html</ref> This works for the following numbers: |
||
Line 88: | Line 94: | ||
'''Note:''' A. With the 3-digit digit sum method, if the result is still not easy to determine, the "right trim method" below can be used to further examine it. |
'''Note:''' A. With the 3-digit digit sum method, if the result is still not easy to determine, the "right trim method" below can be used to further examine it. |
||
+ | |} |
||
+ | |||
+ | {| class="collapsible" style="margin:6px auto; width:100%; background:transparent; border:2px solid #AAA; padding:5px;" |
||
+ | ! style="text-align:left;" | <h2 style="border:none;">Advanced rules</h2> |
||
+ | |- |
||
+ | | |
||
⚫ | |||
− | ==Advanced Rules== |
||
⚫ | |||
For the number '''a''' to test divisibility by '''d''', take off the last digit, multiply it by '''x''', and then add it to all of the remaining digits on the left. |
For the number '''a''' to test divisibility by '''d''', take off the last digit, multiply it by '''x''', and then add it to all of the remaining digits on the left. |
||
Line 121: | Line 132: | ||
#91 is divisible by 13, so 85969 is also divisible by 13. |
#91 is divisible by 13, so 85969 is also divisible by 13. |
||
− | + | <big> Full list below 101 </big> |
|
+ | |||
Any inverse of 10 modulo '''d''' or 100 modulo '''d''' will work, thus there are two methods for the former, and two methods for the latter to do the trimming. The method can be applied to the following numbers: |
Any inverse of 10 modulo '''d''' or 100 modulo '''d''' will work, thus there are two methods for the former, and two methods for the latter to do the trimming. The method can be applied to the following numbers: |
||
Line 285: | Line 297: | ||
{{Divisibility Table End}} |
{{Divisibility Table End}} |
||
− | + | <big> Left trim </big> |
|
+ | |||
[[File:LT ex.png|thumb|130px|right|Left Trim example]] |
[[File:LT ex.png|thumb|130px|right|Left Trim example]] |
||
The trick is that, if 100 divided by the number '''d''' has a remainder of '''h''', then the leftmost digit can be removed, multiplied by '''h''', shifted '''two places''' to the right, and be added from there. It can be described as the following equation: |
The trick is that, if 100 divided by the number '''d''' has a remainder of '''h''', then the leftmost digit can be removed, multiplied by '''h''', shifted '''two places''' to the right, and be added from there. It can be described as the following equation: |
||
Line 429: | Line 442: | ||
{{Divisibility Table B2|35|5, 7 |57|3, 19 |80|5, 16 |100|4, 25 }} |
{{Divisibility Table B2|35|5, 7 |57|3, 19 |80|5, 16 |100|4, 25 }} |
||
{{Divisibility Table End}} |
{{Divisibility Table End}} |
||
+ | |} |
||
− | |||
+ | {| class="collapsible" style="margin:6px auto; width:100%; background:transparent; border:2px solid #AAA; padding:5px;" |
||
− | ==References== |
||
+ | ! style="text-align:left;" | <h2 style="border:none;">References</h2> |
||
+ | |- |
||
+ | | |
||
<references /> |
<references /> |
||
+ | |} |
||
[[Category:Important Pages]] |
[[Category:Important Pages]] |
Revision as of 20:07, 6 September 2015
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 divisibility rules help many mathematicians and geniuses determine prime numbers, even if the number is beyond big.
Let's look at some divisibility rules:
Basic Rules |
---|
The following rules are elementary checks: Divisibility by 1 Every integer is divisible by one. Example: 1289 is divisible by one, and 14461 is divisible by one. Proof: Examining the last n digits Simply examine the last n digits if the divisor can divide 10n with no remainder. As such:
Proof:
Due to this, a is divisible by d if and only if the last n digits of a is divisible by d.[2] Adding blocks of digits Starting from the right to left, sum up all the digits in blocks of n digits. This works for the following numbers:
Alternating Sum First, sort the numbers in groups of n digits from right to left. Alternate between adding and subtracting them. In other words, after adding the first group, continue subtracting the second group, adding the third group, subtracting the fourth group, adding the fifth group, and so on. This is called the alternating sum.[3] This works for the following numbers:
Note: A. With the 3-digit digit sum method, if the result is still not easy to determine, the "right trim method" below can be used to further examine it. |
Advanced rules | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Right trim For the number a to test divisibility by d, take off the last digit, multiply it by x, and then add it to all of the remaining digits on the left. By the elementary number theory results, if the greatest common divisor of d and 10 is 1 (i.e. the number d has the last digit of 1, 3, 7, or 9), there will be a number x that can allow . The term for this sort of number is named inverse of 10 modulo d, and it can be written as . This would allow the number to be trimmed from the right by 1 digit, multiplied by x, and then be added to the remaining digits. Similarly, there also exist a number that can allow , and it can be written as . The number would then be able to be trimmed, multiplied by x, and then be added to the remaining digits. Examples: Since 10x2 ≡ -1 (mod 7), we can take out the last digit, multiply it by 2, and then subtract it from the remaining digits. Therefore:
Since 10x4 ≡ 1 (mod 13), we can take out the last digit, multiply it by 4, and then add it to the remaining digits. Therefore:
Full list below 101 Any inverse of 10 modulo d or 100 modulo d will work, thus there are two methods for the former, and two methods for the latter to do the trimming. The method can be applied to the following numbers:
Left trim The trick is that, if 100 divided by the number d has a remainder of h, then the leftmost digit can be removed, multiplied by h, shifted two places to the right, and be added from there. It can be described as the following equation:
The same can be applied for the number 10 divided by d having a remainder h, with the same method applied to shift the leftmost digit one place to the right, and then be added from there:
Below is a list of numbers where this method can be applied. Only notable numbers will be listed here.
Combining methodsThis is done by testing a number's divisibility of 2 or more numbers if the divisor is a composite number that is not a square, cubic, quadratic number, etc. Suppose that d = mn where m and n are relatively prime. When the above statement is true, the number a is divisible by d if and only if d is divisible by m and d is divisible by n. For example, a number is divisible by 63 if and only if 63 is divisible by both 7 and 9. Below is a list of numbers that can apply this method: |
References |
---|