Let a & b are two positive integers such that a=bq+r. Prove that the common factor of a & b must be the common factor of b & r. 

Asked by araima2001 | 8th Jun, 2015, 10:56: AM

Expert Answer:

a=bq+r
Let a common factor of 'a' and 'b' be 'c'.
So a=cA and b=cB, where 'A' and 'B' are integers.
Substituting these values in the first equation, we get
cA = cBq + r
In the left hand side we have a multiple of 'c'. Hence, the right hand side should also be a multiple of 'c'.
cBq is a multiple of 'c'. So for 'cBq + r' to be a multiple of 'c', the second term 'r' must be a multiple of 'c'.
Hence, we can write 'r' as cR, where 'R' is some integer. 
Hence, 'c' is a common factor of 'b' and 'r'. (Proved)

Answered by satyajit samal | 9th Jun, 2015, 10:03: AM

Queries asked on Sunday & after 7pm from Monday to Saturday will be answered after 12pm the next working day.