Efficiently producing certain kinds of examples of the application of Euclid's algorithm Is there some efficient way to churn out pairs of integers $n,m$ such that


*

*$\gcd(n,m)=1$;

*$n,m$ both have fairly large numbers of fairly small prime factors; and

*Euclid's algorithm applied to $n,m$ has a moderately large number of steps; e.g. a number is replaced by its remainder at least four or five or six times?

 A: Example #1: Neighboring Fibonacci Numbers
By reverse induction and $F_n + F_{n-1} = F_{n+1}$

$(F_n, F_{n+1}) = (F_n, F_{n-1} + F_n) = (F_n, F_{n-1}) = \dots = (F_1, F_0) = 1$

How to prove gcd of consecutive Fibonacci numbers is 1?

Example #2: Advanced Discussion on arXiv
just this week A short proof that the number of division steps in the Euclidean algorithm is normally distributed was posted.  The average number of Euclidean algorithm steps is $\frac{12}{\pi^2} \log 2 \log n $.  If $n = 10^6$ that number is about $2 \times 6 = 12$.
Here with some Python I compute random gcd's of numbers up to $10^6$.  Notice it takes no more than 30 steps (on average about $12$ in agreement with above). In these examples GCD will be $1$ about two-thirds of the time.  My code is on GitHub.


Example #3: Connection to Yves Daoust solution
Divide the set $P$ of primes less than 100 and split into two sets $P_1, P_2$.  If you randomly multiply only within $P_1$ or $P_2$ you are guaranteed to be relatively prime and smooth.  If these two products are less than $10^N$ the expected number of steps is around $2*N$.
A: $$3\cdot7\cdot13\cdot23\cdot31\cdot41=6737367$$
$$2\cdot5\cdot11\cdot17\cdot29\cdot37=2376770$$
$$6737367,
2376770,
1983827,
392943,
19112,
10703,
8409,
2294,
1527,
767,
760,
7,
4,
3,
1$$
A: I would try working the Euclidean algorithm backwards: $r_{n-2}=k\cdot r_{n-1}+r_n$, looking for $k$'s that gave me the small factors I wanted at each step.  Since you want $\gcd(m,n)=1$, the last two remainders would be $0$ (last), and $1$ (second to last).
For instance, the (reverse) sequence of remainders could be something like:
$0$
$1$
$6\cdot 1+0=6$
$4\cdot 6+1=25$
$2\cdot 25+6=56$
$1\cdot 56+25=81$
$4\cdot 81+56=380$
$3\cdot 380+81=1221$
Giving you a problem where you start with taking the gcd of $380=2^2\cdot 5\cdot 19$ and $1221=3\cdot11\cdot 37$
(Of course you can play with the multipliers going from one remainder to the next to (try to) get initial numbers that have suitable factorizations.)
Then, as you discuss in your comments, you would multiply each by some common amount to get the problem you wanted.  
