Scribd
Upload
24 views2 pages

Division Algorithm

The Division Algorithm states that for any integers a > 0 and b, there exist unique integers q and r such that b = aq + r, where 0 ≤ r < a. The proof involves constructing a set of non-negative integers and applying the Well-Ordering Principle to show the existence and uniqueness of r. The proof concludes that if two pairs (q1, r1) and (q2, r2) satisfy the conditions, then q1 must equal q2 and r1 must equal r2, proving uniqueness.

Uploaded by

mubasharraza2003
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
24 views2 pages

Division Algorithm

The Division Algorithm states that for any integers a > 0 and b, there exist unique integers q and r such that b = aq + r, where 0 ≤ r < a. The proof involves constructing a set of non-negative integers and applying the Well-Ordering Principle to show the existence and uniqueness of r. The proof concludes that if two pairs (q1, r1) and (q2, r2) satisfy the conditions, then q1 must equal q2 and r1 must equal r2, proving uniqueness.

Uploaded by

mubasharraza2003
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Division Algorithm (Statement)

Let a , b ∈ Z with a> 0. Then there exist unique integers q ,r ∈ Z .such that
b=aq+ r . where 0≤ r < a

Proof (using Well-Ordering Principle)


Step 1: Construct the set
Define the set
A={ b−ax ∣ x ∈ Z , b−ax ≥ 0 }
This set contains all non-negative integers of the form b−ax .

Step 2: Show that A ≠ ∅ .(A is not empty)


We must prove that at least one element exists in A .

Choose

x=−∣ b ∣

Since a> 0, multiply both sides by a :

−ax =a ∣b ∣≥ ∣b ∣ ≥−b

−ax ≥−b Therefore, b−ax ≥ 0

So this value belongs to A .


Hence,
A≠∅

Step 3: Apply Well-Ordering Principle


Since A is a non-empty set of non-negative integers, by the Well-Ordering Principle, A has a
smallest element.
Call this smallest element r .
So there exists some integer q such that
r =b−aq
Rearrange:
b=aq+ r
This proves the required form.

Step 4: Show that 0 ≤ r <a From definition of A , r≥0


Now we prove that r < a. Suppose, for contradiction,
r≥a Then r −a ≥ 0

Let r 1=r−a .Then. r 1 <r

But
r =b−aq
So
r 1=r−a=b−aq−a ¿ b−a( q+1)
This is of the form b−ax and is non-negative.
So
b−a (q+1)∈ A

This contradicts the fact that r is the smallest element of A .


Therefore,
r<a
Thus,
0 ≤ r <a Part: Proof of Uniqueness

Suppose there are two pairs of integers ( q 1 ,r 1 )and ( q 2 ,r 2 ) that satisfy the conditions:

1. b=a q 1+ r 1where 0 ≤ r 1 <a


2. b=a q 2+ r 2where 0 ≤ r 2 <a

Step 1: Set the equations equal


Since both expressions are equal to b , we can write:

a q 1+ r 1=a q 2 +r 2

Step 2: Rearrange terms


a q 1−a q 2=r 2 −r 1
a (q1 −q2 )=r 2−r 1

a∨(q1−q2 )∨¿ ¿ r 2−r 1 ∨… … …(1)

But 0 ≤ ¿ r 2−r 1|< a Hence 0 ≤ a|( q 1−q 2 )|<a implies 0≤|( q1−q2 )|<1
q 1−q 2=0 so q 1=q 2 Hece from (1 ) r 2=r 1

You might also like