CameraIcon
CameraIcon
SearchIcon
MyQuestionIcon


Question

If a and b are positive integer such that a is equal to bq+r,then every common divisor of b and r,and vice versa


Solution

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. 

flag
 Suggest corrections
thumbs-up
 
0 Upvotes


Similar questions
View More


People also searched for
View More



footer-image