1. ## 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.

2. ## 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.$

3. ## 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.

4. ## 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.