Choosing two numbers $a,b,$ such that the Euclidean algorithm takes 10 steps

Question

The question is to find $2$ integers $a$,$b$ $\in \mathbb{Z}$ for which when applying the Euclidean Algorithm for finding the $\gcd \left(a,b\right)$ precisely $10$ steps are required. This is what I have done: Let $\left(a,b\right)$ = $\left(427,264\right)$ The $10$ steps for the $\gcd \left(427,264 \right)$ are as follows:

$427=264 \cdot 1+163$

$264=163\cdot1+101 $

$163=101\cdot1+62 $

$101=62\cdot1+39 $

$62=39\cdot1+23 $

$39=23\cdot1+16 $

$23=16\cdot1+7 $

$16=7\cdot2+2 $

$7=2\cdot3+1 $

$2=1\cdot2+0$

I just wanna know if what I have done is right??? or if possible note the place I gone wrong??

Answer 1

I like to answer questions directly: your question is very clear and I think the answer should be too, so here's the answer: yes, what you have done is right. Well done. I do think it would be interesting, as mentioned above, to know how you found a and b.

Answer 2

Here is what I think you did:

The final line is always $a = qb + 0$, since getting the remainder $0$ is how you know when to stop. So pick some $q$ and $b$ and then $a$ must be $qb$. Let's pick $q = 2$, $b = 1$, so the last line is $2 = 2\cdot 1 + 0$. How did we get there? Well, when you have some line $a = qb + r$ and $r \not= 0$, then for the next line you divide $b$ by $r$. So whatever the line before $2 = 2\cdot 1 + 0$ was, it must have had $r = 1$ and $b = 2$. So let's pick some other $q$, say $q = 3$, and get $7 = 3\cdot 2 + 1$. Similarly, the line before that might have been (pick $q = 2$) $16 = 2 \cdot 7 + 2$.

You can continue in this way for as long as you like. At every stage you are picking a $q$, which you can pick to be whatever positive integer you want, so all the possible ways of running Euclid's algorithm in $n$ steps correspond to all possible choices of $n + 1$ (remember at the last step we chose $b$ as well!) positive integers.