Is there any actual proof as to why inverses can't exist if numbers have a gcd that isn't one. I understand it intuitively but I would like to see an actual proof if there is one.
Turn on thread page Beta
Inverses in modulo arithmetic watch
- Thread Starter
- 11-04-2006 18:29
- 11-04-2006 18:37
Ok, I'm assuming you want a proof that if m in Z_n has a multiplicative inverse, then m and n are coprime. If not you'll have to write back and be more clear.
Suppose m in Z_n has a multiplicative inverse, then for some integer a, am-1 is a multiple of n. So for some integer b, we have
am - 1 = bn
am - bn = 1
Therefore m and n are coprime. (Recall that the gcd of two numbers m and n may be expressed as am+bn for some integers a and b).
- 11-04-2006 18:55
Also note that we have if gcd(a,n)=1 then a has a unique multiplicative inverse modulo n. So this is actually an "iff" condition.
Try proving this direction. (Hint: Define f:Z_n->Z_n by f([x])=[ax] for all [x] in Z_n. Show that this is a bijection.)