Divisibility Rules

    Take any two integers, you can add them, subtract them, and multiply them; and the result will be an integer. So we say that the set of integers is closed under addition, subtraction, and multiplication.  However, the integers are not closed for division as are the rational numbers. For example, if we choose 7 and 2 then their ratio is not an integer. The point is, as far as the set of integers is concerned, there is no closure for division. So we will study this phenomena more closely by defining the concept of a divisor.  

(1) Definition (Divisibility) If and are integers with we say that is a divisor of written if there exists an integer such that If is a divisor of then we also say that divides is a factor of and that is a multiple of

(2) Example (Divisibility) Determine which of the following is true, or

    Solution. There are no integers with so we write and say 3 does not divide 817. Since there is an integer, namely such that and so we write and we say divides 88, or we might say is a divisor of 88.   

(3) Example (Divisibility) Fill in the blanks, determining a non-trivial divisor of the given integer.

    The concept of divisibility will be the main theme in a course in elementary number theory. Additional topics to be covered later can (and will) be defined in terms of divisibility. So here are some basic properties of divisibility that every reader should be able to prove for themselves after thoroughly understanding the definition of divisibility.  

(4) Proposition (Properties of Divisibility) Assume that and are integers.

    (i) If and then
    
    (ii) If and   then for any integers and
    
    (iii) If and then
    
    (iv) If and then
    
    (v) If then for any positive integer
    
(5) Proof. For part (i), suppose there exists and such that and Then and so
    For part (ii), suppose there exists integers and such that and Then for any integers and we have and so
    For part (iii), suppose there exists integers and such that and Then we have Thus, and so Whence,
    For part (iv), suppose there exists an integer such that Then, since and so
    For part (v), we will use mathematical induction. Since certainly implies the case for is trivial. Assume that holds, then there exists an integer such that Then where and are some integers. Whence,   as desired.  

(6) Proposition (Division Algorithm) If and are integers such that then there are unique integers and such that with The integers and are called the quotient and the remainder in the division of by

(7) Example (Division Algorithm) Find the quotient and remainder in the division algorithm given and   

    Solution. We use division in the real numbers (calculator) and take the integer part of So we have where Therefore, the quotient is and the remainder is

    Another tool for theorem proving involving the integers is the division algorithm. Most students are familiar with the statement of the division algorithm from simply performing long division in elementary school. However, the use of the division algorithm can be far more useful than just finding a quotient and remainder given two integers. How? The main use of the division algorithm is that it allows us to characterize the integers in term of a given integer. For example, say we are given by the division algorithm we can say every integer is exactly one of the forms or This is quiet useful, in fact in proving a statement concerning the integers we can break down the infinite set of integers into a finite number of cases. Here is a concrete example of this idea.

(8) Example (Division Algorithm) Show that the expression is an integer for any positive integer

    Solution. Equivalently, we need to show that is of the form for some for any positive integer By the division algorithm, has exactly one of the forms or
    If for some then



is an integer.  
    If for some then



is an integer.
    Finally, if is of the form then we have



which is an integer.
    Therefore, in all cases,   is an integer for any positive integer

(9) Example (Division Algorithm) Show that the product of any three consecutive integers is divisible by

    Solution. Let be an integer. We need to show that is of the form The division algorithm yields that is either even or odd (not both). In either case, must be even. The integer is also divisible by 3, since one of or is of the form Since is even and is divisible by 3, it must be divisible by 6.

    In the last example it seems like we used a property: for



Although this not a true statement, it does work for this example because the greatest common divisor between 2 and 3 is 1.  

Number Theory Books

A Beginner's Guide to Constructing the Universe: Mathematical Archetypes of N... List Price: $18.95 Buy New: $10.45 You Save: $8.50 (45%) New (37) Used (28) from $8.49The Universe May Be a Mystery,But It's No SecretMichael Schneider leads us on a spectacular, lavishly illustrated journey along the numbers one through ten to explore the mathematical principles made visible (more)

Bayesian Computation with R (Use R) List Price: $49.95 Buy New: $33.51 You Save: $16.44 (33%) New (32) Used (8) from $33.51There has been a dramatic growth in the development and application of Bayesian inferential methods. Some of this growth is due to the availability of powerful simulation-based algorithms to summarize (more)

e: The Story of a Number List Price: $19.95 Buy New: $8.23 You Save: $11.72 (59%) New (42) Used (32) Collectible (1) from $3.25The interest earned on a bank account, the arrangement of seeds in a sunflower, and the shape of the Gateway Arch in St. Louis are all intimately connected with the mysterious number e. In this informal (more)

Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathem... List Price: $16.00 Buy New: $8.91 You Save: $7.09 (44%) New (35) Used (15) from $7.49In 1859, Bernhard Riemann, a little-known thirty-two year old mathematician, made a hypothesis while presenting a paper to the Berlin Academy titled ?On the Number of Prime Numbers Less Than a Given Quantity.? (more)

Euler's Gem: The Polyhedron Formula and the Birth of Topology List Price: $27.95 Buy New: $17.00 You Save: $10.95 (39%) New (27) Used (3) from $14.99Leonhard Euler's polyhedron formula describes the structure of many objects--from soccer balls and gemstones to Buckminster Fuller's buildings and giant all-carbon molecules. Yet Euler's formula is so (more)

Dr. Euler's Fabulous Formula: Cures Many Mathematical Ills List Price: $29.95 Buy New: $17.98 You Save: $11.97 (40%) New (36) Used (10) from $17.98I used to think math was no fun'Cause I couldn't see how it was doneNow Euler's my heroFor I now see why zeroEquals e[pi] i+1--Paul Nahin, electrical engineer In the mid-eighteenth century, Swiss-born (more)

The Fabulous Fibonacci Numbers List Price: $28.98 Buy New: $15.00 You Save: $13.98 (48%) New (35) Used (11) Collectible (1) from $14.50The most ubiquitous, and perhaps the most intriguing, number pattern in mathematics is the Fibonacci sequence. In this simple pattern beginning with two ones, each succeeding number is the sum of the two (more)

Killer Poker By the Numbers: Mathematical Edge for Winning Play (Killer Poker) List Price: $14.95 Buy New: $7.69 You Save: $7.26 (49%) New (35) Used (13) from $7.69Killer Poker By the Numbers: Mathematical Edge for Winning Play (Killer Poker) (more)

Sacred Number: The Secret Quality of Quantities (Wooden Books) List Price: $12.00 Buy New: $5.59 You Save: $6.41 (53%) New (30) Used (13) from $5.59Numbers permeate every aspect of our lives; very little happens without a basic ability to manipulate the simple whole numbers we all take for granted. Beautifully illustrated with old engravings as well (more)

The Music of the Primes: Searching to Solve the Greatest Mystery in Mathematics List Price: $13.95 Buy Used: $0.98 You Save: $12.97 (93%) New (28) Used (29) from $0.98In 1859, German mathematician Bernhard Riemann presented a paper to the Berlin Academy that would forever change the history of mathematics. The subject was the mystery of prime numbers. At the heart of (more)

• print this page
• pages linking here
• related pages