Euler's theorem

Date: 7/2/96 at 13:46:32
From: Anonymous
Subject: Euler's Theorem

I am not sure how to find the inverse of a modulo m using Euler's 
theorem.  Using the formula of my book, I end up just getting a.  The 
answers I get are also not what the book has as the answers.  Any 
hints would be appreciated.

Date: 7/2/96 at 17:30:44
From: Doctor Anthony
Subject: Re: Euler's Theorem

Euler's theorem states that if (a,m)=1 (i.e. a and m are relatively 
prime), then a^(phi(m)) == 1 (mod m)  where phi(m) is the number of 
integers less than m and prime to it.

If phi(m) = n then     a^n == 1 (mod m)

So  a*a^(n-1) == 1 (mod m)  but a*a^(-1) == 1 (mod m)

and so   a^(-1) == a^(n-1) (mod m)


-Doctor Anthony,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/