Euclidean algorithm Proof

  • Thread starter hilly1
  • Start date
  • #1
1
0
Prove that the number of steps of the euclidean algorithm needed to find gcd(km,kn) is exactly the same as the number of steps needed to find gcd(m,n).

any help on this would be appreciated. I'm really lost.
 

Answers and Replies

  • #2
402
1
This a consequence of gcd(ka,kb) = |k|gcd(a,b); after applying the euclidean algorithm to gcd(a,b), multiply each of the lines by |k|, and check that this is a valid sequence of divisions (that is, |k|ri is a valid remainder for each of the divisions). The result follows immediately.
 

Related Threads on Euclidean algorithm Proof

  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
1
Views
3K
Replies
6
Views
4K
Replies
2
Views
7K
  • Last Post
Replies
3
Views
4K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
8
Views
4K
Top