Let $a, b$ be coprime rational integers. Then by Bezout's lemma we can find $(s,t) := \beta(a,b) \in \mathbb{Z}^2$ such that $a*s + b*t = 1$. My question concerns the prime factorization of the second Bezout coefficient $t$.

Now suppose that only $a\in\mathbb{Z}$ is given and our task is to choose $b\in\mathbb{Z}$ with $(a,b)=1$ such that $t$ is easy to factorize, eg. is n-smooth prime, for some $n \in O(\log a)$.

With this much freedom would it be possible to ensure that $t$ can be factorized easily? In general, can anything be said about the decomposition of Bezout coefficients?

edit I considered $a s + b t = 1$. If $b << a$, then we can expect $s = 1$, and so $t$ can be written as $t = \frac{1-a}{b}$. However, I don't know anything about the factorization of $a$ or $1-a$...

edit2: in response to FredH's comment: I'd like to find b with the additional property that $b << a$.

  • $\begingroup$ As written, this is trivial. Choose $b = 1-a$; then $t = s = 1$. Is there some other condition you had in mind? $\endgroup$ – FredH Mar 2 at 18:46
  • $\begingroup$ @FredH, yes thank you for pointing this out. I did consider that case, and in fact I'd like to have $b << a$, I just didn't want to make the question too convoluted. I see this is suboptimal, will edit it in a minute. $\endgroup$ – gen Mar 2 at 18:48

Knowing a and b are coprime, two cases appear:

  • a,b both odd
  • a,b opposite parity

In the first case, if s and t are both odd, then we have odd+odd=odd which is false. So if s is even, t is odd. If s is odd, t is even.

The second case, has s and t of same parity. If s is even, then t will also be even. If s is odd, t will be odd as well.

You can continue this, mod as many primes as you want.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.