Question

Proof that if a and b are +ve 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

Answer 1

Answer:

Step-by-step explanation:

According to the euclids division algorithm, we calculate the Highest Common Factor (HCF) of two given positive integers. The HCF of two positive integers a and b is the largest positive integer d dividing both a and b.

Let the common divisor of a and b = c

Then,  

c| a = a = cq1 for some integer q1

c| b = b = cq2 for some integer q2.

Now, a = bq + r  ( Given)

= 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, the common divisor of a and b is a common divisor of b and r.

Answer 2

Here's the solution

Let c be some common divisor of a & b

Let c be some common divisor of a & bThen,

Let c be some common divisor of a & bThen,c | a => a=cq1 for some integer q1 ; c | b=> b=cq2 for some integer q2

Let c be some common divisor of a & bThen,c | a => a=cq1 for some integer q1 ; c | b=> b=cq2 for some integer q2Now,

Let c be some common divisor of a & bThen,c | a => a=cq1 for some integer q1 ; c | b=> b=cq2 for some integer q2Now,a=bq+r

Let c be some common divisor of a & bThen,c | a => a=cq1 for some integer q1 ; c | b=> b=cq2 for some integer q2Now,a=bq+r=>r=a-bq

Let c be some common divisor of a & bThen,c | a => a=cq1 for some integer q1 ; c | b=> b=cq2 for some integer q2Now,a=bq+r=>r=a-bqbut, a=cq1 & b=cq2

Let c be some common divisor of a & bThen,c | a => a=cq1 for some integer q1 ; c | b=> b=cq2 for some integer q2Now,a=bq+r=>r=a-bqbut, a=cq1 & b=cq2so, r=cq1-cq2q

Let c be some common divisor of a & bThen,c | a => a=cq1 for some integer q1 ; c | b=> b=cq2 for some integer q2Now,a=bq+r=>r=a-bqbut, a=cq1 & b=cq2so, r=cq1-cq2q=>r=c(q1-q2q)

Let c be some common divisor of a & bThen,c | a => a=cq1 for some integer q1 ; c | b=> b=cq2 for some integer q2Now,a=bq+r=>r=a-bqbut, a=cq1 & b=cq2so, r=cq1-cq2q=>r=c(q1-q2q)Hence, c | r

Therefore, c | r and c | b ( Given)

c is a common divisor of b and r.

Similarly we can do the vice-versa for d to be common divisor of b and r respectively.

Hope it helps.