# Question 20076: Multiplication by a Unit Permutes the Complete Reduced Residues [Return to catalogue page 101](https://ocme.evemisslab.com/en/questions/page/101/) [← Question derivation index](https://ocme.evemisslab.com/en/questions/) · [Original question batch](https://ocme.evemisslab.com/en/practice/batch-20261014-advance-20261107-r06-euler-theorem-number-theory-foundations/#q-20261014-advance-20261107-r06-euler-theorem-number-theory-0026) 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. R0039-20076 · q-20261014-advance-20261107-r06-euler-theorem-number-theory-0026 ## Original question and givens Use integer modulus n=5≥2 and original integer base a=2. Compute the positive normalized residue, gcd, Euler totient and modular power exactly by integer arithmetic. Euler's congruence requires gcd(a,n)=1 and is modulo n, not unrestricted integer equality; no primality conclusion follows from a passing congruence. Give (units, sorted_mapped_units, permutation, certificate). - G001 — Use integer modulus n=5≥2 and original integer base a=2. Compute the positive normalized residue, gcd, Euler totient and modular power exactly by integer arithmetic. Euler's congruence requires gcd(a,n)=1 and is modulo n, not unrestricted integer equality; no primality conclusion follows from a passing congruence. Give (units, sorted_mapped_units, permutation, certificate). ## Definition and scope Use the original question domain, assumptions and cited MKO definitions. This item has second-context mathematical and bilingual review, with the model, answer and every arithmetic step independently recomputed from the original parameters; the source question remains a candidate. - [mko-euler-theorem-number-theory](https://ocme.evemisslab.com/en/mko/mko-euler-theorem-number-theory/) ## Step-by-step derivation S001 · impliesBefore source operation=eulerthm-unit-permutation;original snapshot and mathematics retained After explicit ordered source output fields=[units, sorted_mapped_units, permutation, certificate] Conditions: none Retain the historical interface marker in the original snapshot while listing ordered source fields here,without JavaScript or external lookup.Field labels are not additional mathematical evidence,and No retains the source claim scope. Step identifiers and dependenciesRule: source_ordered_interface_explicit_without_javascript · Uses: G001 S002 · calculationBefore Euler ORIGINAL signed base normalization exact quotient := div(2, 5) After Euler ORIGINAL signed base normalization exact quotient = 2/5 Conditions: none Substitute original roles and established intermediates exactly,retaining indices,signs,denominators and the proof's applicability conditions. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S001 S003 · calculationBefore Euler ORIGINAL signed base normalization floor quotient multiple := mul(0, 5) After Euler ORIGINAL signed base normalization floor quotient multiple = 0 Conditions: none Substitute original roles and established intermediates exactly,retaining indices,signs,denominators and the proof's applicability conditions. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S002 S004 · calculationBefore Euler ORIGINAL signed base normalization normalized remainder := sub(2, 0) After Euler ORIGINAL signed base normalization normalized remainder = 2 Conditions: none Substitute original roles and established intermediates exactly,retaining indices,signs,denominators and the proof's applicability conditions. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S003 S005 · impliesBefore Euler ORIGINAL signed base normalization:ORIGINAL signed integer=2;modulus=5;exact ratio=2/5;floor quotient=0 After value=q*n+remainder;normalized residue=2 in[0,5);same congruence class,NOT absolute-value replacement Conditions: none Use the floor quotient for a positive modulus,retaining the congruence class of a negative base rather than replacing it by abs(a).Equal residues mean congruence modulo n,not equality of original integers. Step identifiers and dependenciesRule: euler_exact_signed_remainder_not_abs_or_integer_equality · Uses: G001, S004 S006 · impliesBefore Euler ORIGINAL base applicability gcd:ORIGINAL gcd inputs=[2, 5];nonnegative initial pair=[2, 5] After ALL exact Euclidean rows[left,right,q,r]=[[2, 5, 0, 2], [5, 2, 2, 1], [2, 1, 2, 0]];terminal gcd=1 Conditions: none Each row has left=q*right+r with0≤r=2 Conditions: none Test gcd1 for every representative to obtain the complete unit set,which contains1.The source totient count uses1..n while the unit list uses0..n−1.For n≥2 both swapped endpoints0 and n are nonunits,so the counts agree without assuming a prime modulus. Step identifiers and dependenciesRule: euler_full_units_totient_count_convention_not_prime_only · Uses: G001, S012 S014 · calculationBefore Euler ACTUAL base-unit inverse product := mul(2, 3) After Euler ACTUAL base-unit inverse product = 6 Conditions: none Substitute original roles and established intermediates exactly,retaining indices,signs,denominators and the proof's applicability conditions. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S013 S015 · calculationBefore Euler ACTUAL inverse check exact quotient := div(6, 5) After Euler ACTUAL inverse check exact quotient = 6/5 Conditions: none Substitute original roles and established intermediates exactly,retaining indices,signs,denominators and the proof's applicability conditions. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S014 S016 · calculationBefore Euler ACTUAL inverse check floor quotient multiple := mul(1, 5) After Euler ACTUAL inverse check floor quotient multiple = 5 Conditions: none Substitute original roles and established intermediates exactly,retaining indices,signs,denominators and the proof's applicability conditions. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S015 S017 · calculationBefore Euler ACTUAL inverse check normalized remainder := sub(6, 5) After Euler ACTUAL inverse check normalized remainder = 1 Conditions: none Substitute original roles and established intermediates exactly,retaining indices,signs,denominators and the proof's applicability conditions. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S016 S018 · impliesBefore Euler ACTUAL inverse check:ORIGINAL signed integer=6;modulus=5;exact ratio=6/5;floor quotient=1 After value=q*n+remainder;normalized residue=1 in[0,5);same congruence class,NOT absolute-value replacement Conditions: none Use the floor quotient for a positive modulus,retaining the congruence class of a negative base rather than replacing it by abs(a).Equal residues mean congruence modulo n,not equality of original integers. Step identifiers and dependenciesRule: euler_exact_signed_remainder_not_abs_or_integer_equality · Uses: G001, S017 S019 · impliesBefore ACTUAL modulus n=5;gcd(original a=2,n)=1;normalized base=2;ACTUAL inverse=3;COMPLETE U(n)=[1, 2, 3, 4] After for ANY r in U(n),a*r remains a unit;actual inverse makes multiplication injective;finite self-injection on U(n) is surjective,so a*U(n)=U(n) Conditions: none The reverse product of inverses inverts a product of units,so multiplication by a stays in U(n).Its actual inverse proves injectivity and a finite self-injection is surjective.The modulus may be composite;not every nonzero residue must be a unit. Step identifiers and dependenciesRule: euler_all_unit_residue_permutation_composite_allowed · Uses: G001, S018 S020 · calculationBefore Euler ORIGINAL a times unit representative1 := mul(2, 1) After Euler ORIGINAL a times unit representative1 = 2 Conditions: none Substitute original roles and established intermediates exactly,retaining indices,signs,denominators and the proof's applicability conditions. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S019 S021 · calculationBefore Euler unit representative1 raw image exact quotient := div(2, 5) After Euler unit representative1 raw image exact quotient = 2/5 Conditions: none Substitute original roles and established intermediates exactly,retaining indices,signs,denominators and the proof's applicability conditions. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S020 S022 · calculationBefore Euler unit representative1 raw image floor quotient multiple := mul(0, 5) After Euler unit representative1 raw image floor quotient multiple = 0 Conditions: none Substitute original roles and established intermediates exactly,retaining indices,signs,denominators and the proof's applicability conditions. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S021 S023 · calculationBefore Euler unit representative1 raw image normalized remainder := sub(2, 0) After Euler unit representative1 raw image normalized remainder = 2 Conditions: none Substitute original roles and established intermediates exactly,retaining indices,signs,denominators and the proof's applicability conditions. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S022 S024 · impliesBefore Euler unit representative1 raw image:ORIGINAL signed integer=2;modulus=5;exact ratio=2/5;floor quotient=0 After value=q*n+remainder;normalized residue=2 in[0,5);same congruence class,NOT absolute-value replacement Conditions: none Use the floor quotient for a positive modulus,retaining the congruence class of a negative base rather than replacing it by abs(a).Equal residues mean congruence modulo n,not equality of original integers. Step identifiers and dependenciesRule: euler_exact_signed_remainder_not_abs_or_integer_equality · Uses: G001, S023 S025 · calculationBefore Euler ORIGINAL a times unit representative2 := mul(2, 2) After Euler ORIGINAL a times unit representative2 = 4 Conditions: none Substitute original roles and established intermediates exactly,retaining indices,signs,denominators and the proof's applicability conditions. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S024 S026 · calculationBefore Euler unit representative2 raw image exact quotient := div(4, 5) After Euler unit representative2 raw image exact quotient = 4/5 Conditions: none Substitute original roles and established intermediates exactly,retaining indices,signs,denominators and the proof's applicability conditions. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S025 S027 · calculationBefore Euler unit representative2 raw image floor quotient multiple := mul(0, 5) After Euler unit representative2 raw image floor quotient multiple = 0 Conditions: none Substitute original roles and established intermediates exactly,retaining indices,signs,denominators and the proof's applicability conditions. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S026 S028 · calculationBefore Euler unit representative2 raw image normalized remainder := sub(4, 0) After Euler unit representative2 raw image normalized remainder = 4 Conditions: none Substitute original roles and established intermediates exactly,retaining indices,signs,denominators and the proof's applicability conditions. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S027 S029 · impliesBefore Euler unit representative2 raw image:ORIGINAL signed integer=4;modulus=5;exact ratio=4/5;floor quotient=0 After value=q*n+remainder;normalized residue=4 in[0,5);same congruence class,NOT absolute-value replacement Conditions: none Use the floor quotient for a positive modulus,retaining the congruence class of a negative base rather than replacing it by abs(a).Equal residues mean congruence modulo n,not equality of original integers. Step identifiers and dependenciesRule: euler_exact_signed_remainder_not_abs_or_integer_equality · Uses: G001, S028 S030 · calculationBefore Euler ORIGINAL a times unit representative3 := mul(2, 3) After Euler ORIGINAL a times unit representative3 = 6 Conditions: none Substitute original roles and established intermediates exactly,retaining indices,signs,denominators and the proof's applicability conditions. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S029 S031 · calculationBefore Euler unit representative3 raw image exact quotient := div(6, 5) After Euler unit representative3 raw image exact quotient = 6/5 Conditions: none Substitute original roles and established intermediates exactly,retaining indices,signs,denominators and the proof's applicability conditions. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S030 S032 · calculationBefore Euler unit representative3 raw image floor quotient multiple := mul(1, 5) After Euler unit representative3 raw image floor quotient multiple = 5 Conditions: none Substitute original roles and established intermediates exactly,retaining indices,signs,denominators and the proof's applicability conditions. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S031 S033 · calculationBefore Euler unit representative3 raw image normalized remainder := sub(6, 5) After Euler unit representative3 raw image normalized remainder = 1 Conditions: none Substitute original roles and established intermediates exactly,retaining indices,signs,denominators and the proof's applicability conditions. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S032 S034 · impliesBefore Euler unit representative3 raw image:ORIGINAL signed integer=6;modulus=5;exact ratio=6/5;floor quotient=1 After value=q*n+remainder;normalized residue=1 in[0,5);same congruence class,NOT absolute-value replacement Conditions: none Use the floor quotient for a positive modulus,retaining the congruence class of a negative base rather than replacing it by abs(a).Equal residues mean congruence modulo n,not equality of original integers. Step identifiers and dependenciesRule: euler_exact_signed_remainder_not_abs_or_integer_equality · Uses: G001, S033 S035 · calculationBefore Euler ORIGINAL a times unit representative4 := mul(2, 4) After Euler ORIGINAL a times unit representative4 = 8 Conditions: none Substitute original roles and established intermediates exactly,retaining indices,signs,denominators and the proof's applicability conditions. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S034 S036 · calculationBefore Euler unit representative4 raw image exact quotient := div(8, 5) After Euler unit representative4 raw image exact quotient = 8/5 Conditions: none Substitute original roles and established intermediates exactly,retaining indices,signs,denominators and the proof's applicability conditions. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S035 S037 · calculationBefore Euler unit representative4 raw image floor quotient multiple := mul(1, 5) After Euler unit representative4 raw image floor quotient multiple = 5 Conditions: none Substitute original roles and established intermediates exactly,retaining indices,signs,denominators and the proof's applicability conditions. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S036 S038 · calculationBefore Euler unit representative4 raw image normalized remainder := sub(8, 5) After Euler unit representative4 raw image normalized remainder = 3 Conditions: none Substitute original roles and established intermediates exactly,retaining indices,signs,denominators and the proof's applicability conditions. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S037 S039 · impliesBefore Euler unit representative4 raw image:ORIGINAL signed integer=8;modulus=5;exact ratio=8/5;floor quotient=1 After value=q*n+remainder;normalized residue=3 in[0,5);same congruence class,NOT absolute-value replacement Conditions: none Use the floor quotient for a positive modulus,retaining the congruence class of a negative base rather than replacing it by abs(a).Equal residues mean congruence modulo n,not equality of original integers. Step identifiers and dependenciesRule: euler_exact_signed_remainder_not_abs_or_integer_equality · Uses: G001, S038 S040 · impliesBefore COMPLETE original increasing U(n)=[1, 2, 3, 4];actual images in ORIGINAL unit order=[2, 4, 1, 3] After SOURCE output sorts the mapped list numerically=[1, 2, 3, 4];full-list equality=Yes;not a claim each point is fixed Conditions: none The source's second field is the sorted complete image list,not images in original unit order.Equal lists certify a permutation,not that multiplication by a fixes every point.The raw images are listed separately here. Step identifiers and dependenciesRule: euler_sorted_mapped_units_not_original_image_order_or_identity · Uses: G001, S039 ## Reverse checks - S040 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S039 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S038 · premise_and_result_audit — Recompute Euler unit representative4 raw image normalized remainder with exact rational arithmetic, not rounded decimals. - S037 · premise_and_result_audit — Recompute Euler unit representative4 raw image floor quotient multiple with exact rational arithmetic, not rounded decimals. - S036 · premise_and_result_audit — Recompute Euler unit representative4 raw image exact quotient with exact rational arithmetic, not rounded decimals. - S035 · premise_and_result_audit — Recompute Euler ORIGINAL a times unit representative4 with exact rational arithmetic, not rounded decimals. - S034 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S033 · premise_and_result_audit — Recompute Euler unit representative3 raw image normalized remainder with exact rational arithmetic, not rounded decimals. - S032 · premise_and_result_audit — Recompute Euler unit representative3 raw image floor quotient multiple with exact rational arithmetic, not rounded decimals. - S031 · premise_and_result_audit — Recompute Euler unit representative3 raw image exact quotient with exact rational arithmetic, not rounded decimals. - S030 · premise_and_result_audit — Recompute Euler ORIGINAL a times unit representative3 with exact rational arithmetic, not rounded decimals. - S029 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S028 · premise_and_result_audit — Recompute Euler unit representative2 raw image normalized remainder with exact rational arithmetic, not rounded decimals. - S027 · premise_and_result_audit — Recompute Euler unit representative2 raw image floor quotient multiple with exact rational arithmetic, not rounded decimals. - S026 · premise_and_result_audit — Recompute Euler unit representative2 raw image exact quotient with exact rational arithmetic, not rounded decimals. - S025 · premise_and_result_audit — Recompute Euler ORIGINAL a times unit representative2 with exact rational arithmetic, not rounded decimals. - S024 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S023 · premise_and_result_audit — Recompute Euler unit representative1 raw image normalized remainder with exact rational arithmetic, not rounded decimals. - S022 · premise_and_result_audit — Recompute Euler unit representative1 raw image floor quotient multiple with exact rational arithmetic, not rounded decimals. - S021 · premise_and_result_audit — Recompute Euler unit representative1 raw image exact quotient with exact rational arithmetic, not rounded decimals. - S020 · premise_and_result_audit — Recompute Euler ORIGINAL a times unit representative1 with exact rational arithmetic, not rounded decimals. - S019 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S018 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S017 · premise_and_result_audit — Recompute Euler ACTUAL inverse check normalized remainder with exact rational arithmetic, not rounded decimals. - S016 · premise_and_result_audit — Recompute Euler ACTUAL inverse check floor quotient multiple with exact rational arithmetic, not rounded decimals. - S015 · premise_and_result_audit — Recompute Euler ACTUAL inverse check exact quotient with exact rational arithmetic, not rounded decimals. - S014 · premise_and_result_audit — Recompute Euler ACTUAL base-unit inverse product with exact rational arithmetic, not rounded decimals. - S013 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S012 · premise_and_result_audit — Recompute Euler complete reduced residue count phi with exact rational arithmetic, not rounded decimals. - S011 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S010 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S009 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S008 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S007 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S006 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S005 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S004 · premise_and_result_audit — Recompute Euler ORIGINAL signed base normalization normalized remainder with exact rational arithmetic, not rounded decimals. - S003 · premise_and_result_audit — Recompute Euler ORIGINAL signed base normalization floor quotient multiple with exact rational arithmetic, not rounded decimals. - S002 · premise_and_result_audit — Recompute Euler ORIGINAL signed base normalization exact quotient with exact rational arithmetic, not rounded decimals. - S001 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. ## Result ([1, 2, 3, 4], [1, 2, 3, 4], Yes, multiplication_by_a_permutes_reduced_residues) The full substitutions and premise checks give the original answer; source identity,format and status are unchanged. ## 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: 7a097c1495b417af1036624b02764596eac4163a853ee7663ea7adc4b0dbfd9e - candidate record SHA-256: 1662daeb45f5ed09f2419c899c92e649556e4f94d58ec94e33dd11e945f96288 - semantic review receipt SHA-256: 6e11e35fafe32f16900ce9b522d01acb7b2ee6b463ab179392076cfbe1af8034 - question-first witness SHA-256: cc0fa361fc25151729e70264340d2eae94f179f6f2a2edfe80ba5704fbbd0682 - Lean: NOT_RUN · human review: NOT_PERFORMED [Same-source full JSON](https://ocme.evemisslab.com/data/question-derivations/questions/q-20261014-advance-20261107-r06-euler-theorem-number-theory-0026.json)