You are Here: Home >< Maths

# Inverses in modulo arithmetic watch

1. 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.
Thanks
2. 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).
3. 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.)

### Related university courses

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: April 11, 2006
Today on TSR

### 2,966

students online now

Exam discussions

Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams