Choosing two numbers $a,b,$ such that the Euclidean algorithm takes 10 steps 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??
 A: 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.
A: 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. 
