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 | Radewoosh | 3759 |

2 | orzdevinwang | 3697 |

3 | jiangly | 3662 |

4 | Benq | 3644 |

5 | -0.5 | 3545 |

6 | ecnerwala | 3505 |

7 | tourist | 3486 |

8 | inaFSTream | 3478 |

9 | maroonrk | 3454 |

10 | Rebelz | 3415 |

# | User | Contrib. |
---|---|---|

1 | adamant | 173 |

2 | awoo | 167 |

3 | SecondThread | 163 |

4 | BledDest | 162 |

4 | Um_nik | 162 |

6 | maroonrk | 161 |

6 | nor | 161 |

8 | -is-this-fft- | 150 |

9 | Geothermal | 146 |

10 | TheScrasse | 143 |

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/02/2023 01:50:05 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

Proof not relying on Euclidean algorithmLet'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.