Divisibility

Divisibility Rules

  • 2n, 5n, and 10n - Check if the last n digits are divisible.
  • 3 and 9 - Check if digital sum is divisible.
  • 6 - Check if number is divisible by both 2 and 3.
  • 7 - Subtract twice the last digit from the remaining number and check divisibility again. Another method is triplet method (make triplets from right and do alternate +/- and check the result for divisibility by 7 again… this is useful for very large numbers).
  • 11 - If, sum of all digits at odd position - sum of all digits at even position is 0, then number is divisible by 11.
  • 12 - Check if number is divisible by both 3 and 4 .

Forming Divisibility Rules

Composites - A number is divisible by a given divisor if it is divisible by the highest power of each of its prime factors. For example, to determine divisibility by 36, check divisibility by 4 and by 9. Note that checking 3 and 12, or 2 and 18, would not be sufficient.

Primes - We can form divisibility rules for primes >=13 by the following method.

Suppose we want to find divisibility rule for 13, then we form equation as: 3x + 1 = 13, solving for x gives us x = 4 and we must multiply x with unit digit and sum to the remaining number and check divisibility again by 13.

Suppose we want to find divisibility rule for 17, then we form equation as: 7x + 1 = 17, solving for x gives us x = 16/7 (floor of it is 2) and we must multiply x with unit digit and subtract from the remaining number and check divisibility again by 17.

Programming Problems and Solutions

  • Sum of all numbers divisible by n in range [L-R] - Sum all till R, and sum all till L-1 and subtract to get sum between [L-R].

Link

//Formula

sum = n + 2n + 3n + 4n + 5n ...

sum => n (1 + 2 + 3 + 4 + 5 ...)

sum => (n/2) * (n(n+1)/2) 

sumR = (n / 2) * (R/n) * ((R/n)+1)

sumL as (n / 2) * ((L-1)/n) * ((L-1/n)+1)

References

  1. https://en.wikipedia.org/wiki/Divisibility_rule
  2. D!NG - Divisibility Rules
  3. Brilliant Wiki
    i. Divisibility Rules
    ii. Proof Of Divisibility Rules