Bezout's Lemma

From AoPSWiki

Bezout's Lemma states that if two integers $x$ and $y$ satisfy $gcd(x,y)=1$ , then there exist integers $\alpha$ and $\beta$ such that $x\alpha+y\beta=1$ . In other words, there exists a linear combination of $x$ and $y$ equal to $1$ .

Proof

Since $gcd(x,y)=1$ , $lcm(x,y)=xy$ . So $\alpha=y$ is the first time that $x\alpha\equiv 0\bmod{y}$ , and it is there that the modular residues begin repeating. Now if for all integers $0<a,b<n$ , we have that $xa\neq xb\bmod{y}$ , then one of those $n-1$ integers must be 1 from the Pigeonhole Principle. Assume for contradiction that $xa\equiv xb\bmod{y}$ . Thus it repeats, and one of $a$ or $b$ must be $\geq n$ , which is opposite of what we had. Thus there exists an $\alpha$ such that $x\alpha\equiv 1\bmod{y}$ , and the same proof holds for $\beta$ .

Since $x\alpha +y\beta$ is equivalent to 1 mod x and mod y, and $gcd(x,y)=1$ , $x\alpha +y\beta \equiv 1\bmod{xy}$ . Lets say that $x\alpha+y\beta=xy\gamma +1$ for some integer $\gamma$ . We can subtract $y\gamma$ from $\alpha$ and plug that in to get

$x(\alpha-y\gamma)+y\beta=xy\gamma+1-xy\gamma=1$ .

Thus there does exist integers $\alpha$ and $\beta$ such that $x\alpha+y\beta=1$ .

Personal tools

Navigation

Search

Toolbox

Bezout's Lemma

From AoPSWiki

Proof

See also