# Question 964: Order Divides Phi without Automatically Equaling Phi

[Return to catalogue page 5](https://ocme.evemisslab.com/en/questions/page/5/)

[← Question derivation index](https://ocme.evemisslab.com/en/questions/) · [Original question batch](https://ocme.evemisslab.com/en/practice/batch-20261015-advance-20261116-r07-multiplicative-order-mod-n-foundations/#q-20261015-advance-20261116-r07-multiplicative-order-mod-n-0064)

This teaching derivation has second-context AI mathematical and bilingual semantic review, limited to the model and assumptions stated in this question. It has no human review or new Lean proof and does not promote the original question or MKO to Canonical truth.

P1000-0964 · q-20261015-advance-20261116-r07-multiplicative-order-mod-n-0064



## Original question and givens

Use exact modulus n=16 and integer a=3. First require n≥2 and normalize a modulo n into the canonical nonnegative residue, then require gcd(a,n)=1. The order is the least positive return exponent, not any return. Give (order, phi, order_divides_phi, power_rows, certificate).


- G001 — Use exact modulus n=16 and integer a=3. First require n≥2 and normalize a modulo n into the canonical nonnegative residue, then require gcd(a,n)=1. The order is the least positive return exponent, not any return. Give (order, phi, order_divides_phi, power_rows, certificate).





## Definition and scope

The units split into equal-length orbits, so the order divides phi(n); neither equality nor a primitive root follows.


- [mko-multiplicative-order-mod-n](https://ocme.evemisslab.com/en/mko/mko-multiplicative-order-mod-n/)





## Step-by-step derivation

S001 · impliesBefore

n=16; a=3

After

order is defined here only for n≥2 and units modulo n

Conditions: none

Fix this node's domain first; do not confuse additive and multiplicative order.

Step identifiers and dependenciesRule: order_domain · Uses: G001





S002 · impliesBefore

a=3

After

normalized residue=3; gcd(3,16)=1

Conditions: none

Normalize even a negative representative into[0,n), then test coprimality.

Step identifiers and dependenciesRule: normalize_and_qualify · Uses: G001, S001





S003 · impliesBefore

gcd(residue,n)=1; units=[1, 3, 5, 7, 9, 11, 13, 15]

After

phi(16)=8

Conditions: none

Enumerate every coprime class from0 through n−1; phi is the complete unit-carrier size.

Step identifiers and dependenciesRule: complete_unit_enumeration · Uses: G001, S002





S004 · calculationBefore

power product at k=1 := mul(1, 3)

After

power product at k=1 = 3

Conditions: none

Multiply the preceding power representative by the same normalized base.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S003





S005 · impliesBefore

product=3

After

a^1 mod 16=3

Conditions: none

The remainder is the next full power representative.

Step identifiers and dependenciesRule: reduce_next_power · Uses: G001, S004





S006 · calculationBefore

power product at k=2 := mul(3, 3)

After

power product at k=2 = 9

Conditions: none

Multiply the preceding power representative by the same normalized base.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S005





S007 · impliesBefore

product=9

After

a^2 mod 16=9

Conditions: none

The remainder is the next full power representative.

Step identifiers and dependenciesRule: reduce_next_power · Uses: G001, S006





S008 · calculationBefore

power product at k=3 := mul(9, 3)

After

power product at k=3 = 27

Conditions: none

Multiply the preceding power representative by the same normalized base.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S007





S009 · impliesBefore

product=27

After

a^3 mod 16=11

Conditions: none

The remainder is the next full power representative.

Step identifiers and dependenciesRule: reduce_next_power · Uses: G001, S008





S010 · calculationBefore

power product at k=4 := mul(11, 3)

After

power product at k=4 = 33

Conditions: none

Multiply the preceding power representative by the same normalized base.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S009





S011 · impliesBefore

product=33

After

a^4 mod 16=1

Conditions: none

The remainder is the next full power representative.

Step identifiers and dependenciesRule: reduce_next_power · Uses: G001, S010





S012 · impliesBefore

all positive k<=4: [[1, 3], [2, 9], [3, 11], [4, 1]]

After

first positive return to1 occurs at k=4

Conditions: none

Every smaller positive exponent has been checked not to return to1; the identity at exponent0 is not the order.

Step identifiers and dependenciesRule: least_positive_return · Uses: G001, S011





S013 · impliesBefore

multiply unit 1 successively by 3

After

orbit=[1, 3, 9, 11]; length=4

Conditions: none

Multiplication by a unit is bijective; an earlier return would cancel the starting unit and contradict the least positive order.

Step identifiers and dependenciesRule: unit_orbit_partition · Uses: G001, S012





S014 · impliesBefore

multiply unit 5 successively by 3

After

orbit=[5, 15, 13, 7]; length=4

Conditions: none

Multiplication by a unit is bijective; an earlier return would cancel the starting unit and contradict the least positive order.

Step identifiers and dependenciesRule: unit_orbit_partition · Uses: G001, S013





S015 · impliesBefore

complete disjoint unit orbits=[[1, 3, 9, 11], [5, 15, 13, 7]]

After

phi=8=2·4; remainder=0

Conditions: none

The unit set is partitioned into equal-length orbits, so order divides phi; equality or a primitive-root claim does not follow.

Step identifiers and dependenciesRule: order_divides_totient · Uses: G001, S014









## Reverse checks


- S015 · premise_and_result_audit — Order is the first positive return to1; check n≥2 and coprimality first, and do not assert order=phi.
- S014 · premise_and_result_audit — Order is the first positive return to1; check n≥2 and coprimality first, and do not assert order=phi.
- S013 · premise_and_result_audit — Order is the first positive return to1; check n≥2 and coprimality first, and do not assert order=phi.
- S012 · premise_and_result_audit — Order is the first positive return to1; check n≥2 and coprimality first, and do not assert order=phi.
- S011 · premise_and_result_audit — Order is the first positive return to1; check n≥2 and coprimality first, and do not assert order=phi.
- S010 · premise_and_result_audit — Recompute power product at k=4 with exact rational arithmetic, not rounded decimals.
- S009 · premise_and_result_audit — Order is the first positive return to1; check n≥2 and coprimality first, and do not assert order=phi.
- S008 · premise_and_result_audit — Recompute power product at k=3 with exact rational arithmetic, not rounded decimals.
- S007 · premise_and_result_audit — Order is the first positive return to1; check n≥2 and coprimality first, and do not assert order=phi.
- S006 · premise_and_result_audit — Recompute power product at k=2 with exact rational arithmetic, not rounded decimals.
- S005 · premise_and_result_audit — Order is the first positive return to1; check n≥2 and coprimality first, and do not assert order=phi.
- S004 · premise_and_result_audit — Recompute power product at k=1 with exact rational arithmetic, not rounded decimals.
- S003 · premise_and_result_audit — Order is the first positive return to1; check n≥2 and coprimality first, and do not assert order=phi.
- S002 · premise_and_result_audit — Order is the first positive return to1; check n≥2 and coprimality first, and do not assert order=phi.
- S001 · premise_and_result_audit — Order is the first positive return to1; check n≥2 and coprimality first, and do not assert order=phi.





## Result

(4, 8, Yes, [[1, 3], [2, 9], [3, 11], [4, 1]], ord_n_a_divides_phi_n_without_claiming_equality_or_primitive_root)

The full substitutions and premise audits recover the original answer, retaining its field order and verdict meanings.





## This question review and source binding

Review date: 2026-10-26

Original questions, answers, step expressions, numeric ASTs and historical records are retained. Source candidate labels remain historical and are not overwritten as formal proof.

Source hashes and review receipts
- input commit: 0f7be61e2c22317a4075561dc822c87d881a50db
- original question SHA-256: 46a502a5f1e84324f23f210cf6fb27d8e249ce4a58a13d5a815eb26261a6768f
- candidate record SHA-256: cb5cd333581c214c98cc35eeb7e6a843838f660192ef79a7af54656d2f123ad8
- semantic review receipt SHA-256: 6c2c6d46aded7582a11ac41a8c0b3bdde2669a53bdb6e796eea2039994a02772
- question-first witness SHA-256: 77e43898df9efdbf8094ad81fe4ab91cf4b4bd82f481eb9b4699b73cb4da612b
- Lean: NOT_RUN · human review: NOT_PERFORMED

[Same-source full JSON](https://ocme.evemisslab.com/data/question-derivations/questions/q-20261015-advance-20261116-r07-multiplicative-order-mod-n-0064.json)