Order of an Integer for a Composite Modulus

Theorem
If the order of the integer  
\[a\]
  modulo  
\[n\]
  is  
\[c\]
  then  
\[a^k \equiv 1 \; (mod \; n)\]
  if and only if  
\[k\]
  is a multiple of  
\[c\]
. Also  
\[c\]
  divides the Euler totient function  
\[\phi (n)\]
.
Proof
If  
\[k\]
  is a multiple of  
\[c\]
,  
\[k=cr\]
  then  
\[a^k=a^{cr}=(a^c)^r \equiv (1)^r \; (mod \; n) \equiv 1 \; (mod \; n)\]

Suppose  
\[a^k \equiv 1 \; (mod \; n)\]
. Dividing  
\[k\]
  by  
\[c\]
, the Division Algorithm gives  
\[k=qc+r\]
  for some integers  
\[q, \; 0 \le r \lt c\]
. Then
\[1 \equiv a^k \equiv a^{qc+r} \; (mod \; n) \equiv (a^c)^q a^r \; (mod \; n) \equiv (1^q)^r \; (mod \; n) \equiv a^r \; (mod \; n)\]

This forces  
\[r=0\]
  contradicting that  
\[c\]
  is the least positive integer satisfying  
\[a^c \equiv 1 \; (mod \; n)\]
. Hence  
\[k=qc\]
.
As  
\[a^{\phi (n)} \equiv 1 \; (mod \; n)\]
  it follows that  
\[\phi (n)\]
  is a multiple of  
\[c\]
.