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?
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3382 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 134 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/06/2026 13:48:41 (g2).
Desktop version, switch to mobile version.
Supported by
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.