Editing Divisibility rule (section)

===Divisibility by 7===
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.<ref>{{citation |url=https://www.jimloy.com/number/divis.htm |archive-url=https://web.archive.org/web/20071010143520/https://www.jimloy.com/number/divis.htm |archive-date=2007-10-10  |title=Divisibility Tests |first=Jim |last=Loy |date=1999 |quote=Multiply the right-most digit by 5 and add to the rest of the numbers. If this sum is divisible by 7, then the original number is divisible by 7.}}</ref> 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>{{citation |url=https://archive.org/details/penguindictionar0000well_f3y1/page/50/mode/2up?view=theater |title=The Penguin dictionary of curious and interesting numbers |first=David |last=Wells |pages=51 |date=1997|isbn=9780140261493 }}</ref>

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
| last      = Su
| first      = Francis E.
| title      = "Divisibility by Seven" ''Mudd Math Fun Facts''
| url      = http://www.math.hmc.edu/funfacts/ffiles/10005.5.shtml
| access-date      = 2006-12-12
| archive-date      = 2019-06-13
| archive-url      = https://web.archive.org/web/20190613183517/https://www.math.hmc.edu/funfacts/ffiles/10005.5.shtml
| url-status      = dead
}}</ref>

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.

The simplification goes as follows:
*Take for instance the number '''371'''
*Change all occurrences of '''7''', '''8''' or '''9''' into '''0''', '''1''' and '''2''', respectively. In this example, we get: '''301'''. This second step may be skipped, except for the left most digit, but following it may facilitate calculations later on.
*Now convert the first digit (3) into the following digit in the sequence '''13264513...''' In our example, 3 becomes '''2'''.
*Add the result in the previous step (2) to the second digit of the number, and substitute the result for both digits, leaving all remaining digits unmodified: 2&nbsp;+&nbsp;0&nbsp;=&nbsp;2. So ''30''1 becomes '''''2''1'''.
*Repeat the procedure until you have a recognizable multiple of 7, or to make sure, a number between 0 and 6. So, starting from 21 (which is a recognizable multiple of 7), take the first digit (2) and convert it into the following in the sequence above: 2 becomes 6. Then add this to the second digit: 6&nbsp;+&nbsp;1&nbsp;=&nbsp;'''7'''.
*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''':
*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'''.
*Repeat the procedure, since the number is greater than 7. Now, 4 becomes 5, which must be added to 6. That is&nbsp;'''11'''.
*Repeat the procedure one more time: 1 becomes 3, which is added to the second digit (1): 3&nbsp;+&nbsp;1&nbsp;=&nbsp;'''4'''.

Now we have a number smaller than 7, and this number (4) is the remainder of dividing 186/7. So 186&nbsp;minus&nbsp;4, which is 182, must be a multiple of&nbsp;7.

Note: The reason why this works is that if we have: '''a+b=c''' and '''b''' is a multiple of any given number '''n''', then '''a''' and '''c''' will necessarily produce the same remainder when divided by '''n'''. In other words, in 2&nbsp;+&nbsp;7&nbsp;=&nbsp;9, 7 is divisible by&nbsp;7. So 2 and 9 must have the same remainder when divided by 7. The remainder is&nbsp;2.

Therefore, if a number ''n'' is a multiple of 7 (i.e.: the remainder of ''n''/7 is&nbsp;0), then adding (or subtracting) multiples of 7 cannot change that property.

What this procedure does, as explained above for most divisibility rules,  is simply subtract little by little multiples of 7 from the original number until reaching a number that is small enough for us to remember whether it is a multiple of 7. If 1 becomes a 3 in the following decimal position, that is just the same as converting 10×10<sup>''n''</sup> into a 3×10<sup>''n''</sup>. And that is actually the same as subtracting 7×10<sup>''n''</sup> (clearly a multiple of 7) from 10×10<sup>''n''</sup>.

