Euclidean Algorithm - Number Theory #Euclidean #Algorithm #- #Number #Theory
Euclid Algorithm or Division Algorithm :
Statement :
Given integers a and b with b > 0 , there exists a unique pair of integers q and r such that
a = bq + r , with 0 ≤ r < b. Moreover , r = 0 if, and only, if b/a.
Proof :
Suppose a and b are two integers with b > 0.
Let S = { y / y= a - bx , x is an integer, y ≥ 0 } .
Clearly S is a non - empty set of non - negative integers.
∴ By well- ordering Principle , S must have a smallest member , say a - bq for some integer q .
Let r = a - bq.
Hence r is the smallest among all the members of S.
We have r = a - bq
=> a= bq + r and r ≥ 0.
Now we prove r < b.
In contrary, assume that r ≥ b.
r - b ≥ 0.
Also r - b < r.
Now r - b = ( a - bq ) - b
= a - bq - b
= a - ( q +1 ) b
r- b 𝟄 S.
∴ we have r - b 𝟄 S and r - b < r
Since r- b < r and r is the smallest member of S, we must have r - b is not in S.
This is a controdiction to r- b 𝟄 S.
∴ Our assumption is false.
∴ we have r < b.
Hence a = bq + r with 0 ≤ r < b.
Uniqueness of q and r :
If possible, suppose there exists q', r' such that a = bq' + r' with 0 ≤ r' < b
we have a = bq +r = bq'+ r'
=> bq-bq' = r' - r
=> b ( q - q') = r' - r
=> b / q - q'
If r' -r ≠ 0 then b ≤ | r '- r' |
Since r < b and r' < b => r - r' < b
| r - r' | < b
This is a controdiction to b ≤ | r - r' |
∴ r' - r = 0
=> r ' = r.
We have b ( q - q' ) = r' - r
=> b ( q - q' ) = 0 | since r' - r = 0 |
b = 0 or q - q' = 0.
Since b > 0 , we have q - q' = 0
q = q'
Hence a = bq + r = bq' + r'
=> q = q' and r= r'
In the representation of a = bq + r, q and r are unique.
Moreover, suppose r = 0.
∴ a = bq + r
< = > a = bq
< = > b/a
*** Hence the Proof ***
Note :
In the above theorem, the integers q and r are called the quotient and remainder when a is divided with b.
* Historical background of Number Theory
* Fundamental theorem of arithmetic
#Euclidean #Algorithm #- #Number #Theory
Comments
Post a Comment