Use permutation of units to control powers

Try

The unit classes modulo ten are 1, 3, 7, 9. Multiplying each by three gives 3, 9, 1, 7 in a different order. The product of the list has not changed, so 3⁴ times that product equals the original product modulo ten. Because every factor is invertible, the product can be cancelled, giving 3⁴≡1. This permutation mechanism is the core of Euler’s theorem.

Predict

Predict whether the same argument works for multiplication by two. It does not: two is not a unit modulo ten, and multiplying units by two leaves the unit set. The product cannot be cancelled in the same way. Coprimality is not a decorative assumption; it supplies both the permutation and the legal cancellation. Check it before shortening a large exponent.

Experiment

Inspect the unit permutation.

Unit u	3u modulo 10
1	3
3	9
7	1
9	7

Use the resulting period divisor four to compute 3²³ modulo ten. Reduce the exponent to three and verify the residue seven. Then compare powers of the nonunit two, which have different behavior.

Understand

Let U(m) be the finite multiplicative group of units modulo m and let φ(m) be its size. For gcd(a, m)=1, multiplication by a is a bijection of U(m), with inverse multiplication by a⁻¹. Multiplying all entries before and after the permutation gives a^φ(m)∏u≡∏u. The product is a unit, so cancellation proves Euler’s theorem. For prime p there are p−1 nonzero classes, all units, giving a^(p−1)≡1 when p∤a. Including the zero class yields Fermat’s form a^p≡a for every integer a. The distinction between these two forms matters when the base is divisible by p.

A multinomial route that does not assume Fermat or Euler

In expanding (x+y+z)⁵, the coefficient of x²y²z is5!/(2!2!1!)=30; the coefficient of x³y² with no z is5!/(3!2!0!)=10. Both are divisible by5. The pure powers x⁵,y⁵,z⁵ each have coefficient one. Zero exponents belong in the argument:0!=1, not a reason to omit a mixed term.

Why does primality rule out shorter nonconstant orbits?

Predict the number of different rotations of the selected word. Compare prime degree5 with composite degree4 and word0101. Track the same symbol-count vector in the coefficient table.

Degree 23456 Symbols 23 Reset

Position 1 01Position 2 01Position 3 01Position 4 01Position 5 01

Degree 5 is prime. Count vector (3, 2). Different rotations: 5.

• 01010
• 10100
• 01001
• 10010
• 00101

All words: 32. Constant words: 2. Nonconstant words: 30, remainder 0 on division by 5.

Exponent vector	Coefficient	Pure power?	Remainder modulo degree
(0, 5)	1	Yes	1
(1, 4)	5	No	0
(2, 3)	10	No	0
(3, 2) ← selected	10	No	0
(4, 1)	5	No	0
(5, 0)	1	Yes	1

At most28 coefficient rows and six displayed rotations. Coefficients count fixed-position words, while rotation classes group them; the word itself is not identified with its rotations until that equivalence is stated. Temporary exact arithmetic; no automatic proof assessment.

Let p be prime and nonnegative integers e₁,…,eᵣ sum to p. A non-pure profile has no exponent equal to p, so each eᵢ is at most p−1. The multinomial coefficient C is an integer because it counts words with those symbol multiplicities. Its factorial identity is C·∏eᵢ! = p!. No factor in the denominator product is divisible by p, whereas p divides p!. Euclid’s lemma therefore forces p to divide C. This is an integer divisibility proof, not division by a possibly noninvertible residue. Pure profiles have coefficient one and are the only exceptions.

The multinomial theorem now gives (a₁+⋯+aᵣ)ᵖ congruent to a₁ᵖ+⋯+aᵣᵖ modulo p for integers aᵢ. One Fermat deduction uses the two-term version: (a+1)ᵖ≡aᵖ+1, so induction from a=0 gives aᵖ≡a for every nonnegative integer a. For an arbitrary integer, choose its nonnegative residue modulo p and use preservation of congruence by integer powers. If p does not divide a, its inverse modulo p exists by Bézout, so cancellation gives aᵖ⁻¹≡1. The dependencies are integer counting, the multinomial theorem, Euclid/Bézout and induction; neither Euler’s theorem nor Fermat itself was used as an input.

Rotation gives a second explanation of the prime factor

Rotate a length-p word one position cyclically. Rotations preserve its symbol-count profile and partition the words into disjoint classes. A constant word has one rotation. If two different shifts of a word agree, the word is fixed by a nonzero shift s modulo p. Since p is prime, repeated additions of s visit every position: Bézout makes s invertible modulo p. Every position must therefore carry the same symbol. Consequently every nonconstant word has exactly p different rotations. Each non-pure profile is partitioned into classes of size p, proving its word count divisible by p again.

With q symbols there are qᵖ words and q constant words, so p divides qᵖ−q, another direct proof of the nonnegative Fermat congruence. This is a count of all fixed-position words before grouping them, not a claim that there are qᵖ distinct rotation classes.

At composite degree4, the word0101 has only two rotations,0101 and1010. The mixed coefficient C(4,2)=6 is not divisible by4. Thus both the factorial-cancellation proof and the prime orbit-size proof lose essential hypotheses. This does not contradict characteristic-two identities: iterating the valid square identity modulo2 gives (x+y)⁴≡x⁴+y⁴ modulo2, not modulo4. Keep the exponent and the modulus separate.

Apply

A prime must satisfy Fermat identities, but a composite can pass a particular base test. For example, 341=11·31 and 2¹⁰≡1 modulo 341, so it also satisfies 2³⁴⁰≡1. Passing one test is not a primality proof. Some composites pass every coprime-base Fermat test; stronger primality methods need additional structure and analysis. Conversely, finding a base that violates the necessary identity certifies compositeness, assuming exact modular arithmetic. This asymmetry between passing and failing is central when interpreting computational evidence.

Euler’s theorem can fail spectacularly for a nonunit. Modulo eight, two raised to φ(8)=4 is zero rather than one. The permutation proof explains the failure: multiplication by two merges several residue classes and sends some units outside the unit set. A useful modular exponentiation workflow therefore begins with a gcd check. If the base is not coprime to the modulus, separate prime-power factors and analyze each component; do not reduce an exponent modulo φ(n) mechanically. CRT can reassemble results after those component calculations are justified.

Continue

Euler’s exponent φ(m) is not always the smallest period for a given base. The next lesson defines multiplicative order and proves that it divides every exponent giving one. That sharper invariant supports primitive roots, residue tests and modular algorithms. For computation, repeated squaring avoids forming the enormous integer a^n directly. A correct power routine should be checked on nonunit bases too, even when a theorem used elsewhere requires coprimality.

Return to the number theory unit to choose a targeted retry. Continue with find the true period of a unit.