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

Related Videos

This video explains the statement of Euclid's Division lemma and algorithm ...

This video explains the statement of Euclid's Division lemma and algorithm ...

This video explains the statement of Euclid's Division lemma and algorithm ...

All Questions Ask Doubt