Problem 958

Euclid’s Labour

The Euclidean algorithm can be used to find the greatest common divisor of two positive integers. At each step of the algorithm the smaller number is subtracted from the larger one. The algorithm terminates when the numbers are equal, which is then the greatest common divisor of the original numbers.

For two numbers $n$ and $m$, let $d(n, m)$ be the number of subtraction steps used by the Euclidean algorithm for computing the greatest common divisor of $n$ and $m$.

For a number $n$, let $f(n)$ be the positive number $m$ coprime to $n$ that minimizes $d(n, m)$. If more than one number attains the minimum, the minimal $m$ is chosen.

For example, at least four steps are needed for computing the GCD of $7$ and any positive number $m$ coprime to $7$. This number of steps is obtained by $m=2,3,4,5$, yielding $f(7)=2$. You are also given $f(89)=34$ and $f(8191) = 1856$.

Find $f(10^{12}+39)$.

欧几里得的劳作

欧几里得算法可以用于求两个正整数的最大公约数。算法的每一步都从较大的数中减去较小的数，直至两数相等为止，此时即得到初始两数的最大公约数。

对于两个正整数$n$和$m$，记$d(n, m)$为用欧几里得算法计算$n$和$m$的最大公约数时进行的减法次数。

对于正整数$n$，记$f(n)$为与$n$互质且使得$d(n, m)$最小的正整数$m$。如果有多个$m$能取得最小值，则选择最小的$m$。

例如，对于$7$和任意与$7$互质的正整数$m$，计算最大公约数至少需要进行四次减法，该最小值可由$m=2,3,4,5$取得，因此$f(7)=2$。此外已知$f(89)=34$，$f(8191) = 1856$。

求$f(10^{12}+39)$。