# 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?

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" );
}
}

• oeis.org/A034883 is relevant. Commented Mar 27, 2023 at 10:42
• @GerryMyerson thank you, yes. I've read through A034883 and some related sequences, but I haven't found any method apart from iterating though all possible b. I was hoping there might be some way to calculate solutions or narrow the range. Commented Mar 29, 2023 at 18:48
• Let's look at $a=997$, where the maximum number of steps is $12$. There are $996$ values of $b$ to check, and only $12$ different possible lengths, so on average there are $83$ values of $b$ for each length. I don't know how many values of $b$ actually give length $12$, but this calculation suggests there might be lots of them. I think that's one of the difficulties; if there were always only one or two values of $b$ maximizing length, there'd be a hope there was some formula to find them. But if there are $80$ different $b$ that work, then I don't see any improvement on exhaustive search. Commented Mar 29, 2023 at 21:33
• For a = 997, there are two values of b which give the max number of steps, 616 and 717. Of the a 1-1000, there are 63 where only one b gives the max number of steps and 455 where there are two values of b which give the max. Note ( 616 * 717 ) % 997 = 1. Of those 455 a which have two b with the max steps, 430 have ( b₁ * b₂ ) % a = ±1. Commented Mar 30, 2023 at 18:10
• It's no surprise that $b_1b_2\equiv\pm1\bmod a$ very often when $b_1$ and $b_2$ have the same number of steps, as the continued fractions of $b_1/a$ and $b_2/a$ are very closely related when $b_1b_2\equiv\pm1\bmod a$. It is a surprise to me that for $a=997$ there are only two values of $b$ that give the maximum number of steps. Commented Mar 30, 2023 at 22:18

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.

• Thank you, I'll go through your answer in detail and run some tests. Commented Apr 10, 2023 at 14:17