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 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
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 \gt 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 \gt 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.