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\]
.