Given $a$ in $\gcd(a,b)$ with $a > b > 0$, how can I find $b$ which give the maximum number of steps for the Euclidean algorithm?

Question

Given $a$, where $a$ and $b$ are positive integers with $a > b$, how can I find the values for $b$ which give the maximum number of steps for the Euclidean algorithm $\gcd(a,b)$?

For example, where $a = 1000, b = 703$ and $b = 633$ both give the maximum number of steps:

$$(1000,703) → (703,297) → (297,109) → (109,79) → (79,30) → (30,19) → (19,11) → (11,8) → (8,3) → (3,2) → (2,1)$$

$$(1000,633) → (633,367) → (367,266) → (266,101) → (101,64) → (64,37) → (37,27) → (27,10) → (10,7) → (7,3) → (3,1)$$

If $a$ is the Fibonacci number $F_n$, then $b= F_{n-1}$ gives the maximum number of steps, but I'm looking for a method that works for any $a$.

Thanks.

Update: C code to list all b which take max steps

I've been using the following code to iterate through all possible b and display those which take the max number of steps. However, I was hoping there might be some way to calculate solutions or narrow the range.

#include <stdio.h>

/* count number of steps for Euclidean algorithm */

int gcd_steps(int a, int b)
{
    return !a ? 0 : 1 + gcd_steps( b % a, a );
}

/* for each A (1-50), display the maximum number of steps for the
   Euclidean algorithm and list all B which take the max steps */

void main()
{
    int a, b, max_steps;
    for ( a=1; a<=50; a++ )
    {
        max_steps = 0;
        for ( b=1; b<a; b++ )
            if ( gcd_steps( b,a ) > max_steps )
                max_steps = gcd_steps( b, a );
        printf( "%i [%i] ",a , max_steps );
        for ( b=1; b<a; b++ )
            if ( gcd_steps( b, a ) == max_steps )
                printf( "%i,",b );
        printf( "\n" );
    }
}

Answer 1

Comment:

Suppose number of steps or the length is $l$, we have:

$a-kb=d_1$

$b-k_1d_1=d_2$

$d_1-k_2d_2=d_3$

.

.

.

$d_{l-2}-d_{l-1}=d_l$

---

$a-(k-1)b-d_l=\sum^l_{i=1}l_id_i \space\space\space\space\space\space\space\space\space(1)$

Also we know that if $(a, b)=c$ , then we have an equation like:

$ma-nb=c\space\space\space\space\space\space\space\space\space(2)$

So we have to maximise $l$ in following system of equations:

$\begin{cases}a-(k-1)b-d_l=\sum^l_{i=1}l_id_i\\ma-nb=c\end{cases}$

We can let $l$ and $c$ as knowns of system. For estimating $l$ and $b$ we may use following method: In your example we have:

$m\times 1000- 703\times633=1$

which gives $m=445$ and $n=703$ or $n=633$, such that:

$445\times 1000-703\times 633=1$

we can use this property for estimation of other numbers. For example we want to find $b$ for number $a=4277$. We may write:

$4277/1000=4.277$

We use this as proportion factor:

$b= 4.277\times633=2707.341$

Take for example $b=2707$ which is prime, so $c=1$:

$(4277, 2707)=1$, also number of steps or length is $l=10$

Also $m=1788$and $n=2825$, such that:

$1788\times 4277-2825\times 2707=1$

$(4277, 2825)=1$, also number of steps or the length is $l=10$

We do not know $l=10$ is maximum, but we can check few numbers as a range it's mean is $2825$ or $2707$.

We can also try $b= 4.227\times 703=3006.731$, take for example $b=3001$ which is prime and gives:

$1437\times 4277-2048\times 3001=1$

$(4277, 3001)=1$ and $l=6$

also:

$(4277, 2048)=1$ and $l=6$

and conclude that numbers $2875$ and $2707$ are more reasonable for our task.