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!  http://mathforum.org/dr.math/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search