Similarly, when you turn a 3 into a 2 in the following decimal position, you are turning 30×10<sup>''n''</sup> into 2×10<sup>''n''</sup>, which is the same as subtracting 30×10<sup>''n''</sup>−28×10<sup>n</sup>, and this is again subtracting a multiple of 7. The same reason applies for all the remaining conversions:
* 20×10<sup>''n''</sup>&nbsp;−&nbsp;6×10<sup>''n''</sup>='''14'''×10<sup>''n''</sup>
* 60×10<sup>''n''</sup>&nbsp;−&nbsp;4×10<sup>''n''</sup>='''56'''×10<sup>''n''</sup>
* 40×10<sup>''n''</sup>&nbsp;−&nbsp;5×10<sup>''n''</sup>='''35'''×10<sup>''n''</sup>
* 50×10<sup>''n''</sup>&nbsp;−&nbsp;1×10<sup>''n''</sup>='''49'''×10<sup>''n''</sup>

'''First method example'''<br>
1050 → 105 − 0=105 → 10 − 10 = 0. ANSWER: 1050 is divisible by 7.

'''Second method example'''<br>
1050 → 0501 (reverse) → 0×'''1''' + 5×'''3''' + 0×'''2''' + 1×'''6''' = 0 + 15 + 0 + 6 = 21 (multiply and add). ANSWER: 1050 is divisible by 7.

