Proof Thnat Order of an Integer Modulo p Divides p-1
If
\[a\]
has order \[c\]
modulo \[p \gt 3\]
where \[p\]
is a prime, and \[a^k \gt 1 \; (mod \; p)\]
then \[c | k\]
. In particular \[c | (p-1)\]
.Proof
By the Division Algorithm we can write
\[k=qc+r, \; 0 \le r \lt c\]
.\[a^k = a^{qc+r} =(a^c)^q \times a^r \equiv 1^q \times a^r \; (mod \; p) \equiv a^r \; (mod \; p)\]
\[a^k \equiv a^r \equiv 1 \; (mod \; p)\]
Therefore
\[r=0\]
otherwise the order of \[a\]
would be less than \[c\]
. Hence \[c | k\]
.Fermat's Little Theorem gives
\[a^{p-1} \equiv 1 \; (mod \; p)\]
\[c | (p-1)\]
. 
