Question 966: Order Divides Phi without Automatically Equaling Phi

Original question and givens

Use exact modulus n=18 and integer a=5. 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=18 and integer a=5. 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

Step-by-step derivation

n=18; a=5

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

a=5

normalized residue=5; gcd(5,18)=1

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

phi(18)=6

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

power product at k=1 = 5

product=5

a^1 mod 18=5

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

power product at k=2 = 25

product=25

a^2 mod 18=7

power product at k=3 := mul(7, 5)

power product at k=3 = 35

product=35

a^3 mod 18=17

power product at k=4 := mul(17, 5)

power product at k=4 = 85

product=85

a^4 mod 18=13

power product at k=5 := mul(13, 5)

power product at k=5 = 65

product=65

a^5 mod 18=11

power product at k=6 := mul(11, 5)

power product at k=6 = 55

product=55

a^6 mod 18=1

all positive k<=6: [[1, 5], [2, 7], [3, 17], [4, 13], [5, 11], [6, 1]]

first positive return to1 occurs at k=6

multiply unit 1 successively by 5

orbit=[1, 5, 7, 17, 13, 11]; length=6

complete disjoint unit orbits=[[1, 5, 7, 17, 13, 11]]

phi=6=1·6; remainder=0

Reverse checks

• S018 · premise_and_result_audit — Order is the first positive return to1; check n≥2 and coprimality first, and do not assert order=phi.
• S017 · premise_and_result_audit — Order is the first positive return to1; check n≥2 and coprimality first, and do not assert order=phi.
• S016 · premise_and_result_audit — Order is the first positive return to1; check n≥2 and coprimality first, and do not assert order=phi.
• 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 — Recompute power product at k=6 with exact rational arithmetic, not rounded decimals.
• 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 — Recompute power product at k=5 with exact rational arithmetic, not rounded decimals.
• 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

(6, 6, Yes, [[1, 5], [2, 7], [3, 17], [4, 13], [5, 11], [6, 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.