# Bézout's Identity **The [[greatest common divisor]] of two integers can be expressed as the linear combination of those two integers.** >[!Example] Bézout's Identity > For any integers $a$ and $b$, there exists *integers* $x$ and $y$ such that > $\gcd(a,b)=ax+by$ > Additionally, any integers of the form $as+bt$ are *multiples* of $\gcd(a,b)$. As by definition $\gcd(a,b)\mid a$ and $\gcd(a,b)\mid b$, the GCD of $a$ and $b$ must also be divisible by any *integer linear combination* of $a$ and $b$. Thus, for $ax+by=d$ where $x$ and $y$ are integers, - If $\gcd(a,b)\nmid d$, then there are *no integer solutions* for $x$ and $y$ - If $\gcd(a,b) \mid d$, then integer solutions can be found for $x$ and $y$ by applying the [[Euclidean Algorithm|reverse Euclidean algorithm]].