Sideway
output.to from Sideway
Number Theory


Factorization



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
close

References

  1. R. Paulo, 1996, The New Book of Prime Number Records, Springer-Verlag, New York
  2. Wolstenholme, R.J., 1862, On Certain Properties of Prime Numbers, The Quarterly Journal of Pure and Applied Mathematics, Vol 5, p35-39, London
  3. Mann, H.B., Shanks D., 1972, A Necessary and Sufficient Condition for Primality, and Its Source, Journal of Combinatorial Theory, 13, p131-134
  4. J.M Pollard, Kangaroos, 1975, A Monte Carlo Method for Factorization, BIT 15 (1975), 331-334
close

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

IMAGE

Home (5)

Business

Management

HBR (3)

Information

Recreation

Hobbies (7)

Culture

Chinese (1097)

English (336)

Reference (66)

Computer

Hardware (149)

Software

Application (187)

Digitization (24)

Numeric (19)

Programming

Web (618)new

CSS (SC)

ASP.NET (SC)

HTML

Knowledge Base

Common Color (SC)

Html Entity (Unicode) (SC)

Html 401 Special (SC)

OS (388)new

MS Windows

Windows10 (SC)

.NET Framework (SC)

DeskTop (7)

Knowledge

Mathematics

Formulas (8)

Number Theory (206)

Algebra (20)

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)

Biology (1)

Geography (1)


Copyright © 2000-2019 Sideway . All rights reserved Disclaimers last modified on 10 Feb 2019