0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ It's not clear what you are asking, Maybe a specific example would help to clarify, $\endgroup$ – Bill Dubuque Oct 21 at 3:25
  • 2
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson Oct 21 at 4:03
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Oct 21 at 4:06
  • $\begingroup$ Also, finding the gcd is generally done with Euclid's algorithm. $\endgroup$ – Gerry Myerson Oct 21 at 4:07
  • 1
    $\begingroup$ 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$. $\endgroup$ – Gerry Myerson Oct 21 at 4:28
2
$\begingroup$

$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$.

As for finding the gcd, you would use the Extended Euclidean Algorithm.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Anan Oct 21 at 4:43
  • $\begingroup$ @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. $\endgroup$ – user706791 Oct 21 at 4:47
  • $\begingroup$ Ahh I managed to miss ". Using Bézout's Lemma, we can find the", you updated it midway while I was reading it and so missing that part made me think you were saying this is all this, then for that use EEA, my bad $\endgroup$ – Anan Oct 21 at 4:53
  • $\begingroup$ @Anan glad I could help $\endgroup$ – user706791 Oct 21 at 4:55

Not the answer you're looking for? Browse other questions tagged or ask your own question.