OpenCart Templates
Saturday , July 22 2017
Home / Elementary Number Theory / Divisibility theory in integers

Divisibility theory in integers

Theorem: Given integers a and b, with b > 0, there exists unique integers q and r satisfying a = qb + r, 0 ≤ r < b.

The integers q and r are called, respectively the quotient and remainder in the division of a by b.

Proof: We begin by proving that the set S = {a – xb\x is an integer; a – xb ≥ 0} is non empty.

For this, it suffices to exhibit a value x making a – xb non negative. Since the integer b ≥ 1. We have |a|b ≥ |a| and so a – (-|a|)b = a + |a| b ≥ a + |a| ≥ 0.

Hence for the choice x = -|a|, a – xb lies in S. This paves the way for application of the well ordering principle, from which we inter that the set S contains a smallest integer, call it r.

But the definition of S, there exists an integer q satisfying r = a – qb , 0 ≤ r.

We argue that r < b

If this were not the case, then r ≥ b and a – (q +1)b = (a – qb) – b = r – b ≥ 0.

The implication is that the integer a – (q + 1)b has the proper from to belongs to the set S.

But a – (q + 1) = a – qb – b = r – b < r

Leading to a contradiction of the choice of r as the smallest number of S.

Hence r < b

We next form to the task of showing the uniqueness of q and r. Suppose that a has two representation of desired form; say a = qb + r = q′b + r′

Where 0 ≤ r <b, 0 ≤ r′ < b. Then r′-r = b(q – q′) and owing to the fact that the absolute value of a product is equal to the product of the absolute values

|r′-r| = b|q-q′|

Upon adding the two inequalities –b < -r ≤ 0 and 0 ≤ r′ < b. We obtain

–b < r′-r ≤ 0, or in equivalent terms. |r′ – r|<b. Thus b|q –q′|<b, which yields 0 ≤|q-q′| < 1.

Since |q – q′| is a non-negative integer, the only possibility is is that

|q – q′| = 0 implies that q – q′ = 0. i.e., q = q′

This in its form gives r = r′, ending the proof.

Check Also

Application of Euclidian’s algorithm in Diophantine equation

Problem-1: Which of the following Diophantine equations cannot be solved –   a) 6x + ...

Leave a Reply

Your email address will not be published. Required fields are marked *