2
$\begingroup$

I have, $$sx + ty = d,$$ where $s,x,t,y,d \in \mathbb{Z}$ and $d$ is the gcd of $x$ and $y$. Is there anyway I could perhaps find an another expression: $$s'x + t'y = d,$$ where $s'$ is even? This question is relevant to me because it could be used for the binary Euclidean Algorithm.

Thanks!

$\endgroup$
1
  • 3
    $\begingroup$ Not necessarily, take for example $x=3, y=2, d=1$. $\endgroup$
    – dxiv
    Sep 19, 2021 at 0:24

1 Answer 1

0
$\begingroup$

As @dxiv mentioned, yes, it needn't happen always. I'd try and say using @dxiv's example:

We know, $\gcd(3,2) = 1 = d$. By Bezout's identity, we can say that $\exists s,t : 3s+2t = 1$.Here we see a solution $s = 1, t = -1$. Suppose you take $s$ as an even integer, say $2n$, we see $6n + 2t = 1$ which has no solution in $\mathbb{Z}$ as no two even numbers differ by $1$. But taking an even $t$ may be possible, for example let's say $t = 2k$ and thus $3s + 4k = 1$ and we get $(s,k) = (-9,7)$ and hence $(s,t) = (-9, 14)$.So yes, if you ever get an even $s'$ or $t'$, it's just trivial or even more properly, is a result of the numbers used(perhaps; I'm still learning 😄). If you look up in Wikipedia about Bezout's Identity, you can see the example of $12$ and $42$; here $s'$ can be even. So an even $s'$ can appear trivially or it may not; all depends on the numbers used.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .