I'm having trouble understanding why for finding the inverse for xmod, \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