The Order of an Integer mod p and the Cycle Length of 1/p
\[p\]
is prime and \[gcd(a,p) =1\]
then the order of \[a \; (mod \; p)\]
is the smallest integer \[n\]
such that \[a^n \equiv 1 \; (mod \; p)\]
.When we find the reciprocal of a prime number
\[p \neq 2, \; 5\]
the decimal expansions cycles and repeats, and the length of the repeating cycle fits a pattern. The maximum length of the cycle can be \[p-1\]
because there are \[p-1\]
remainders when 1 is divided by \[p\]
. Foe ease of calculation we can put \[a=10\]
in the definition above, then length of the cycle \[n\]
is the smallest solution to \[a^n \equiv 1 \; (mod \; p)\]
.Suppose that the length of the cycle is
\[k\]
then \[10^k \equiv 1 \; (mod \; p) \rightarrow 10^k=1_qp\]
, so the length of the cycle is the number of iterations of the long division needed to obtain a remainder 1. The maximum length obtained in this way can also be obtained from Fermat's Little Theorem \[a^{p-1} \equiv 1 \; (mod \; p)\]
.The length of the actual cycle must divide
\[p-1\]
so the remainder is equal to 1 after \[p-1\]
iterations.Example:
\[\frac{1}{7}=0.142857142857...\]
and \[10^6 = 142857 \times 7+1 \equiv 1 \; (mod \; 7)\]
.Example:
\[\frac{1}{11}=0.090909090909090...\]
and \[10^10 = 0909090909 \times 11+1 \equiv 1 \; (mod \; 11)\]
.In the last example the cycle repeated five times.
