- #1

- 7

- 0

## Main Question or Discussion Point

Hi

I am currently studying Information Theory. Could I please have anyone's ideas on the following question:

Using the Euclidean algorithm, show that coprime numbers always have multiplicative inverses modulo each other.

I tried the following proof, using Fermat's little theorem, let me know what you think.

Let

{a,2a,...,(n-1)a}={1,2,...,(n-1)}(mod n)

Then

(n-1)! a^(n-1)=(n-1)! (mod n)

and

a^(n-1)=1 (mod n)

any improvements/suggestions are very welcome! Thank you!

I am currently studying Information Theory. Could I please have anyone's ideas on the following question:

Using the Euclidean algorithm, show that coprime numbers always have multiplicative inverses modulo each other.

I tried the following proof, using Fermat's little theorem, let me know what you think.

Let

{a,2a,...,(n-1)a}={1,2,...,(n-1)}(mod n)

Then

(n-1)! a^(n-1)=(n-1)! (mod n)

and

a^(n-1)=1 (mod n)

any improvements/suggestions are very welcome! Thank you!