'''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 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}}

'''Vedic method example:'''
 Is 438,722,025 divisible by seven?  Multiplier = 5.
  4  3  8  7  2  2  0  2  5
 42 37 46 37  6 40 37 27
 YES

'''Pohlman–Mass method of divisibility by 7'''<br>
The Pohlman–Mass method provides a quick solution that can determine if most integers are divisible by seven in three steps or less.  This method could be useful in a mathematics competition such as MATHCOUNTS, where time is a factor to determine the solution without a calculator in the Sprint Round.

Step A:
If the integer is 1000 or less, subtract twice the last digit from the number formed by the remaining digits.  If the result is a multiple of seven, then so is the original number (and vice versa).  For example:

 112 -> 11 − (2×2) = 11 − 4  =  7  YES
 98  -> 9  − (8×2) = 9  − 16 = −7  YES
 634 -> 63 − (4×2) = 63 − 8  = 55  NO

Because 1001 is divisible by seven, an interesting pattern develops for repeating sets of 1, 2, or 3 digits that form 6-digit numbers (leading zeros are allowed) in that all such numbers are divisible by seven.  For example:

 001 001 = 1,001 / 7 = 143
 010 010 = 10,010 / 7 = 1,430
 011 011 = 11,011 / 7 = 1,573
 100 100 = 100,100 / 7 = 14,300
 101 101 = 101,101 / 7 = 14,443
 110 110 = 110,110 / 7 = 15,730

 01 01 01 = 10,101 / 7 = 1,443
 10 10 10 = 101,010 / 7 = 14,430

 111,111 / 7 = 15,873
 222,222 / 7 = 31,746
 999,999 / 7 = 142,857

 576,576 / 7 = 82,368

For all of the above examples, subtracting the first three digits from the last three results in a multiple of seven.  Notice that leading zeros are permitted to form a 6-digit pattern.

This phenomenon forms the basis for Steps B and C.

Step B:
If the integer is between 1001 and one million, find a repeating pattern of 1, 2, or 3 digits that forms a 6-digit number that is close to the integer (leading zeros are allowed and can help you visualize the pattern).  If the positive difference is less than 1000, apply Step A.  This can be done by subtracting the first three digits from the last three digits.  For example:

 341,355 − 341,341 = 14 -> 1 − (4×2) = 1 − 8 = −7     YES
  67,326 − 067,067 = 259 -> 25 − (9×2) = 25 − 18 = 7  YES

The fact that 999,999 is a multiple of 7 can be used for determining divisibility of integers larger than one million by reducing the integer to a 6-digit number that can be determined using Step B.  This can be done easily by adding the digits left of the first six to the last six and follow with Step A.

Step C:
If the integer is larger than one million, subtract the nearest multiple of 999,999 and then apply Step B.  For even larger numbers, use larger sets such as 12-digits (999,999,999,999) and so on.  Then, break the integer into a smaller number that can be solved using Step B.  For example:

 22,862,420 − (999,999 × 22) = 22,862,420 − 21,999,978 -> 862,420 + 22 = 862,442
    862,442 -> 862 − 442 (Step B) = 420 -> 42 − (0×2) (Step A) = 42  YES

This allows adding and subtracting alternating sets of three digits to determine divisibility by seven.  Understanding these patterns allows you to quickly calculate divisibility of seven as seen in the following examples:

'''Pohlman–Mass method of divisibility by 7, examples:'''

 Is 98 divisible by seven?
 98  -> 9  − (8×2) = 9  − 16 = −7  YES  (Step A)

 Is 634 divisible by seven?
 634 -> 63 − (4×2) = 63 − 8  = 55  NO  (Step A)

 Is 355,341 divisible by seven?
 355,341 − 341,341 = 14,000 (Step B) -> 014 − 000 (Step B) -> 14 = 1 − (4×2) (Step A) = 1 − 8 = −7  YES

 Is 42,341,530 divisible by seven?
 42,341,530 -> 341,530 + 42 = 341,572 (Step C)
 341,572 − 341,341 = 231 (Step B)
 231 -> 23 − (1×2) = 23 − 2 = 21  YES (Step A)

 Using quick alternating additions and subtractions:
  42,341,530 -> 530 − 341 + 42 = 189 + 42 = 231 -> 23 − (1×2) = 21  YES

'''Multiplication by 3 method of divisibility by 7, examples:'''

 Is 98 divisible by seven?
 98  -> 9 remainder 2 -> 2×3 + 8 = 14 YES

 Is 634 divisible by seven?
 634 -> 6×3 + 3 = 21 -> remainder 0 -> 0×3 + 4 = 4 NO

 Is 355,341 divisible by seven?
 3 × 3 + 5 = 14 -> remainder 0 -> 0×3 + 5 = 5 -> 5×3 + 3 = 18 -> remainder 4 -> 4×3 + 4 = 16 -> remainder 2 -> 2×3 + 1 = 7 YES

 Find remainder of 1036125837 divided by 7
 1×3 + 0 = 3
 3×3 + 3 = 12 remainder 5
 5×3 + 6 = 21 remainder 0
 0×3 + 1 = 1
 1×3 + 2 = 5
 5×3 + 5 = 20 remainder 6
 6×3 + 8 = 26 remainder 5
 5×3 + 3 = 18 remainder 4
 4×3 + 7 = 19 remainder 5
 Answer is 5

'''Finding remainder of a number when divided by 7'''

7 − (1, 3, 2, −1, −3, −2, cycle repeats for the next six digits) Period: 6 digits.
Recurring numbers: 1, 3, 2, −1, −3, −2
<br>Minimum magnitude sequence <br>
(1, 3, 2, 6, 4, 5, cycle repeats for the next six digits) Period: 6 digits.
Recurring numbers: 1, 3, 2, 6, 4, 5
<br>Positive sequence

Multiply the right most digit by the left most digit in the sequence and multiply the second right most digit by the second left most digit in the sequence and so on and so for. Next, compute the sum of all the values and take the modulus of 7.
<br>Example: What is the remainder when 1036125837 is divided by 7? <br>
<br>Multiplication of the rightmost digit = 1 × 7 = 7 <br>
<br>Multiplication of the second rightmost digit = 3 × 3 = 9 <br>
<br>Third rightmost digit = 8 × 2 = 16 <br>
<br>Fourth rightmost digit = 5 × −1 = −5 <br>
<br>Fifth rightmost digit = 2 × −3 = −6 <br>
<br>Sixth rightmost digit = 1 × −2 = −2 <br>
<br>Seventh rightmost digit = 6 × 1 = 6 <br>
<br>Eighth rightmost digit = 3 × 3 = 9 <br>
<br>Ninth rightmost digit = 0 <br>
<br>Tenth rightmost digit = 1 × −1 = −1 <br>
<br>Sum = 33 <br>
<br>33 modulus 7 = 5 <br>
<br>Remainder = 5

'''Digit pair method of divisibility by 7'''

This method uses '''1''', '''−3''', '''2''' pattern on the ''digit pairs''. That is, the divisibility of any number by seven can be tested by first separating the number into digit pairs, and then applying the algorithm on three digit pairs (six digits). When the number is smaller than six digits, then fill zero's to the right side until there are six digits. When the number is larger than six digits, then repeat the cycle on the next six digit group and then add the results. Repeat the algorithm until the result is a small number. The original number is divisible by seven if and only if the number obtained using this algorithm is divisible by seven. This method is especially suitable for large numbers.

''Example 1:''<br>
The number to be tested is 157514.
First we separate the number into three digit pairs: 15, 75 and 14.<br>
Then we apply the algorithm: '''1''' × 15 '''− 3''' × 75 + '''2''' × 14 = 182<br>
Because the resulting 182 is less than six digits, we add zero's to the right side until it is six digits.<br>
Then we apply our algorithm again: '''1''' × 18 '''− 3''' × 20 + '''2''' × 0 = −42<br>
The result −42 is divisible by seven, thus the original number 157514 is divisible by seven.

''Example 2:''<br>
The number to be tested is 15751537186.<br>
('''1''' × 15 '''− 3''' × 75 + '''2''' × 15) + ('''1''' × 37 '''− 3''' × 18 + '''2''' × 60) = −180 + 103 = −77<br>
The result −77 is divisible by seven, thus the original number 15751537186 is divisible by seven.

'''Another digit pair method of divisibility by 7'''

'''Method'''

This is a non-recursive method to find the remainder left by a number on dividing by 7:

# Separate the number into digit pairs starting from the ones place. Prepend the number with 0 to complete the final pair if required.
# Calculate the remainders left by each digit pair on dividing by 7.
# Multiply the remainders with the appropriate multiplier from the sequence 1, 2, 4, 1, 2, 4, ... : the remainder from the digit pair consisting of ones place and tens place should be multiplied by 1, hundreds and thousands by 2, ten thousands and hundred thousands by 4, million and ten million again by 1 and so on.
# Calculate the remainders left by each product on dividing by 7.
# Add these remainders. 
# The remainder of the sum when divided by 7 is the remainder of the given number when divided by 7.

[[File:Example for digit pair divisibility test for 7.jpg|thumb|500x500px]]
For example:

The number 194,536 leaves a remainder of 6 on dividing by 7.

The number 510,517,813 leaves a remainder of 1 on dividing by 7.

'''Proof of correctness of the method'''

The method is based on the observation that 100 leaves a remainder of 2 when divided by 7. And since we are breaking the number into digit pairs we essentially have powers of 100.

1 mod 7 = 1

100 mod 7 = 2

10,000 mod 7 = 2^2 = 4

1,000,000 mod 7 = 2^3 = 8; 8 mod 7 = 1

100,000,000 mod 7 = 2^4 = 16; 16 mod 7 = 2

10,000,000,000 mod 7 = 2^5 = 32; 32 mod 7 = 4

And so on.

The correctness of the method is then established by the following chain of equalities:

Let N be the given number <math>\overline{a_{2n} a_{2n-1} ... a_2a_1}</math>.

<math>\overline{a_{2n}a_{2n-1}...a_2a_1}\mod 7</math>

<math>[\sum_{k=1}^n(a_{2k}a_{2k-1}) \times 10^{2k-2}] \bmod 7</math>

<math>\sum_{k=1}^n(a_{2k}a_{2k-1} \times 10^{2k-2}) \bmod 7</math>

<math>\sum_{k=1}^n(a_{2k}a_{2k-1} \bmod 7) \times (10^{2k-2} \bmod 7)</math>