The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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!   
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.