greatitself.
Continue
core28 min studyLesson 126 in Mathematics

Fermat, Euler, and multiplicative orders

Use the finite cycle of an invertible residue to reduce powers while distinguishing a period from the smallest period.

Before you begin
On this page

The question for today

What you’ll understand

  • Explain why multiplication by a unit permutes the invertible residues.
  • Apply Fermat’s and Euler’s theorems with their hypotheses intact.
  • Compute an element’s order and reduce exponents using its true period.

Repeated multiplication modulo an integer eventually repeats, but not every repeated pattern is a cycle starting at one. Invertibility makes the crucial difference. For a unit, powers form a reversible finite motion and return to one after a definite number of steps. Fermat’s and Euler’s theorems provide guaranteed return times; the multiplicative order is the earliest return. Keeping these three ideas separate prevents both incorrect exponent reduction and unnecessary computation.

A permutation gives a power identity

For modulus m at least two, let the units be the residue classes coprime to m, and write their number as φ(m). Multiplication by a fixed unit a permutes this set: an inverse recovers the input, so no two inputs can collide. Multiply all entries before and after the permutation. Each output contributes a factor a, producing a power of a times the original product.

Every factor in that product is a unit, so the entire product can be canceled modulo m. The result is Euler’s theorem. For a prime p, every nonzero class is a unit and φ(p) = p − 1, giving Fermat’s theorem. The hypothesis is essential: a residue sharing a factor with the modulus need not have any positive power equal to one. Modulo eight, powers of two reach zero rather than returning to one.

gcd⁡(a,m)=1 ⟹ aφ(m)≡1(modm);p∤a ⟹ ap−1≡1(modp)\gcd(a,m)=1\ \Longrightarrow\ a^{\varphi(m)}\equiv1\pmod m;\qquad p\nmid a\ \Longrightarrow\ a^{p-1}\equiv1\pmod p
Euler applies to any modulus m ≥ 2 and a unit a. Fermat is the prime-modulus case and assumes p is prime and does not divide a.↔ Scroll wide equations horizontally.

Find the first return, not just a return

The multiplicative order of a unit a modulo m is the smallest positive d with a to the power d congruent to one. Existence follows from Euler. Divide any other return exponent k by d, writing k = qd + r with zero at most r less than d. Then a to the power k is congruent to a to the power r. If k returns to one, minimality forces r to be zero.

Consequently the order divides every return exponent, including φ(m). To compute it, factor a known return exponent and test its divisors, or successively remove prime factors whenever a shorter exponent still returns to one. Testing a few early powers can establish a lower bound but does not by itself prove the order is maximal. A complete divisor test or a prime-factor test supplies the missing argument.

ord⁡m(a)∣φ(m),au≡av(modm) ⟺ u≡v(modord⁡m(a))\operatorname{ord}_m(a)\mid\varphi(m),\qquad a^u\equiv a^v\pmod m\ \Longleftrightarrow\ u\equiv v\pmod{\operatorname{ord}_m(a)}
Here a is a unit and u, v are nonnegative integers. Cancellation by a power of a reduces equality of powers to a return-to-one condition.↔ Scroll wide equations horizontally.

Reduce powers without constructing huge integers

Once a valid period is known, reduce the exponent modulo that period and evaluate the remaining power by repeated squaring. Squaring and reducing keep all intermediate residues small. The totient can be computed from a known prime factorization of m by removing the fractions divisible by each distinct prime. Knowing that formula does not imply factoring a large arbitrary modulus is easy, so computational costs remain separate from the theorem.

Fermat congruences are also not a complete primality test. A composite integer can pass a congruence for a particular base, and some composites pass every coprime base. Thus a failed necessary congruence can prove compositeness, while a successful one requires additional reasoning. The theorem flows from a hypothesis to a conclusion; reversing that implication without proof is a logical error, even when many small examples happen to be prime.

Work it through

Reduce a large power using a short order

Compute 7²²² modulo 20 and determine the order used in the reduction.

  1. Check gcd(7, 20) = 1, so unit power theorems apply. The units modulo 20 number φ(20) = 20(1 − 1/2)(1 − 1/5) = 8, giving a guaranteed return exponent of eight.

  2. Compute 7² ≡ 49 ≡ 9 modulo 20 and 7⁴ ≡ 9² ≡ 1. The divisors of four are one, two, and four; neither 7 nor 9 is congruent to one, so the order is exactly four.

  3. Reduce 222 modulo four to get two. Therefore 7²²² is congruent to 7² and hence 9 modulo 20. The shorter true period avoids working with any large integer power.

The result

The residue is 9, and the multiplicative order of 7 modulo 20 is 4, smaller than Euler’s guaranteed exponent 8.

The living notebook

Explore the model

Interactive lab

Interactive lab · waves

A return is different from a first return

With amplitude ratio one, compare phase differences zero and 180°. Predict that one produces reinforcement and the other cancellation, despite both being legitimate positions in a periodic cycle. The lab varies phase in two fixed-frequency waves; it does not generate modular powers. Use it to distinguish a cycle position from a return, then verify integer orders by exact residues.

A return is different from a first returnTwo waves share the same frequency and wave number. Playback advances t in sin(2x − t) + a sin(2x − t + phase). Current readings: Sum at x = 0: 0.866; Resultant amplitude: 1.732; Phase difference: 60°. All parameters are adjustable with the labeled controls below.−3.14−1.5701.573.14−3.4−1.701.73.4x · radiansAmplitude
SumFirst componentSecond component
Sum at x = 0
0.866
Resultant amplitude
1.732
Phase difference
60°
t = 0 s

Two waves share the same frequency and wave number. Playback advances t in sin(2x − t) + a sin(2x − t + phase). Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.

Look forA claimed period needs a return check; a smallest period also requires ruling out shorter returns.

Pause & reason

Check your understanding

The residue a is a unit modulo m and a⁶ ≡ 1. Which order is impossible?

Your turn

Try it yourself

Find the order of 2 modulo 9 and use it to compute 2¹⁰⁰ modulo 9. Explain why Euler cannot be applied to base 3 for the same modulus.

Take a moment to make a prediction or work it out on paper. Open a hint when you need one.

Give me a hint

Use φ(9) = 6, test its proper divisors, and check the gcd for each proposed base.

Compare with the solution

The proper positive divisors of six are one, two, and three. The powers 2, 4, and 8 are not one modulo nine, while 2⁶ = 64 is one, so the order is six. Since 100 leaves remainder four modulo six, 2¹⁰⁰ ≡ 2⁴ ≡ 16 ≡ 7 modulo nine. Base three has gcd three with nine, so it is not a unit; indeed 3² is zero modulo nine and no positive power returns to one.

Keep the idea

Take it with you

  • Euler and Fermat require invertibility, with primality additionally required in Fermat’s version.
  • The multiplicative order divides any valid return exponent.
  • A congruence that follows from primality does not automatically prove primality.

Read further

Original sources and deeper explanations to follow at your own pace.

Optional progress, saved in this browser when available. Revisit any lesson at any time.

Lesson not marked complete.