MathDB

<span class='latex-italic'>Euclidean step</span>

transforms a pair

(a, b)

of positive integers,

a > b

, to the pair

(b, r)

, where

r

is the remainder when a is divided by

b

. Let us call the

<span class='latex-italic'>complexity</span>

of a pair

(a, b)

the number of Euclidean steps needed to transform it to a pair of the form

(s, 0)

. Prove that if

ad - bc = 1

, then the complexities of

(a, b)

and

(c, d)

differ at most by

2

Problem Statement