## 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.