How to do this modified Bezout's Theorem thingy?

Revision en2, by Red0, 2024-08-18 10:48:53

I'm trying to solve this problem: Xum

And it's hard enough that I look at the editorial.

Then I meet this Bezout's Theorem for the first time ever in my life, which online, it states that there exist $$$a$$$ and $$$b$$$ for any equation in the form of $$$ax+by=gcd(x, y)$$$, or in the case of this problem where both $$$x$$$ and $$$y$$$ are relatively prime, $$$ax+by=1$$$.

This is a classic Diophantine equation, which can be solved using the Extended Euclidean Algorithm. However what the problem asks us for is to find values of $$$a$$$ and $$$b$$$ such that $$$a,b ≥ 0$$$ and $$$ax-by=1$$$. How do we do this?

Thanks!

If you are like me and missed some tiny important details when reading, it might help to know beforehand that $$$x ≤ 999,999$$$ and is odd for all testcases.

Tags math

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Red0 2024-08-20 15:49:56 291
en2 English Red0 2024-08-18 10:48:53 157
en1 English Red0 2024-08-18 10:43:04 694 Initial revision (published)