# Multiplicative Inverse

• May 11th 2012, 09:34 AM
alyosha2
Multiplicative Inverse
This is in regard to proving that the statements (a) $a$ and $n$ are coprime and (c) row $a$ of the multiplication table for $Z_{n}$ includes all of $Z_{n}$

$ab = kn + 1$

"this equation implies that $a$ and $n$ are coprime because any common factor of $a$ and $n$ must also be a factor of 1

I don't see why this is so.
• May 11th 2012, 09:44 AM
Sylvia104
Re: Multiplicative inverse
Let $d$ be a common factor of $a$ and $n,$ so $a=a_0d,$ $n=n_0d$ for some integers $a_0,n_0.$ Then

$\begin{array}{rcl} ab &=& kn+1 \\ a_0db &=& kn_0d+1 \\ \left(a_0b-kn_0\right)d &=& 1 \end{array}$

Thus $d\mid1.$
• May 13th 2012, 01:07 AM
alyosha2
Re: Multiplicative Inverse
So because the difference is 1 we know the only factor we can pull out is 1. Good stuff. Thanks for the help.
• May 13th 2012, 11:02 PM
kalwin
Re: Multiplicative Inverse
Thank you Sylvia for solving this problem, even i had the same problem and i was also thinking of posting this but i saw Alyosha2 had already posted it and from here i got the solution of the problem and this is the best forum where we get maximum math problem solved.