Motivation
Repeated powers modulo an integer eventually repeat because there are only finitely many residue classes. For a unit, cancellation moves that repetition back to : its powers form a genuine cycle starting at the identity. This explains why large exponents can be reduced, and why the reduction is legitimate only after checking coprimality.
Definitions
Definition 3.1.1
(Euler's function and multiplicative order)
For , let be the set of units modulo and let . If , the order is the smallest positive integer with .
To justify existence of the order, among two powers agree. Multiplying by the inverse of the smaller power gives a positive power equal to . The least such exponent exists by well-ordering. The hypothesis excludes numbers such as modulo , whose positive powers never equal .
Theorem/Proposition
Theorem 3.1.2
(Euler's theorem and Fermat's little theorem)
If and , then . In particular, for a prime and , . For every integer , including multiples of , .
Theorem 3.1.3
(Order detects all return times)
If , then for every nonnegative integer , if and only if . Thus . More generally, for positive ,
Proof sketch or proof idea
Proof
(Multiplication by a unit permutes the units)
Multiplication by a unit permutes : it maps units to units, and its inverse is multiplication by . Choose representatives where . Multiplying all images yields
The product of units has an inverse, so cancellation gives Euler's theorem. For prime , every nonzero residue is a unit, hence . Multiplication by proves the all-integer version when ; when , both and vanish modulo .
Proof
(Division with remainder on the exponent)
For the order criterion write with . Then ; if this is , minimality forces . The converse follows by taking powers of . This also includes . Finally exactly when . Writing , with and , this is equivalent to . Its least positive solution is , proving the formula.
Proof X-ray
The division algorithm supplies the converse
Knowing that the order is a return exponent proves that its multiples return. To prove these are all the returns, divide any proposed exponent by the order. The remainder would also be a return exponent. Its being smaller than the least positive return forces it to be zero. This converse is what permits all later divisor tests and generator counts.
These are exact statements about units, not a claim that every order equals . Euler gives a common exponent that works for all units; individual cycles may be shorter.
Worked examples
Worked example 3.1.4
(A large exponent with a small cycle)
Modulo , and . The order is because and . Therefore since . The calculation uses an actual return exponent, not an approximation to the power.
Worked example 3.1.5
(Determining an order by excluding proper divisors)
Modulo , Fermat gives . Any proper divisor of divides or . But and , neither . Hence . The order formula then gives .
Worked example 3.1.6
(A Fermat test does not prove primality)
The composite integer satisfies , because . Thus . It passes the base- Fermat condition despite being composite. A failed test proves compositeness when the hypotheses are used correctly, but a passed test alone is not a primality certificate.
Why finite repetition becomes a cycle only for units
A finite sequence of residue states generated by repeated multiplication must eventually revisit a state. Without invertibility, the repeated segment need not include the initial value one. For example, successive positive powers of two modulo eight reach zero and remain there. The process has a short repeating tail, but it has no positive return to one. Calling the length of that tail the multiplicative order would contradict the definition and invalidate every use of cancellation in the proof.
For a unit, multiplication is a permutation of all residues, with an inverse permutation. If two powers agree, one can move backwards by the smaller exponent. The return then starts at one, and no transient part is possible. Every position in the cycle is distinct before the first return. This gives a finite-state interpretation of order that remains entirely algebraic: the essential ingredient is reversibility of the transition.
Concept lensStructural
Order as the length of a reversible orbit
Follow the orbit of one under multiplication by a fixed unit. The orbit returns to one and consists of exactly the powers before the first return. Reducing an exponent modulo the order means choosing the same position in this orbit. Euler's exponent may traverse the orbit several times; it need not equal its length.
What Euler's multiplication argument does and does not use
The proof of Euler's theorem is often compressed into “multiply the reduced residues.” The set being multiplied must be specified: it contains one representative of each unit class, not every nonzero residue. For a composite modulus there are nonzero nonunits, and including them can make the product noninvertible. The cancellation step would then have no justification. The proof works because the selected product is a unit at every stage.
There is no need to claim that multiplying the representatives preserves their numerical values or their order. It preserves their classes as a set. The representatives may change after reduction, but each unit class appears exactly once because multiplication by a unit is injective and surjective. Products of complete representative lists are consequently congruent. This is a statement about a permutation, not about a convenient ordering of the integers.
One may also regard the proof as a special finite-group argument. In that language, the units form a group under multiplication, and Euler's exponent is the size of the group. The direct permutation proof has the advantage that every cancellation is visible and no prior group theorem is required. Later algebra can organize the same reasoning more generally, but the elementary proof is already complete.
Finding an exact order efficiently after an exponent bound
Suppose an exponent has been proved to return a unit to one. The exact order must divide that exponent. It is therefore unnecessary to test every positive integer below it. Factor the exponent, and for each prime factor test whether removing one copy of that prime still leaves a return exponent. If it does, replace the bound by the smaller exponent and continue. If it does not, that prime-power contribution cannot be removed from the current bound.
The correctness of this reduction follows from divisibility of every return exponent by the order. When a prime is removed successfully, the order still divides the new bound. If no prime can be removed, a proper divisor could not remain possible: any proper divisor would omit at least one prime factor of the bound and hence divide one of the tested smaller exponents. That would contradict a failed test. The procedure makes the two responsibilities explicit: first prove a return bound, then eliminate all smaller divisor possibilities.
For an exponent with many small factors this can reduce the number of tests substantially. It does not make integer factorization free, and it is not a general complexity claim for arbitrary large moduli. The mathematical conclusion is simply that divisor structure organizes a finite search for the order. Repeated squaring can perform the power tests without expanding huge integers, provided reductions are done consistently modulo the fixed modulus.
The order of a power describes subcycles
Taking every second, third or later point in a cycle can visit fewer positions. The order-of-a-power formula measures exactly how many. If the step size and cycle length share a factor, the walk is confined to one congruence class of positions relative to that factor. If they are coprime, every position is eventually visited. This is why a power of a generator is itself a generator precisely when its exponent is coprime to the original order.
For a small model, arrange ten positions in a circle. Moving four positions each time visits five positions before returning, while moving three positions each time visits all ten. The arithmetic explanation is the same in both cases: the first positive number of moves must make the product of the step and move count divisible by ten. No geometric assumption is needed; the circle only displays the divisibility condition proved in the theorem.
Interpreting primality tests without reversing implications
Fermat's theorem has the logical form: if the modulus is prime and the base is not divisible by it, a specified power returns to one. The contrapositive says that failure of this return, with the base condition checked, rules out primality. The converse would say that a return proves primality; the worked composite example refutes it. The distinction is a logical issue, not a matter of numerical precision.
Passing tests for several bases can provide more evidence, but the elementary theorem stated here does not turn any unspecified collection of passes into a proof. A rigorous certificate needs an additional theorem with its own hypotheses. In particular, finding a short power cycle of one base only describes that base's order; it does not determine the structure of all residues or the primality of the modulus. Keeping those conclusions separate prevents an effective computation from being asked to prove more than it actually establishes.
Testing a claimed period at its starting point
A proposed exponent period for a unit can be checked at one: it is a period exactly when that power of the base equals one. If it does, multiplying by any power shows that shifting any exponent by the proposed period leaves the value unchanged. Conversely, a period valid for all nonnegative exponents must in particular preserve the value at exponent zero, so it must return to one. This equivalence ties the language of periodic sequences directly to the order definition. For a nonunit, an eventual period may work only beyond an initial segment, as the powers of two modulo eight demonstrate. Checking values late in that sequence would therefore fail to justify reduction of an early exponent. Always state whether periodicity begins at zero or only after a transient part; only the first version supports unrestricted reduction of nonnegative exponents by the claimed period.
Common mistakes
Common mistake
(Reducing exponents for a nonunit base)
Exponent reduction by requires a unit. Modulo , reducing exponent to would incorrectly identify with . An exponent congruence is not automatically a congruence of powers for arbitrary bases.
Common mistake
(Reversing Fermat or assuming maximal order)
The converse of Fermat is also false, as shows. Even for a prime modulus, the order need not be maximal: modulo , the class has order , although . To establish an order, give both a return exponent and a reason no smaller divisor works.
Counterexample mode
The all-integer form of Fermat needs a prime modulus
Claim: since holds for every integer when is prime, holds for every integer and every . Take and . Then and , while . The prime case works because the only nonunit modulo is , which every power fixes; modulo the nonunit is nonzero, yet . The repaired statement multiplies Euler's theorem by and therefore assumes ; without that hypothesis, the congruence for every integer is guaranteed here only for a prime modulus.
Summary
Euler's theorem comes from permuting the units. Division with remainder turns the smallest return exponent into a divisibility criterion for every return. The order of a power follows by reducing the integer condition .
Exercises
Quick check
(Find the order of modulo and compute the order of its cube.)
First obtain an exponent bound, then inspect its divisors.
Solution · Answer
, , and . Divisors do not return to , so the order is . The order of is , agreeing with .
Quick check
(Prove that a unit modulo has order exactly when its square is but the unit itself is not . List all such units modulo .)
An element of order need not be the residue for a composite modulus.
Solution · Answer
Order means precisely that exponent returns to while exponent does not. Conversely, if these conditions hold, the least positive return divides and is not , so is . The units modulo are , and their squares are all . Therefore are exactly the order- units.
Quick check
(Compute modulo , and explain why reducing the exponent is legitimate.)
Check coprimality before using .
Solution · Answer
Since , Euler's theorem gives , so exponents may be reduced modulo . As , we get . In fact and , so and no smaller reduction is available.