471 views
0 votes
0 votes

Let (x, y) correspond to gcd(b, a mod b), i.e. gcd(b, a mod b) = x·b + y· (a mod b). Then show that gcd(a, b) = y· a + (xq)b where q is the quotient of the integer division of a by b.

Can anyone help me with this?
 

Please log in or register to answer this question.

Related questions

2 votes
2 votes
2 answers
1
Pawan Kumar 2 asked Jan 18, 2018
475 views
Kindly help...thanks
5 votes
5 votes
1 answer
2
rahul sharma 5 asked Dec 14, 2016
1,036 views
Reposting the previous post as I faced same questions during test series.Not able to find exact answer on google.I will close previous post.
0 votes
0 votes
0 answers
3
rahul sharma 5 asked Dec 8, 2016
701 views
What is the best case and worst case time complexity for Euclid's algorithm?Let numbers be a and bAs per my understandingBest case - If a and b are multiple :0(1).Worst c...
1 votes
1 votes
1 answer
4
radha gogia asked Jul 21, 2015
2,178 views
I have already gone through the links of stackoverflow on this topic but still couldn't understand it clearly , so please explain the logic behind this .