Find Any Integer Pair That Needs Exactly K Euclidean Divisions to Make B Zero

Revision en2, by Zaoly, 2023-12-19 07:06:04

Assume two integers $a$ and $b$ ($a > b$) that form an ordered integer pair $(a, b)$. We can perform a Euclidean division on it, which will make it $(b, a \bmod b)$. If we keep performing this division, then $b$ will eventually be $0$. We define the number of Euclidean divisions needed to make $b$ equal $0$ as $k$.

Example: $(19, 8)$ → $(8, 3)$ → $(3, 2)$ → $(2, 1)$ → $(1, 0)$. We perform $4$ divisions until $b$ equals $0$, so $k = 4$.

With the value of $k$ specified ($1 \le k \le 10^9$), how to find any ordered integer pair $(a, b)$ ($1 \le b < a \le 10^{18}$) that needs exactly $k$ Euclidean division to make $b$ equal $0$? If there does not exist such a pair, report it.

I am also curious about one question: it is all known that the Euclidean algorithm is fast, but the speed of the algorithm is determined by $k$, so may $k$ be infinitely large?

#### History

Revisions

Rev. Lang. By When Δ Comment
en4 Zaoly 2023-12-19 07:18:27 14
en3 Zaoly 2023-12-19 07:07:44 10 Tiny change: 'and $b$ ($a > b$) that fo' -> 'and $b$ ($1 \le b < a$) that fo'
en2 Zaoly 2023-12-19 07:06:04 12
en1 Zaoly 2023-12-19 06:30:58 964 Initial revision (published)