1. ## Multiplicative Inverse

This is in regard to proving that the statements (a) $\displaystyle a$ and $\displaystyle n$ are coprime and (c) row $\displaystyle a$ of the multiplication table for $\displaystyle Z_{n}$ includes all of $\displaystyle Z_{n}$

$\displaystyle ab = kn + 1$

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

I don't see why this is so.

2. ## Re: Multiplicative inverse

Let $\displaystyle d$ be a common factor of $\displaystyle a$ and $\displaystyle n,$ so $\displaystyle a=a_0d,$ $\displaystyle n=n_0d$ for some integers $\displaystyle a_0,n_0.$ Then

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

Thus $\displaystyle 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.