if integers A and B satisfy gcd(A,B)=1,why there are always two integers x and y that x*A-y*B=1?
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3757 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| # | User | Contrib. |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | awoo | 165 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | maroonrk | 155 |
| 6 | nor | 154 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 147 |
| 9 | orz | 145 |
| 9 | pajenegod | 145 |
check extended euclidian algorithm. Because this algorithm works you can see that this statement is always true
Also it can be proved by euler theorem
Let's consider all $$$Ai + Bj > 0$$$ and take the smallest of them $$$d = min(Ai + Bj) = Ax + By$$$.
Let $$$r$$$ be a remainder of $$$A$$$ divided by $$$d$$$: $$$A = dA_1 + r$$$, $$$d > r \ge 0$$$.
Then $$$r = A - dA_1 = A - (Ax + By)A_1 = A(1 - x) - B(A_1y)$$$, so $$$r$$$ can also be represented as $$$Ai + Bj$$$, or $$$r = 0$$$. The former means that $$$r \ge d$$$ (as $$$d$$$ is minimal such number), which leads to contradiction. Then $$$r = 0$$$, meaning that $$$d$$$ is a divisor of $$$A$$$. The same logic applies to $$$B$$$, so $$$d$$$ is a common divisor of $$$A$$$ and $$$B$$$.
Why is it the greatest? Because if $$$g = gcd(A, B)$$$, then $$$d = Ax + By$$$ $$$\vdots$$$ $$$g$$$, implying $$$d \ge g$$$.
Well, it's Bézout's identity。 You can search it on the Internet.