### Gary2005's blog

By Gary2005, history, 4 years ago,

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?

• +8

 » 4 years ago, # |   +6 check extended euclidian algorithm. Because this algorithm works you can see that this statement is always true
•  » » 4 years ago, # ^ |   +3 Also it can be proved by euler theorem
 » 4 years ago, # | ← Rev. 2 →   +6 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$.
 » 4 years ago, # |   +11 Well, it's Bézout's identity。 You can search it on the Internet.