Problem 1: Let k>3 be an odd number. Perform the Euclidean Algorithm on 2k and k+1. How many divisions will be required? Explain.
Problem 2: Let k>3 be an even number. Perform the Euclidean Algorithm on 2k and k+1. How many divisions will be required? Explain.
My proposed solutions:
Problem 1: k is odd
Divide through until the remainder becomes 2. Then, for the next (and last division), it becomes a matter of forming an even number using 2.
2k = (1)(k-1) +(k-1)
k+1 = (1)(k-1) + 2
k-1 = 2n + 0, where n is a natural number, since k-1 is even
Problem 2: k is even
Divide through until the remainder becomes 2. Then use 2 to form an odd number, in the form of 2n+1. Since 2n+1 leaves a remainder that is a divisor of 2n, there is one last division.
2k = (1)(k+1) + (k-1)
k+1 = (k-1) + 2
k-1 = 2n + 1, where n is a natural number, since k-1 is odd
2n = (1)(2n) + 0
Thoughts? Does this seem right? Should I be working towards definitive numbers, rather than inserting a natural number variable, n? Is there a more succinct explanation for these problems?