Question

Why is Euclid's division algorithm , only for positive numbers.? Why not for negative numbers. ?

Answer 1

Theorem : If a and b are positive integers such that a = bq + r, then every common divisor of a and b is a common divisor of b and r, and vice-versa.
Proof : Let c be a common divisor of a and b. Then,
c| a ⇒ a = cq1 for some integer q1
c| b ⇒ b = cq2 for some integer q2.
Now, a = bq + r
⇒ r = a – bq
⇒ r = cq1 – cq2 q
⇒ r = c( q1 – q2q)
⇒ c | r
⇒ c| r and c | b
⇒ c is a common divisor of b and r.
Hence, a common divisor of a and b is a common divisor of b and r.
Euclids Division Algorithm is a technique to compute the Highest Common Factor (HCF) of two given positive integers. Recall that the HCF of two positive integers a and b is the largest positive integer d that divides both a and b.
FROM THE PROOF IF THE TWO INTEGERS ARE NEGATIVE THEN THE PROOF DOES NOT VALID.IT VIOLATE THE RULE SO WE CANT USE EUCLID'S DIVISION ALGORITHM.