Sideway
output.to from Sideway
Number Theory

NumberPrime NumberFactorization


Draft for Information Only

Content

Divisibility
  Divisibility Test
  Divisibility Test for a Numberr a Number

Divisibility

The divisibility of a positive number by an integer divisor can be determined by some divisibility rule. The divisibility rules are usually a test to test the digits of a number without performing the division directly.

Divisibility Test

A base 10 number, a, can be expressed in terms of digits ai, that is

image

 Some standard divisibility tests are as following

  1. Testing of Ending Digit Block

    A base 10 number can also be expressed as the sum of two parts. If the number  a is divided by a divisor, d, the divisor, d, must divides both parts. In other words, for a divisor dividing the power of ten, the divisor divides the given number if and only if the divisor divides the ending digits.

    image

    For example,

    image

    Therefore, this is the divisibility test for numbers by number with prime factor 2 and 5.

  2. Testing of the Sum of Digit Blocks

    Instead of expressing a base 10 number as the sum of two parts, a base 10 number can also be expressed in forms of parts of fixed size digit blocks. By deducting the sum of digit blocks from the given number, the coefficients of remaining digit blocks become a repeated pattern of digit 9. If the number a is divided by a divisor, d, the divisor, d, must divides  the sum of digit blocks and all parts of fixed size digit blocks. In other words, for a divisor dividing the power of ten minus 1, the divisor divides the given number if and only if the divisor divides the sum of digit blocks.

    image

    For example,

    image

    Therefore, this is the divisibility test for numbers by number with prime factor of a digit block with dight 9s, i.e. 9, 99, 999,....

  3. Testing of the Alternating Sum of Digit Blocks

    Similar to testing of the sum of digit blocks, a base 10 number can be expressed in forms of parts of fixed size digit blocks. Instead of refering to the digit block of "9...9", a digit block of the form "10...01". The relation can be determined by modular arithmetic. By using modular arithmetic, the coefficients of digit blocks become an alternating sum of digit blocks. If a number a is divided by the divisor, d, the divisor, d, must divide  the alternating sum of digit blocks also. In other words, for a divisor dividing the power of ten plus 1, the divisor divides the given number if and only if the divisor divides the alternating sum of digit blocks.

    image

    The same relation can also be determined algebrically as in testing of the sum of digit blocks. The coefficient of all negative terms are always divided by the first coefficient 10i+1, i.e. 10i+1|10i+2x+1. Besides, The coefficient of all positive terms are also always divided by the first coefficient 10i+1, i.e. 10i+1|10i+2x+1-1. 

    For example,

    image
  4. Eliminate from the right digit block

    Instead of testing the ending digit block, the ending digit block can also be eliminated by reducing  the coefficient of the front digit block from the powers of ten to 1 so as to reduce the given number by a digit block from the right.

    image

    The same relation can also be determined using modular arithmetic. The integer multipler u is expressed as an inverse of 10i modulo d. 

    image

    For example,

    image
  5. Eliminate from the left digit block

    Similar to eliminating from the right dight block, the beginning digit block can also be eliminated by reducing the coefficient of the front digit block by powers of ten so as to reduce the given number by a digit block from the left.

    image

    The integer multipler u can also be determined algebrically

    image

    For example,

    image
  6. Factor the Divisor

    For a composite divisor, the divisibility tests for each prime factor of the composite divisor can be used to test  the given numebr one by one seperately.

Divisibility Test for a Numberr a Number

The divisibility of an integer number for some integers can be examined by some rules:

  • 2 - number with the last digit is even

  • 3 - number with the sum of digits is divisible by 3

  • 4 - number with the number of the last two digits is divisible by 4 

  • 5 - number with the  last digit is 5 or 0

  • 6 - number is divisible by both 2 and 3

  • 7 - number with the number without the last digit minus the double of the last digit is equal to 0 or divisible by 7

  • 8 - number with the number of the last three digits is divisible by 8

  • 9 - number with the sum of digits is divisible by 9

  • 10 - number with the last digit is 0

  • 11 - number with the sum of every second digit minus the sum of other digits is equal to 0 or divisible by 11

  • 12 - number is divisible by both 3 and 4

  • 25 - number with the number of the last two digit is 00, 25, 50, or 75


©sideway

ID: 160300002 Last Updated: 2/3/2016 Revision: 0 Ref:

close

References

  1. R. Paulo, 1996, The New Book of Prime Number Records
  2. Wolstenholme, R.J., 1862, On Certain Properties of Prime Numbers
  3. Mann, H.B., Shanks D., 1972, A Necessary and Sufficient Condition for Primality, and Its Source
  4. J.M Pollard, Kangaroos, 1975, A Monte Carlo Method for Factorization
close
IMAGE

Home 5

Business

Management

HBR 3

Information

Recreation

Hobbies 8

Culture

Chinese 1097

English 337

Reference 67

Computer

Hardware 149

Software

Application 198

Digitization 105

Numeric 19

Programming

Web 283

Unicode 494

HTML 65

CSS 58

ASP.NET 66

OS 389

DeskTop 7

Python 17

Knowledge

Mathematics

Formulas 8

Algebra 25

Number Theory 206

Trigonometry 18

Geometry 18

Calculus 67

Complex Analysis 21

Engineering

Tables 8

Mechanical

Mechanics 1

Rigid Bodies

Statics 92

Dynamics 37

Fluid 5

Fluid Kinematics 5

Control

Process Control 1

Acoustics 19

FiniteElement 2

Physics

Electric 27

Biology 1

Geography 1


Copyright © 2000-2020 Sideway . All rights reserved Disclaimers last modified on 06 September 2019