Divisibility - Revision history

Khanh: /* Divisibility rules for numbers 1–30 */

2021-12-11T21:51:08Z

Divisibility rules for numbers 1–30

Khanh at 21:49, 11 December 2021

2021-12-11T21:49:55Z

Khanh: /* Generalized divisibility rule */

2021-12-11T21:47:36Z

Generalized divisibility rule

Khanh: /* Proofs */

2021-12-11T21:45:30Z

Proofs

Khanh: /* Beyond 30 */

2021-12-11T21:43:51Z

Beyond 30

Show changes

Khanh: /* Step-by-step examples */

2021-12-11T21:24:41Z

Step-by-step examples

Khanh: /* Divisibility rules for numbers 1–30 */

2021-12-11T21:11:28Z

Divisibility rules for numbers 1–30

Khanh: Created page with "A '''divisibility rule''' is a shorthand and useful way of determining whether a given integer is divisible by a fixed divisor without performing the division, usually by exam..."

2021-12-11T21:00:54Z

Created page with "A '''divisibility rule''' is a shorthand and useful way of determining whether a given integer is divisible by a fixed divisor without performing the division, usually by exam..."

Show changes

@@ Line 93: / Line 93: @@
 |-
 |id=9| '''9'''
-| Sum the digits.  The result must be divisible by 9.<ref name="Pascal's-criterion"/><ref name="apostol-1976"/><ref name="Richmond-Richmond-2009"/>
+| Sum the digits.  The result must be divisible by 9.
 | 2880: 2 + 8 + 8 + 0 = 18: 1 + 8 = 9.
 |-

@@ Line 899: / Line 899: @@
 |-
 |'''125'''
-|The number formed by the last three digits must be divisible by 125.<ref name="last-m-digits"/>
+|The number formed by the last three digits must be divisible by 125.
 |2,125: 125 is divisible by 125.
 |-
@@ Line 907: / Line 907: @@
 |-
 |'''128'''
-|The number formed by the last seven digits must be divisible by 128.<ref name="Pascal's-criterion"/><ref name="last-m-digits"/>
+|The number formed by the last seven digits must be divisible by 128.
 |-
 |'''131'''
@@ Line 1,019: / Line 1,019: @@
 |-
 |'''250'''
-|The number formed by the last three digits must be divisible by 250.<ref name="Pascal's-criterion"/><ref name="last-m-digits"/>
+|The number formed by the last three digits must be divisible by 250.
 |1,327,750: 750 is divisible by 250.
 |-
@@ Line 1,027: / Line 1,027: @@
 |-
 |'''256'''
-|The number formed by the last eight digits must be divisible by 256.<ref name="Pascal's-criterion"/><ref name="last-m-digits"/>
+|The number formed by the last eight digits must be divisible by 256.
 |-
 |'''257'''
@@ Line 1,100: / Line 1,100: @@
 |-
 |'''512'''
-|The number formed by the last nine digits must be divisible by 512.<ref name="Pascal's-criterion"/><ref name="last-m-digits"/>
+|The number formed by the last nine digits must be divisible by 512.
 |-
 |'''625'''
@@ Line 1,269: / Line 1,269: @@
 so ''x'' is divisible by 7 if and only if ''y'' − 2''z'' is divisible by 7.

@@ Line 1,151: / Line 1,151: @@
 ==Generalized divisibility rule==
