I'm having trouble understanding why for finding the inverse for $x\bmod n$, $\gcd(x, n)=1$ is a precondition. Obviously I've tried examples where the gcd is greater than one and I can't find $a$ for $ax \equiv _n 1$. I'm trying to prove to myself why this is the case.
I can mechanically say the following:
Find the modular inverse $a$ of $x\pmod n$
$$ax \equiv _n 1 \Leftrightarrow n \mid (ax-1)$$
And $n \mid (ax-1)$ implies that $(ax-1)=nk$ for some $k \in \mathbb Z $
After that I am stuck and I'm not sure if I'm going in the right direction.
Answer
If there is an inverse of $x \bmod n$, that gives us a number $y$ so that $xy \equiv 1 \bmod n$. That means that $xy=kn+1$, or (rearranging) that $xy-kn=1$.
Now for any common divisor, $c$, of $x$ and $n$ we will have that $c \mid (xy-kn)$ which gives $c\mid 1$, that is, $c=1$. So that is an outcome - and therefore a requirement - of finding the inverse of $x \bmod n$
No comments:
Post a Comment