respected teacher,
what do you mean by the statement "greatest common divisor of two numbers can be expressed as a linear combination of two numbers"?????
please explain using an example..

Asked by shailesh arlekar | 28th Jun, 2014, 07:25: PM

Expert Answer:

C o n s i d e r space t h e space H C F space o f space 65 space a n d space 117 H e r e comma space 117 greater than 65 A p p l y i n g space e u c l i d apostrophe s space d i v i s i o n space l e m m a comma space w e space h a v e comma 117 equals 65 cross times 1 plus 52. comma.. left parenthesis 1 right parenthesis A n d space 52 not equal to 0 comma space s o space a p p l y i n g space d i v i s i o n space l e m m a space a g a i n comma space w e space h a v e 65 equals 52 cross times 1 plus 13... left parenthesis 2 right parenthesis H e r e comma space 13 not equal to 0 comma space t h u s comma space a p p l y i n g space d i v i s i o n space l e m m a comma space w e space h a v e comma 52 equals 13 cross times 4 plus 0 H e r e comma space t h e space r e m a i n d e r space i s space z e r o. space T h u s comma space H C F space o r space G C D space o f space 65 space a n d space 117 space i s space 13. N o w space f r o m space left parenthesis 2 right parenthesis comma space w e space h a v e comma 13 equals 65 minus 52 cross times 1 rightwards double arrow 13 equals 65 minus open parentheses 117 minus 65 cross times 1 close parentheses cross times 1 space space space space space space space open square brackets f r o m space left parenthesis 1 right parenthesis close square brackets rightwards double arrow 13 equals 65 minus 117 cross times 1 plus 65 cross times 1 rightwards double arrow 13 equals 65 cross times 2 minus 117 cross times 1 rightwards double arrow 13 equals 65 cross times 2 plus 117 cross times open parentheses minus 1 close parentheses rightwards double arrow 13 equals 65 m plus 117 n comma space w h e r e space m equals 2 space a n d space n equals minus 1 T h u s comma space G C D space o f space t w o space n u m b e r s space c a n space b e space e x p r e s s e d space a s space a space l i n e a r space c o m b i n a t i o n space o f space t w o space n u m b e r s.

Answered by Vimala Ramamurthy | 30th Jun, 2014, 11:24: AM