-To test for divisibility by ''D'', where ''D'' ends in 1, 3, 7, or 9, the following method can be used.<ref>Dunkels, Andrejs, "Comments on note 82.53—a generalized test for divisibility", ''[[Mathematical Gazette]]'' 84, March 2000, 79-81.</ref> Find any multiple of ''D'' ending in 9. (If ''D'' ends respectively in 1, 3, 7, or 9, then multiply by 9, 3, 7, or 1.) Then add 1 and divide by 10, denoting the result as ''m''. Then a number ''N'' = 10''t'' + ''q'' is divisible by ''D'' if and only if ''mq + t'' is divisible by ''D''. If the number is too large, you can also break it down into several strings with ''e'' digits each, satisfying either 10<sup>''e''</sup> = 1 or 10<sup>''e''</sup> = -1 (mod ''D''). The sum (or alternate sum) of the numbers have the same divisibility as the original one.
+To test for divisibility by ''D'', where ''D'' ends in 1, 3, 7, or 9, the following method can be used. Find any multiple of ''D'' ending in 9. (If ''D'' ends respectively in 1, 3, 7, or 9, then multiply by 9, 3, 7, or 1.) Then add 1 and divide by 10, denoting the result as ''m''. Then a number ''N'' = 10''t'' + ''q'' is divisible by ''D'' if and only if ''mq + t'' is divisible by ''D''. If the number is too large, you can also break it down into several strings with ''e'' digits each, satisfying either 10<sup>''e''</sup> = 1 or 10<sup>''e''</sup> = -1 (mod ''D''). The sum (or alternate sum) of the numbers have the same divisibility as the original one.
 For example, to determine if 913 = 10×91 + 3 is divisible by 11, find that ''m'' = (11×9+1)÷10 = 10. Then ''mq+t'' = 10×3+91 = 121; this is divisible by 11 (with quotient 11), so 913 is also divisible by 11. As another example, to determine if 689 = 10×68 + 9 is divisible by 53, find that ''m'' = (53×3+1)÷10 = 16. Then ''mq+t'' = 16×9 + 68 = 212, which is divisible by 53 (with quotient 4); so 689 is also divisible by 53.
@@ Line 1,158: / Line 1,158: @@
 <math>D(n) \equiv \begin{cases} 9a+1, & \mbox{if }n\mbox{ = 10a+1} \\ 3a+1, & \mbox{if }n\mbox{ = 10a+3} \\ 7a+5, & \mbox{if }n\mbox{ = 10a+7} \\ a+1, & \mbox{if }n\mbox{ = 10a+9}\end{cases} \ </math>
