Proving TheoremsDate: 07/20/2001 at 06:55:45 From: Condensate Subject: How to prove Euler's Theorem, i.e., a^f(n) = 1 (mod n) where f(n) is the phi function. Dear Dr. Math, I would like to ask two questions: (1) How to prove Euler's Theorem, i.e., let f(x) be the Euler phi-function. Then a^f(n) = 1 (mod n) for any integer a. (2) Is there a theorem stating that 'If (a, p) = 1, then a^(p-1) = 1 (mod p)? (I think it is a bit different from Fermat's Little Theorem.) If so, can you give me a proof of it? Thanks for your help! Condensate Date: 07/20/2001 at 14:30:57 From: Doctor Rob Subject: Re: How to prove Euler's Theorem, i.e., a^f(n) = 1 (mod n) where f(n) is the phi function. Thanks for writing to Ask Dr. Math, Condensate. Your statement of Euler's Theorem is incorrect. It doesn't work for any integer a. For example, try a = 2 and n = 4. You must add the condition that (a,n) = 1. (1) Look at the multiplicative group G of integers x such that 1 <= x < n and (x,n) = 1, with multiplication done modulo n. By definition, f(n) = #G = the number of elements in G. Let A = a (mod n), where 1 <= A < n, so A is in G. Now consider the subgroup H of G consisting of powers of A. By Lagrange's Theorem, #H | #G. Then #H is the order of A, ord(A), so ord(A) | f(n). Since A^ord(A) = 1 (mod n) by the definition of the order of an element of a group, that implies that A^f(n) = 1 (mod n), which in turn implies that a^f(n) = 1 (mod n). Lagrange's Theorem is proved by showing that if H is a subgroup of a finite group G, then any two left cosets of H are disjoint or coincident; all left cosets of H have the same size; and the left cosets of H exhaust G. Thus G can be split into a number m of sets all of whose sizes are #H. Thus #G = m*#H, and so #H | #G. (2) This is false. Try a = 3 and p = 4. If you add the condition that p is prime, then it is Fermat's Little Theorem, and so it is true. - Doctor Rob, The Math Forum 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/