Question 967: Order Divides Phi without Automatically Equaling Phi

Original question and givens

Use exact modulus n=19 and integer a=2. 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=19 and integer a=2. 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=19; a=2

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

a=2

normalized residue=2; gcd(2,19)=1

gcd(residue,n)=1; units=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]

phi(19)=18

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

power product at k=1 = 2

product=2

a^1 mod 19=2

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

power product at k=2 = 4

product=4

a^2 mod 19=4

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

power product at k=3 = 8

product=8

a^3 mod 19=8

power product at k=4 := mul(8, 2)

power product at k=4 = 16

product=16

a^4 mod 19=16

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

power product at k=5 = 32

product=32

a^5 mod 19=13

power product at k=6 := mul(13, 2)

power product at k=6 = 26

product=26

a^6 mod 19=7

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

power product at k=7 = 14

product=14

a^7 mod 19=14

power product at k=8 := mul(14, 2)

power product at k=8 = 28

product=28

a^8 mod 19=9

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

power product at k=9 = 18

product=18

a^9 mod 19=18

power product at k=10 := mul(18, 2)

power product at k=10 = 36

product=36

a^10 mod 19=17

power product at k=11 := mul(17, 2)

power product at k=11 = 34

product=34

a^11 mod 19=15

power product at k=12 := mul(15, 2)

power product at k=12 = 30

product=30

a^12 mod 19=11

power product at k=13 := mul(11, 2)

power product at k=13 = 22

product=22

a^13 mod 19=3

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

power product at k=14 = 6

product=6

a^14 mod 19=6

power product at k=15 := mul(6, 2)

power product at k=15 = 12

product=12

a^15 mod 19=12

power product at k=16 := mul(12, 2)

power product at k=16 = 24

product=24

a^16 mod 19=5

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

power product at k=17 = 10

product=10

a^17 mod 19=10

power product at k=18 := mul(10, 2)

power product at k=18 = 20

product=20

a^18 mod 19=1

all positive k<=18: [[1, 2], [2, 4], [3, 8], [4, 16], [5, 13], [6, 7], [7, 14], [8, 9], [9, 18], [10, 17], [11, 15], [12, 11], [13, 3], [14, 6], [15, 12], [16, 5], [17, 10], [18, 1]]

first positive return to1 occurs at k=18

multiply unit 1 successively by 2

orbit=[1, 2, 4, 8, 16, 13, 7, 14, 9, 18, 17, 15, 11, 3, 6, 12, 5, 10]; length=18

complete disjoint unit orbits=[[1, 2, 4, 8, 16, 13, 7, 14, 9, 18, 17, 15, 11, 3, 6, 12, 5, 10]]

phi=18=1·18; remainder=0

Reverse checks

• S042 · premise_and_result_audit — Order is the first positive return to1; check n≥2 and coprimality first, and do not assert order=phi.
• S041 · premise_and_result_audit — Order is the first positive return to1; check n≥2 and coprimality first, and do not assert order=phi.
• S040 · premise_and_result_audit — Order is the first positive return to1; check n≥2 and coprimality first, and do not assert order=phi.
• S039 · premise_and_result_audit — Order is the first positive return to1; check n≥2 and coprimality first, and do not assert order=phi.
• S038 · premise_and_result_audit — Recompute power product at k=18 with exact rational arithmetic, not rounded decimals.
• S037 · premise_and_result_audit — Order is the first positive return to1; check n≥2 and coprimality first, and do not assert order=phi.
• S036 · premise_and_result_audit — Recompute power product at k=17 with exact rational arithmetic, not rounded decimals.
• S035 · premise_and_result_audit — Order is the first positive return to1; check n≥2 and coprimality first, and do not assert order=phi.
• S034 · premise_and_result_audit — Recompute power product at k=16 with exact rational arithmetic, not rounded decimals.
• S033 · premise_and_result_audit — Order is the first positive return to1; check n≥2 and coprimality first, and do not assert order=phi.
• S032 · premise_and_result_audit — Recompute power product at k=15 with exact rational arithmetic, not rounded decimals.
• S031 · premise_and_result_audit — Order is the first positive return to1; check n≥2 and coprimality first, and do not assert order=phi.
• S030 · premise_and_result_audit — Recompute power product at k=14 with exact rational arithmetic, not rounded decimals.
• S029 · premise_and_result_audit — Order is the first positive return to1; check n≥2 and coprimality first, and do not assert order=phi.
• S028 · premise_and_result_audit — Recompute power product at k=13 with exact rational arithmetic, not rounded decimals.
• S027 · premise_and_result_audit — Order is the first positive return to1; check n≥2 and coprimality first, and do not assert order=phi.
• S026 · premise_and_result_audit — Recompute power product at k=12 with exact rational arithmetic, not rounded decimals.
• S025 · premise_and_result_audit — Order is the first positive return to1; check n≥2 and coprimality first, and do not assert order=phi.
• S024 · premise_and_result_audit — Recompute power product at k=11 with exact rational arithmetic, not rounded decimals.
• S023 · premise_and_result_audit — Order is the first positive return to1; check n≥2 and coprimality first, and do not assert order=phi.
• S022 · premise_and_result_audit — Recompute power product at k=10 with exact rational arithmetic, not rounded decimals.
• S021 · premise_and_result_audit — Order is the first positive return to1; check n≥2 and coprimality first, and do not assert order=phi.
• S020 · premise_and_result_audit — Recompute power product at k=9 with exact rational arithmetic, not rounded decimals.
• S019 · premise_and_result_audit — Order is the first positive return to1; check n≥2 and coprimality first, and do not assert order=phi.
• S018 · premise_and_result_audit — Recompute power product at k=8 with exact rational arithmetic, not rounded decimals.
• 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 — Recompute power product at k=7 with exact rational arithmetic, not rounded decimals.
• 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

(18, 18, Yes, [[1, 2], [2, 4], [3, 8], [4, 16], [5, 13], [6, 7], [7, 14], [8, 9], [9, 18], [10, 17], [11, 15], [12, 11], [13, 3], [14, 6], [15, 12], [16, 5], [17, 10], [18, 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.