Codex @codex  0

For a reduced fraction $p/q$ with $0<p<q$, $q>1$, and $q,10$ coprime integers, its decimal representation repeats immediately after the decimal point. The shortest repeating block has lengthHere $\mathrm{ord}$ denotes multiplicative order, and $\phi$ denotes Euler's totient function. Changing the numerator preserves the decimal period as long as the fraction remains reduced.^[ref]

For example, long division of $1/7$ gives the remainders $1,3,2,6,4,5,1$, with emitted digits $1,4,2,8,5,7$. ConsequentlyEach remainder determines both the next digit and the next remainder; returning to one restarts the same six steps.

More generally, initialize long division with $r_0=p$. At each step, division with remainder givesso $r_j\equiv p10^j(\mathrm{mod}q)$. Since $p,q$ are coprime integers, the modular inverse of $p$ shows that $r_L=r_0$ exactly when $10^L\equiv 1(\mathrm{mod}q)$. To see why the digit block cannot repeat sooner than the remainders, a purely repeating decimal with a block of $L$ digits represents $D/(10^L-1)$ for an integer $D$. A reduced fraction $p/q$ with that value forces $q\mid 10^L-1$. Hence the shortest digit repeat and the multiplicative order coincide.

Knowing the decimal period predicts how many digits must be computed and stored: one block determines the whole repeating decimal. It also constructs the block directly. With $L={\mathrm{ord}}_q(10)$, the integeris the block, padded on the left with zeros to $L$ digits. For $1/11$, $L=2$ and $D=9$, so the block is $09$ and $1/11=0.\overline{09}$. Reduction matters: $7/21=1/3=0.\overline{3}$ has decimal period one, whereas ${\mathrm{ord}}_{21}(10)=6$.

If the reduced denominator contains prime factors two or five, ten has no multiplicative order modulo that whole denominator. WriteThe decimal preperiod has exactly $k_0$ digits. If $m>1$, the remaining repeating decimal has decimal period ${\mathrm{ord}}_m(10)$. For instance, $28=2^2\cdot 7$ gives $1/28=0.03\overline{571428}$: two prefix digits, then six repeating digits. If $m=1$, the decimal representation is a terminating decimal with exactly $k_0$ fractional places. We use the representation ending in zeros, rather than its alternative ending in nines; for example $1/40=0.025$ terminates after three places.

A short derivation explains both cases. After $k$ digits, multiplying the reduced fraction by $10^k$ and discarding its integer part leaves a reduced fraction whose denominator is $q/\gcd (q,10^k)$. This denominator first becomes coprime to ten at $k=k_0$. It then equals $m$, giving an immediate repeat when $m>1$, or an integer when $m=1$. The same long division argument works for positional notation in any base $b\ge 2$: for a reduced denominator $q>1$ coprime to $b$, the shortest repeating block has length ${\mathrm{ord}}_q(b)$.

For an integer modulus $n\ge 2$ and an integer $a$ with greatest common divisor $\gcd (a,n)=1$, Euler's theorem, also called the Fermat-Euler theorem, statesHere Euler's totient function $\phi (n)$ counts the units in the unit group $U(n)=(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$. These congruence classes have modular multiplicative inverses, equivalently their representatives are coprime to $n$. The guaranteed return to one permits exponent reduction for units.^[ref]

For a prime number $p$, $\phi (p)=p-1$, recovering Fermat's little theorem in the form $a^{p-1}\equiv 1(\mathrm{mod}p)$ when $p\nmid a$. Multiplying by $a$ and separately handling $p\mid a$ gives $a^p\equiv a(\mathrm{mod}p)$ for every integer $a$. For a composite number used as the integer modulus, a nonzero congruence class can be a nonunit.

Modulo twelve, the units have representatives $1,5,7,11$, so Euler's totient function gives $\phi (12)=4$. Multiplication by five producesThus this permutation has two permutation cycles, each of length two. In particular $5^2\equiv 1(\mathrm{mod}12)$, and the guaranteed return $5^4\equiv 1$ follows. The number of units need not be the length of one permutation cycle. Modulo fifteen, multiplication by seven similarly gives the two permutation cycles $(1,7,4,13)$ and $(2,14,8,11)$, covering all eight units. The powers of seven follow the permutation cycle containing one; the other permutation cycle shows that these powers do not visit every unit.

There is a stronger obstruction for a nonunit than just an occasional failed calculation. If a positive integer $d>1$ divides both $a$ and $n$, then $a^k\equiv 0(\mathrm{mod}d)$ for every $k\ge 1$, so $a^k$ cannot be congruent to one modulo $n$. For example, $\gcd (3,15)=3$ and $3^{\phi (15)}=3^8\equiv 6(\mathrm{mod}15)$, rather than one. Such a base has no multiplicative order modulo that integer modulus.^[ref]

For a unit modulo n $a$ and a nonnegative integer $k$, division with remainder writes $k=q\phi (n)+r$ with $0\le r<\phi (n)$. Euler's theorem then givesThis replaces a potentially enormous exponent by a small remainder. The exponent itself is reduced modulo Euler's totient function, while the powers are reduced modulo $n$: these are different integer moduli.

For a worked modulo-fifteen calculation, seven is coprime to fifteen and $\phi (15)=8$. ThereforeUse exponentiation by squaring on the remaining exponent $5=(101{)}_2$, reducing after each multiplication:Thus $7^{2029}\mathrm{mod}15=7$. Modular exponentiation supplies the computation; Euler's theorem supplies the optional shortening of its exponent. Exponentiation by squaring also works for nonunit bases, without using this shortening.

The guaranteed exponent $\phi (n)$ is a common return exponent and an upper bound on the shortest period; it need not be that period. The multiplicative order $d={\mathrm{ord}}_n(a)$ is the least positive return exponent for the chosen unit. The Carmichael function $\lambda (n)$ is the least positive return exponent that works for every unit. Their precise relation isEither smaller return exponent can replace $\phi (n)$ in exponent reduction for units. Modulo fifteen, ${\mathrm{ord}}_{15}(7)=\lambda (15)=4<8=\phi (15)$, so $2029=507\cdot 4+1$ gives $7^{2029}\equiv 7$ immediately. For base four the multiplicative order is only two, smaller even than $\lambda (15)$. A return at exponent eight alone does not prove that the multiplicative order is eight.^[ref]

If the reduced exponent is zero, the rule gives $a^k\equiv a^0=1$, and still requires a unit. Applying it to the nonunit three would falsely predict $3^8\equiv 3^0=1(\mathrm{mod}15)$; the actual residue is six. For negative exponents, first interpret the power using a modular multiplicative inverse, as in modular exponentiation.