# Bezout's Identity and inverse modulo proof (GCD) [duplicate]

So might be a dumb question and actually quite simple, but I managed to confuse myself, and I don't really want to be learning the wrong thing.

So $$a≡b\;(\bmod n)$$ can be defined by $$a-b=ln,$$ $$l\in\mathbb{Z}$$ (modular equivalence), and if it exists, the modular inverse $$p^{-1}p≡1\;(\bmod q)$$.

Bezout's identity states that for some $$a,b$$ there always exists $$m,n$$ such that $$am + bn = \gcd(a, b)$$

How should I show the inverse mod as a modular equivalence? I just kind of know how to do them but not how to work them if that makes sense and I'm confusing myself.

How would I then use that with Bezout's Identity to find the gcd?

• It's not clear what you are asking, Maybe a specific example would help to clarify, – Bill Dubuque Oct 21 at 3:25
• Most of what you have written is very sloppy, Anan, which may be the root cause of your difficulties. $a\equiv b\bmod n$ is not defined by $a-b=ln$, it is defined by "there exists an integer $l$ such that $a-b=ln$. The modular (not "modulo") inverse of $p$, working modulo $q$, is the object $r$ such that $rp\equiv1\bmod q$, and $p^{-1}$ is a common notation for this modular inverse (provided $q$ is understood. Continued. – Gerry Myerson Oct 21 at 4:03
• Bezout states that for every pair $a,b$ other than $a=b=0$ there exist integers $m,n$ such that $am+bn=\gcd(a,b)$. Now: what do you mean by "show the inverse mod as a modular equivalence"? What do you mean by "use that with Bezout's identity to find the gcd"? Please try to give answers that use the language carefully and precisely. – Gerry Myerson Oct 21 at 4:06
• Also, finding the gcd is generally done with Euclid's algorithm. – Gerry Myerson Oct 21 at 4:07
• The question isn't what $p^{-1}p\equiv1\bmod q$ means, the question is what $p^{-1}$ means, because it doesn't mean the rational number $1/p$ as one might expect it to. It means the solution $x$ to the congruence $px\equiv1\bmod q$, so it means the $x$ (modulo $q$) such that there exists $y$ such that $px-1=qy$. – Gerry Myerson Oct 21 at 4:28

$$p^{-1}p \equiv 1\;(\bmod q)$$ simply means $$p^{-1}p=kq+1,k\in\mathbb{Z}$$. Using Bézout's Lemma, we can find the modular inverse of $$p\; (\bmod q)$$. Note that the inverse only exists if $$\gcd(p,q)=1$$. By the lemma, there exist integers $$x,y$$ such that $$px+qy=1\Rightarrow px=(-y)q+1\Rightarrow px\equiv 1\;(\bmod q)$$ and so by definition $$x$$ is the modular inverse of $$p$$.
• Would there be a way to simply rearrange what you get from that and then apply bezout's identity to conclude that if $gcd(p, q) = 1$ then $p^{-1}$ exists $(modulo$ $q)$? Or is the extended euclidean the only way? – Anan Oct 21 at 4:43
• @Anan I showed using Bézout's lemma that if $\gcd(p,q)=1,$ then $p^{-1}$ exists modulo $q$. The extended euclidean method is very useful for computing $\gcd(a,b)$ when $a$ and $b$ are very large. – user706791 Oct 21 at 4:47