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?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3690 |
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 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 163 |
4 | TheScrasse | 159 |
5 | nor | 157 |
6 | maroonrk | 155 |
7 | -is-this-fft- | 152 |
8 | Petr | 146 |
8 | orz | 146 |
10 | BledDest | 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.