Euler's Theorem

Theorem: If  
\[a \in \mathbb{Z}_n^*\]
\[a^{\phi(n)} = 1 \pmod{n}\]
This reduces to Fermat’s Little Theorem when  
  is prime.
Proof: Let  
\[m = \phi(n)\]
, and label the units  
. Consider the sequence  
\[a u_1,...,a u_m\]
 (we multiply each unit by  
). If  
\[a u_i = a u_j\]
, then multiplying by  
 (which exists since 
 is a unit) shows  
\[u_i = u_j\]
, hence the members of the sequence are distinct. Furthermore products of units must also be units, hence  
\[a u_1, ..., a u_m\]
 must be  
 in some order.
Multiplying all the units together gives  
\[ a u_1 ... a u_m = u_1 ... u_m.\]
Rearranging yields  
\[ a^{\phi(n)} = a^m = (u_1 ... u_m)(u_1 ... u_m)^{-1} = 1 \]
Similarly Euler’s Theorem also gives an alternative way to compute inverses. For  
\[a \in \mathbb{Z}_n^*\]
  can be computed as  
. This is efficient as we may use repeated squaring, but Euclid’s algorithm is still faster (why?) and does not require one to compute  
These theorems do not tell us the order of a given unit  
 but they do narrow it down: let  
 be the order of  
. If we know  
\[a^y = 1\]
 by Euclid’s algorithm we can find  
\[m, n\]
 such that  
\[ d = m x + n y \]
\[d = \gcd(x, y)\]
. Then  
\[ a^d = a^{m x + n y} = (a^x)^m (a^y)^n = 1 \]

thus sinc e 
\[d \le x\]
 we must have  
\[d = x\]
 is the smallest positive integer for which  
\[a^x = 1\]
), and hence  
 must be a divisor of  
. Thus by Euler’s Theorem, the order of  
These statements are in fact trivial corollaries of Lagrange’s Theorem from group theory. Of course Fermat and Euler died long before group theory was discovered.

Add comment

Security code