- #1
miccol999
- 7
- 0
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!