Euclidean algorithm

  • Thread starter miccol999
  • Start date
  • #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!
 

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,967
19
Well, I see these problems:

First, you introduce new variables without explanation: a and n. If they are supposed to be an arbitrary pair of coprime numbers, then you should say something like that.

{a,2a,...,(n-1)a}={1,2,...,(n-1)}(mod n)
How do you know that? The most obvious proof requires you to already know that a is invertible mod n.

Then
(n-1)! a^(n-1)=(n-1)! (mod n)
and
a^(n-1)=1 (mod n)
You cannot divide by (n-1)! unless you already know it's invertible. And you cannot prove it's invertible -- for most n it's actually equivalent to zero mod n

And finally, you've made no remark about why this should have anything to do with the theorem you were trying to prove.


Using the Euclidean algorithm, show that coprime numbers always have multiplicative inverses modulo each other.
But the most serious problem is that you aren't even doing the problem you were asked to do.
 
Last edited:
  • #3
miccol999
7
0
ok then, that proves that I am completely lost! how would you prove this theorem?
 

Suggested for: Euclidean algorithm

  • Last Post
Replies
3
Views
538
Replies
1
Views
430
Replies
3
Views
1K
  • Last Post
Replies
3
Views
930
  • Last Post
Replies
1
Views
683
  • Last Post
Replies
1
Views
876
  • Last Post
Replies
2
Views
763
  • Last Post
Replies
1
Views
990
  • Last Post
Replies
1
Views
1K
Top