Hi(adsbygoogle = window.adsbygoogle || []).push({});

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!

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Euclidean algorithm

Loading...

Similar Threads - Euclidean algorithm | Date |
---|---|

A Pairing algorithm | Jan 27, 2018 |

B Bellman's and Bellman-Ford algorithm | Nov 1, 2017 |

I Dijkstra's algorithm spp | Nov 1, 2017 |

I Dijkstra's algorithm - Shortest Path Query | Jan 8, 2017 |

**Physics Forums - The Fusion of Science and Community**