-The first few terms of the sequence, generated by D(n) are 1, 1, 5, 1, 10, 4, 12, 2, ... (sequence  [http://oeis.org/A333448 A333448] in [[OEIS]]).
+The first few terms of the sequence, generated by D(n) are 1, 1, 5, 1, 10, 4, 12, 2, ... (sequence  [http://oeis.org/A333448 A333448] in OEIS).
-The piece wise form of D(n) and the sequence generated by it were first published by Bulgarian mathematician Ivan Stoykov in March 2020. <ref name="auto">{{cite journal|last1=Stoykov|first1=Ivan|date=March 2020|title=OEIS A333448|url=http://oeis.org/A333448|journal=OEIS A333448}}</ref>
+The piece wise form of D(n) and the sequence generated by it were first published by Bulgarian mathematician Ivan Stoykov in March 2020.
 ==Proofs==

@@ Line 1,166: / Line 1,166: @@
 ===Proof using basic algebra===
-Many of the simpler rules can be produced using only algebraic manipulation, creating [[binomial (polynomial)|binomial]]s and rearranging them.  By writing a number as the [[positional notation|sum of each digit times a power of 10]] each digit's power can be manipulated individually.
+Many of the simpler rules can be produced using only algebraic manipulation, creating binomials and rearranging them.  By writing a number as the sum of each digit times a power of 10 each digit's power can be manipulated individually.
 '''Case where all digits are summed'''
@@ Line 1,172: / Line 1,172: @@
 This method works for divisors that are factors of 10&nbsp;−&nbsp;1 = 9.
-Using 3 as an example, 3 divides 9&nbsp;=&nbsp;10&nbsp;−&nbsp;1. That means <math>10 \equiv 1 \pmod{3}</math> (see [[modular arithmetic]]). The same for all the higher powers of 10: <math>10^n \equiv 1^n \equiv 1 \pmod{3}</math>  They are all [[congruence relation|congruent]] to 1 modulo 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:
+Using 3 as an example, 3 divides 9&nbsp;=&nbsp;10&nbsp;−&nbsp;1. That means <math>10 \equiv 1 \pmod{3}</math> (see modular arithmetic). The same for all the higher powers of 10: <math>10^n \equiv 1^n \equiv 1 \pmod{3}</math>  They are all congruent to 1 modulo 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:
 :<math>100\cdot a + 10\cdot b + 1\cdot c \equiv (1)a + (1)b + (1)c \pmod{3}</math>
@@ Line 1,246: / Line 1,246: @@
 ===Proof using modular arithmetic===
-This section will illustrate the basic method; all the rules can be derived following the same procedure. The following requires a basic grounding in [[modular arithmetic]]; for divisibility other than by 2's and 5's the proofs rest on the basic fact that 10 mod ''m'' is invertible if 10 and ''m'' are relatively prime.
+This section will illustrate the basic method; all the rules can be derived following the same procedure. The following requires a basic grounding in modular arithmetic; for divisibility other than by 2's and 5's the proofs rest on the basic fact that 10 mod ''m'' is invertible if 10 and ''m'' are relatively prime.
 '''For 2<sup>''n''</sup> or 5<sup>''n''</sup>:'''

@@ Line 269: / Line 269: @@
 First, take any number (for this example it will be 492) and add together each digit in the number (4 + 9 + 2 = 15). Then take that sum (15) and determine if it is divisible by 3. The original number is divisible by 3 (or 9) if and only if the sum of its digits is divisible by 3 (or 9).
-Adding the digits of a number up, and then repeating the process with the result until only one digit remains, will give the [[remainder]] of the original number if it were divided by nine (unless that single digit is nine itself, in which case the number is divisible by nine and the remainder is zero).
+Adding the digits of a number up, and then repeating the process with the result until only one digit remains, will give the remainder of the original number if it were divided by nine (unless that single digit is nine itself, in which case the number is divisible by nine and the remainder is zero).
-This can be generalized to any [[List of numeral systems#Standard positional numeral systems|standard positional system]], in which the divisor in question then becomes one less than the [[radix]]; thus, in [[duodecimal|base-twelve]], the digits will add up to the remainder of the original number if divided by eleven, and numbers are divisible by eleven only if the digit sum is divisible by eleven.
+This can be generalized to any standard positional system, in which the divisor in question then becomes one less than the radix; thus, in base-twelve, the digits will add up to the remainder of the original number if divided by eleven, and numbers are divisible by eleven only if the digit sum is divisible by eleven.
 The product of three consecutive numbers is always divisible by 3. This is useful for when a number takes the form of ''n'' × (''n'' − 1) × (''n'' + 1).
@@ Line 289: / Line 289: @@
 ===Divisibility by 4===
-The basic rule for divisibility by 4 is that if the number formed by the last two digits in a number is divisible by 4, the original number is divisible by 4;<ref name="Pascal's-criterion"/><ref name="last-m-digits"/> this is because 100 is divisible by 4 and so adding hundreds, thousands, etc. is simply adding another number that is divisible by 4.  If any number ends in a two digit number that you know is divisible by 4 (e.g. 24, 04, 08, etc.), then the whole number will be divisible by 4 regardless of what is before the last two digits.
+The basic rule for divisibility by 4 is that if the number formed by the last two digits in a number is divisible by 4, the original number is divisible by 4; this is because 100 is divisible by 4 and so adding hundreds, thousands, etc. is simply adding another number that is divisible by 4.  If any number ends in a two digit number that you know is divisible by 4 (e.g. 24, 04, 08, etc.), then the whole number will be divisible by 4 regardless of what is before the last two digits.
 Alternatively, one can simply divide the number by 2, and then check the result to find if it is divisible by 2.  If it is, the original number is divisible by 4.  In addition, the result of this test is the same as the original number divided by 4.
@@ Line 307: / Line 307: @@
 ===Divisibility by 5===
-Divisibility by 5 is easily determined by checking the last digit in the number (47'''5'''), and seeing if it is either 0 or 5.  If the last number is either 0 or 5, the entire number is divisible by 5.<ref name="Pascal's-criterion"/><ref name="last-m-digits"/>
+Divisibility by 5 is easily determined by checking the last digit in the number (47'''5'''), and seeing if it is either 0 or 5.  If the last number is either 0 or 5, the entire number is divisible by 5.
 If the last digit in the number is 0, then the result will be the remaining digits multiplied by 2.  For example, the number 40 ends in a zero, so take the remaining digits (4) and multiply that by two (4 × 2 = 8).  The result is the same as the result of 40 divided by 5(40/5 = 8).
@@ Line 330: / Line 330: @@
 ===Divisibility by 6===
-Divisibility by 6 is determined by checking the original number to see if it is both an even number ([[#Divisibility by 2|divisible by 2]]) and [[#Divisibility by 3|divisible by 3]].<ref name="product-of-coprimes"/> This is the best test to use.
+Divisibility by 6 is determined by checking the original number to see if it is both an even number (divisible by 2) and divisible by 3. This is the best test to use.
 If the number is divisible by six, take the original number (246) and divide it by two (246 ÷ 2 = 123).  Then, take that result and divide it by three (123 ÷ 3 = 41).  This result is the same as the original number divided by six (246 ÷ 6 = 41).
@@ Line 364: / Line 364: @@
 Divisibility by 7 can be tested by a recursive method. A number of the form 10''x''&nbsp;+&nbsp;''y'' is divisible by 7 if and only if ''x''&nbsp;−&nbsp;2''y'' is divisible by 7.  In other words, subtract twice the last digit from the number formed by the remaining digits.  Continue to do this until a number is obtained for which it is known whether it is divisible by 7.  The original number is divisible by 7 if and only if the number obtained using this procedure is divisible by 7.  For example, the number 371: 37&nbsp;−&nbsp;(2×1) =&nbsp;37&nbsp;−&nbsp;2&nbsp;=&nbsp;35; 3&nbsp;−&nbsp;(2&nbsp;×&nbsp;5) =&nbsp;3&nbsp;−&nbsp;10 =&nbsp;−7; thus, since −7 is divisible by 7, 371 is divisible by&nbsp;7.
-Similarly a number of the form 10''x''&nbsp;+&nbsp;''y'' is divisible by 7 if and only if ''x''&nbsp;+&nbsp;5''y'' is divisible by 7. So add five times the last digit to the number formed by the remaining digits, and continue to do this until a number is obtained for which it is known whether it is divisible by 7.<ref name="7Divis">{{Cite web|date=2019-09-20|title=Chika's Test|url=https://www.westminsterunder.org.uk/chikas-test/|access-date=2021-03-17|website=Westminster Under School|language=en-GB}}</ref>
+Similarly a number of the form 10''x''&nbsp;+&nbsp;''y'' is divisible by 7 if and only if ''x''&nbsp;+&nbsp;5''y'' is divisible by 7. So add five times the last digit to the number formed by the remaining digits, and continue to do this until a number is obtained for which it is known whether it is divisible by 7.
 Another method is multiplication by 3. A number of the form 10''x''&nbsp;+&nbsp;''y'' has the same remainder when divided by 7 as 3''x''&nbsp;+&nbsp;''y''. One must multiply the leftmost digit of the original number by 3, add the next digit, take the remainder when divided by 7, and continue from the beginning: multiply by 3, add the next digit, etc. For example, the number 371: 3×3 + 7 = 16 remainder 2, and 2×3 + 1 = 7. This method can be used to find the remainder of division by 7.
-A more complicated algorithm for testing divisibility by 7 uses the fact that 10<sup>0</sup>&nbsp;≡&nbsp;1, 10<sup>1</sup>&nbsp;≡&nbsp;3, 10<sup>2</sup>&nbsp;≡&nbsp;2, 10<sup>3</sup>&nbsp;≡&nbsp;6, 10<sup>4</sup>&nbsp;≡&nbsp;4, 10<sup>5</sup>&nbsp;≡&nbsp;5, 10<sup>6</sup>&nbsp;≡&nbsp;1, ...&nbsp;(mod&nbsp;7). Take each digit of the number (371) in reverse order (173), multiplying them successively by the digits '''1''', '''3''', '''2''', '''6''', '''4''', '''5''', repeating with this sequence of multipliers as long as necessary (1, 3, 2, 6, 4, 5, 1, 3, 2, 6, 4, 5, ...), and adding the products (1×'''1'''&nbsp;+&nbsp;7×'''3'''&nbsp;+&nbsp;3×'''2''' =&nbsp;1&nbsp;+&nbsp;21&nbsp;+&nbsp;6&nbsp;=&nbsp;28). The original number is divisible by 7 if and only if the number obtained using this procedure is divisible by 7 (hence 371 is divisible by 7 since 28 is).<ref name="7Divis1">{{cite web
+A more complicated algorithm for testing divisibility by 7 uses the fact that 10<sup>0</sup>&nbsp;≡&nbsp;1, 10<sup>1</sup>&nbsp;≡&nbsp;3, 10<sup>2</sup>&nbsp;≡&nbsp;2, 10<sup>3</sup>&nbsp;≡&nbsp;6, 10<sup>4</sup>&nbsp;≡&nbsp;4, 10<sup>5</sup>&nbsp;≡&nbsp;5, 10<sup>6</sup>&nbsp;≡&nbsp;1, ...&nbsp;(mod&nbsp;7). Take each digit of the number (371) in reverse order (173), multiplying them successively by the digits '''1''', '''3''', '''2''', '''6''', '''4''', '''5''', repeating with this sequence of multipliers as long as necessary (1, 3, 2, 6, 4, 5, 1, 3, 2, 6, 4, 5, ...), and adding the products (1×'''1'''&nbsp;+&nbsp;7×'''3'''&nbsp;+&nbsp;3×'''2''' =&nbsp;1&nbsp;+&nbsp;21&nbsp;+&nbsp;6&nbsp;=&nbsp;28). The original number is divisible by 7 if and only if the number obtained using this procedure is divisible by 7 (hence 371 is divisible by 7 since 28 is).
 This method can be simplified by removing the need to multiply. All it would take with this simplification is to memorize the sequence above (132645...), and to add and subtract, but always working with one-digit numbers.
@@ Line 385: / Line 380: @@
 *If at any point the first digit is 8 or 9, these become 1 or 2, respectively. But if it is a 7 it should become 0, only if no other digits follow. Otherwise, it should simply be dropped. This is because that 7 would have become 0, and numbers with at least two digits before the decimal dot do not begin with 0, which is useless. According to this, our 7 becomes&nbsp;'''0'''.
-If through this procedure you obtain a '''0''' or any recognizable multiple of 7, then the original number is a multiple of 7. If you obtain any number from '''1''' to '''6''', that will indicate how much you should subtract from the original number to get a multiple of&nbsp;7. In other words, you will find the [[remainder]] of dividing the number by 7. For example, take the number&nbsp;'''186''':
+If through this procedure you obtain a '''0''' or any recognizable multiple of 7, then the original number is a multiple of 7. If you obtain any number from '''1''' to '''6''', that will indicate how much you should subtract from the original number to get a multiple of&nbsp;7. In other words, you will find the remainder of dividing the number by 7. For example, take the number&nbsp;'''186''':
 *First, change the 8 into a 1: '''116'''.
 *Now, change 1 into the following digit in the sequence (3), add it to the second digit, and write the result instead of both: 3&nbsp;+&nbsp;1&nbsp;=&nbsp;''4''. So ''11''6 becomes now '''''4''6'''.
@@ Line 412: / Line 407: @@
 '''Vedic method of divisibility by osculation'''<br>
-Divisibility by seven can be tested by multiplication by the ''Ekhādika''. Convert the divisor seven to the nines family by multiplying by seven. 7×7=49. Add one, drop the units digit and, take the 5, the ''Ekhādika'', as the multiplier. Start on the right. Multiply by 5, add the product to the next digit to the left. Set down that result on a line below that digit. Repeat that method of multiplying the units digit by five and adding that product to the number of tens. Add the result to the next digit to the left. Write down that result below the digit. Continue to the end. If the end result is zero or a multiple of seven, then yes, the number is divisible by seven. Otherwise, it is not. This follows the Vedic ideal, one-line notation.<ref>Page 274, '''Vedic Mathematics: Sixteen Simple Mathematical Formulae''', by Swami Sankaracarya, published by Motilal Banarsidass, Varanasi, India, 1965, Delhi, 1978. 367 pages.</ref>{{unreliable source?|date=March 2016}}
+Divisibility by seven can be tested by multiplication by the ''Ekhādika''. Convert the divisor seven to the nines family by multiplying by seven. 7×7=49. Add one, drop the units digit and, take the 5, the ''Ekhādika'', as the multiplier. Start on the right. Multiply by 5, add the product to the next digit to the left. Set down that result on a line below that digit. Repeat that method of multiplying the units digit by five and adding that product to the number of tens. Add the result to the next digit to the left. Write down that result below the digit. Continue to the end. If the end result is zero or a multiple of seven, then yes, the number is divisible by seven. Otherwise, it is not. This follows the Vedic ideal, one-line notation.
 '''Vedic method example:'''

@@ Line 196: / Line 196: @@
 | 480: it is divisible by 4 and 5.
 |-
-| id=21 rowspan=2|'''[[21 (number)|21]]'''
+| id=21 rowspan=2|'''21'''
 |Subtracting twice the last digit from the rest gives a multiple of 21.
 |168: 16 − 8 × 2 = 0.
 |-
-|It is divisible by 3 and by 7.<ref name="product-of-coprimes"/>
+|It is divisible by 3 and by 7.
 |231: it is divisible by 3 and by 7.
 |-
-|id=22| '''[[22 (number)|22]]'''
+|id=22| '''22'''
-|It is divisible by 2 and by 11.<ref name="product-of-coprimes"/>
+|It is divisible by 2 and by 11.
 |352: it is divisible by 2 and by 11.
 |-
-|id=23 rowspan=2| '''[[23 (number)|23]]'''
+|id=23 rowspan=2| '''23'''
 |Add 7 times the last digit to the rest.
 |3128: 312 + 8 × 7 = 368.  36 + 8 × 7 = 92.
@@ Line 214: / Line 214: @@
 |1725: 17 + 25 × 3 = 92.
 |-
-|id=24| '''[[24 (number)|24]]'''
+|id=24| '''24'''
-|It is divisible by 3 and by 8.<ref name="product-of-coprimes"/>
+|It is divisible by 3 and by 8.
 |552: it is divisible by 3 and by 8.
 |-
-|id=25| '''[[25 (number)|25]]'''
+|id=25| '''25'''
 |If the last two digits are 00, 25, 50 or 75.
 |134,250: 50 is divisible by 25.
 |-
-|id=26 rowspan=2| '''[[26 (number)|26]]'''
+|id=26 rowspan=2| '''26'''
-|It is divisible by 2 and by 13.<ref name="product-of-coprimes"/>
+|It is divisible by 2 and by 13.
 |156: it is divisible by 2 and by 13.
 |-
@@ Line 229: / Line 229: @@
 |1248 : (124 ×2) - (8×5) =208=26×8
 |-
-| rowspan="3" id="27" |'''[[27 (number)|27]]'''
+| rowspan="3" id="27" |'''27'''
 |Sum the digits in blocks of three from right to left.
 |2,644,272:  2 + 644 + 272 = 918.
@@ Line 239: / Line 239: @@
 |6507: 65 × 8 - 7 = 520 - 7 = 513 = 27 × 19.
 |-
-|id=28| '''[[28 (number)|28]]'''
+|id=28| '''28'''
-|It is divisible by 4 and by 7.<ref name="product-of-coprimes"/>
+|It is divisible by 4 and by 7.
 |140: it is divisible by 4 and by 7.
 |-
-| rowspan="2" id="29" | '''[[29 (number)|29]]'''
+| rowspan="2" id="29" | '''29'''
 |Add three times the last digit to the rest.
 |348: 34 + 8 × 3 = 58.
@@ Line 250: / Line 250: @@
 |5510: 55 + 10 × 9 = 145 = 5 × 29.
 |-
-|id=30| '''[[30 (number)|30]]'''
+|id=30| '''30'''
-|It is divisible by 3 and by 10.<ref name="product-of-coprimes"/>
+|It is divisible by 3 and by 10.
 |270: it is divisible by 3 and by 10.
 |}