4

If $c,d$ are two relatively prime positive integers, then we can find integers $a,b$ such that $ad-bc=1$. But $a$ and $b$ are not unique: we can replace $a$ with $a+kc$ and $b$ with $b+kd$ for any integer $k$ and get another solution. So there is a solution $(a,b)$ of minimal distance from the origin, in the sense that $a^2+b^2$ is smallest possible, and in fact that's the solution found via the Euclidean algorithm. My question is: what can we say about the size of $a^2+b^2$ for the minimal solution? Is it true that $a^2+b^2$ is always less than $c^2+d^2$?

Math101
  • 1,106
  • 2
    If it helps: just by considering the quadratic function $(a + k c)^2 + (b + k d)^2$ of $k$, the real number $k$ that minimizes it is $k=-(ac+bd)/(c^2+d^2)$ and at that $k$-value the function takes the value $1/(c^2+d^2)$. The minimal integer solution will arise from either $\lfloor -(ac+bd)/(c^2+d^2) \rfloor$ or $\lceil -(ac+bd)/(c^2+d^2) \rceil$. – Greg Martin Mar 28 '24 at 01:23
  • The answer is contained in solving this previous Question about whether the extended Euclidean algorithm does find the smallest coefficients. In terms of the present notation it is shown (by induction on the number of steps needed) that if $c \gt d$, then $|a| \le c/2$ and $|b| \le d/2$. Thus $a^2 + b^2 \le c^2$. If you agree, we can mark this Question as a duplicate. – hardmath Mar 30 '24 at 16:32
  • The Wikipedia article presents only a weaker claim, so it might be worth having an Answer here to sort out the difference. – hardmath Mar 30 '24 at 17:34

1 Answers1

1

Comment: See my comment on this question:' Given $a$ in $\gcd(a,b)$ with $a > b > 0$, how can I find $b$ which give the maximum number of steps($l$) for the Euclidean algorithm?'

I found the size of $a^2+b^2$ depends on the number of steps for the Euclidian algorithm. Look at this example from my previous comment:

$1437\times4277-2048\times 3001=1$

1)) Number of steps: 10

2)) $a^2+b^2=6259273$

3)) $c^2+d^2=27298730$

$\Rightarrow a^2+b^2<c^2+d^2$

For the same $d=4277$ we also have:

$1788\times 4277-2825\times 2707=1$

1)) Number of steps: 10

2)) $a^2+b^2=11156149$

3)) $c^2+d^2=25620578$

4)) $\Rightarrow a^2+b^2<c^2+d^2$

Comparing these two we Find:

$(l=10):a^2+b^2=11156149>6259273; (l=6)$

we predict revers for $c^2+d^2$ and it is true and shown below:

$(l=6): c^2+d^2=27298730> 25620578; (l=10)$

So in both cases $a^2+b^2<c^2+d^2$.

sirous
  • 10,751
  • I don't think this solves the Question. At best it checks a few examples, and drawing a connection with another Question is not well explained. – hardmath Mar 30 '24 at 14:30
  • @hardmath, I like to see an alternative or counter example.I used the examples from my previous comment, this is the connection. – sirous Mar 30 '24 at 14:39
  • It looks like you are referring to this previous Answer from about one year ago. I've given a link to an older Question above where the claim is proved in a fairly strong form. – hardmath Mar 30 '24 at 16:42
  • @hardmath, Correct. How can I refer to a question by a code in Latex?Where is your link? – sirous Mar 31 '24 at 04:37