PRINT LINKED RELATED

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.98 You Save: $7.97 (42%) New (31) Used (24) from $7.58The 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)

Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathem... List Price: $16.00 Buy New: $8.86 You Save: $7.14 (45%) New (38) Used (19) 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)

Bayesian Computation with R (Use R) List Price: $49.95 Buy New: $37.82 You Save: $12.13 (24%) New (35) Used (13) from $35.75There 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)

Euler's Gem: The Polyhedron Formula and the Birth of Topology List Price: $27.95 Buy New: $16.98 You Save: $10.97 (39%) New (32) Used (4) from $16.98Leonhard 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)

e: The Story of a Number List Price: $19.95 Buy Used: $2.94 You Save: $17.01 (85%) New (11) Used (38) Collectible (1) from $2.94The 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)

Not Even Wrong: The Failure of String Theory and the Search for Unity in Phys... List Price: $16.95 Buy New: $7.61 You Save: $9.34 (55%) New (34) Used (11) from $6.78When does physics depart the realm of testable hypothesis and come to resemble theology? Peter Woit argues that string theory isn't just going in the wrong direction, it's not even science. Not Even Wrong (more)

Killer Poker By the Numbers: Mathematical Edge for Winning Play List Price: $14.95 Buy New: $6.99 You Save: $7.96 (53%) New (34) Used (13) from $6.99Killer Poker By the Numbers: Mathematical Edge for Winning Play (more)

Elementary Number Theory (5th Edition) List Price: $124.00 Buy New: $99.20 You Save: $24.80 (20%) New (9) Used (17) from $79.05Elementary Number Theory and Its Applications is noted for its outstanding exercise sets, including basic exercises, exercises designed to help students explore key concepts, and challenging exercises. (more)

Complex Analysis for Mathematics and Engineering List Price: $124.95 Buy New: $48.99 You Save: $75.96 (61%) New (14) Used (15) from $47.90Revised and updated, the new Fifth Edition of Complex Analysis for Mathematics and Engineering presents a comprehensive, student-friendly introduction to Complex Analysis. It's clear, concise writing (more)

Dr. Euler's Fabulous Formula: Cures Many Mathematical Ills List Price: $29.95 Buy New: $14.74 You Save: $15.21 (51%) New (43) Used (15) from $14.49I 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)