Euler's theoremDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/