What is the importance of Bézout's identity?

Solution 1:

Given integers $m,n$ (not both zero), Bezout's identity finds integers $x,y$ that satisfy: $$xm+ny=\gcd(m,n)$$

One important application is if we know $\gcd(m,n)=1$. Then, we can take the above equation modulo $n$ to get $$xm\equiv 1\pmod{n}$$ This is useful, because we have found the multiplicative inverse to $m$, modulo $n$.

We have a constructive (and fast) way to find $x,y$, using the extended Euclidean algorithm.

One reason a multiplicative inverse is useful is: suppose we want to find some integer $z$ satisfying the modular equation $$mz\equiv t\pmod{n}$$ Once we have found $x$, as above, we may multiply both sides by $x$ to get $$z\equiv 1z\equiv (xm)z\equiv xt\pmod{n}$$

Solution 2:

Bezout's identity turns the qualitative statement "two numbers are relatively prime" into an equation which can be manipulated. For a proof or exercise about relatively prime numbers, one of the common first steps is to turn that condition into Bezout's identity.

Solution 3:

Let's say you have two $a, b \in \Bbb{Z}$. Since they are in $\Bbb{Z}$, they have some greatest common divisor, which I'll call $d$. What Bezout's Identity states is that there exist $x, y \in \Bbb{Z}$ such that: $$ax+by=d$$ The way we find $x, y$ is through the Extended Euclidean Algorithm. If you recall, the regular Euclidean Algorithm takes in $a, b$ and then gives us the greatest common divisor, but the Extended Eucliden Algorithm takes $a, b$ and then gives us the greatest common divisor $d$ along with $x, y$.

Now, to find the RSA private key, we need that $d \equiv e^{-1} \pmod {\phi(n)}$ where $\gcd(e, \phi(n))=1$. Thus, by Bezout's Identity, we get there exist $x, y$ such that: $$ex+\phi(n)y=1 \implies ex=1-\phi(n)y \implies ex \equiv 1 \pmod {\phi(n)}$$ Thus, $ex$ is the private key, so we can find the private key by figuring out $x$ using the Extended Euclidean Algorithm.