EU0018

euler_unit_factor_scaled_congruence

A unit index contributes exactly one multiplier factor under the actual residue permutation.

Alpha v34 checked-use · first admitted v31 · independently kernel and Lean verified; not Stable

Current library: Alpha v34, 4,223 checked-use theorems; Stable remains 432. Historical first admissions, original proof editions, and non-admitted aliases are preserved.

The exact G014 theorem covers m>1 and genuinely invertible a. Phi counts coprime residues independently of the conclusion. The broader coprime theorem handles m=1 by congruence, not by asserting that one is a canonical remainder. Multiplicative-order and RSA statements are not claimed.

Exact theorem in conservative defined notation

∀ a. ∀ m. ∀ i. ∀ r. ∀ u. ∀ v. Coprime(a,m) → ModEq(m,a · i,r) → UnitProductFactor(m,i,u) → UnitProductFactor(m,r,v) → Coprime(i,m) → ModEq(m,a · u,v)

Every linked abbreviation expands hygienically to the identical original native formula.

Definition DAG

UnitProductFactor(m,i,v) · 2Coprime(a,b) · 6ModEq(m,a,b) · 2

Actual proof prerequisites

euler_multiplier_coprime_iffeuler_unit_product_factor_unit_value
Original expanded first-order statement 
forall a m i r u v. (forall eut_divisor_eu_scale_multiplier. (exists eut_left_eu_scale_multiplier. (a) = eut_divisor_eu_scale_multiplier * eut_left_eu_scale_multiplier) -> (exists eut_right_eu_scale_multiplier. (m) = eut_divisor_eu_scale_multiplier * eut_right_eu_scale_multiplier) -> eut_divisor_eu_scale_multiplier = 1) -> (exists eu_mod_left_scale_residue eu_mod_right_scale_residue. (a*i) + (m) * eu_mod_left_scale_residue = (r) + (m) * eu_mod_right_scale_residue) -> ((((forall eut_divisor_eu_scale_source_coprime. (exists eut_left_eu_scale_source_coprime. (i) = eut_divisor_eu_scale_source_coprime * eut_left_eu_scale_source_coprime) -> (exists eut_right_eu_scale_source_coprime. (m) = eut_divisor_eu_scale_source_coprime * eut_right_eu_scale_source_coprime) -> eut_divisor_eu_scale_source_coprime = 1) /\ (u)=(i)) \/ (~(forall eut_divisor_eu_scale_source_coprime. (exists eut_left_eu_scale_source_coprime. (i) = eut_divisor_eu_scale_source_coprime * eut_left_eu_scale_source_coprime) -> (exists eut_right_eu_scale_source_coprime. (m) = eut_divisor_eu_scale_source_coprime * eut_right_eu_scale_source_coprime) -> eut_divisor_eu_scale_source_coprime = 1) /\ (u)=1))) -> ((((forall eut_divisor_eu_scale_target_coprime. (exists eut_left_eu_scale_target_coprime. (r) = eut_divisor_eu_scale_target_coprime * eut_left_eu_scale_target_coprime) -> (exists eut_right_eu_scale_target_coprime. (m) = eut_divisor_eu_scale_target_coprime * eut_right_eu_scale_target_coprime) -> eut_divisor_eu_scale_target_coprime = 1) /\ (v)=(r)) \/ (~(forall eut_divisor_eu_scale_target_coprime. (exists eut_left_eu_scale_target_coprime. (r) = eut_divisor_eu_scale_target_coprime * eut_left_eu_scale_target_coprime) -> (exists eut_right_eu_scale_target_coprime. (m) = eut_divisor_eu_scale_target_coprime * eut_right_eu_scale_target_coprime) -> eut_divisor_eu_scale_target_coprime = 1) /\ (v)=1))) -> (forall eut_divisor_eu_scale_index_unit. (exists eut_left_eu_scale_index_unit. (i) = eut_divisor_eu_scale_index_unit * eut_left_eu_scale_index_unit) -> (exists eut_right_eu_scale_index_unit. (m) = eut_divisor_eu_scale_index_unit * eut_right_eu_scale_index_unit) -> eut_divisor_eu_scale_index_unit = 1) -> (exists eu_mod_left_scale_result eu_mod_right_scale_result. (a*u) + (m) * eu_mod_left_scale_result = (v) + (m) * eu_mod_right_scale_result)

Complete tactic proof in conservative notation

All 38 original proof lines are preserved. Only local proposition formulas are abbreviated; every abbreviation has an exact binder-safe expansion check. The linked exact edition contains the unchanged replay script.

Read the argument

Proof checkpoints

38 script commands · 7 reading checkpoints · 3 local claims

This is a reading aid, not a new proof or a proof-tree certificate. Checkpoint groups are consecutive commands, not inferred branch boundaries. Every step links to the preserved script.

Definition notation is shown below. Open the paired exact edition for the original native formulas. Source pairing is not a new equivalence certificate.

Named ingredients (2)
euler multiplier coprime iffeuler unit product factor unit value
01Fix variables and assumptionsL1–10

Work with arbitrary variables or the premises of the current implication.

  1. L1
    intro a
  2. L2
    intro m
  3. L3
    intro i
  4. L4
    intro r
  5. L5
    intro u
  6. L6
    intro v
  7. L7
    intro ha
  8. L8
    intro hmod
  9. L9
    intro hu
  10. L10
    intro hv
02Fix variables and assumptionsL11–11

Work with arbitrary variables or the premises of the current implication.

  1. L11
    intro hi
03Establish hequivL12–19

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply euler multiplier coprime iff.

  1. L12
    have hequiv : (Coprime(i,m) → Coprime(r,m)) ∧ (Coprime(r,m) → Coprime(i,m))Definitions: Coprime(i,m)Coprime(r,m)Original native command in the exact edition
  2. L13
    specialize euler_multiplier_coprime_iff (a)
  3. L14
    specialize euler_multiplier_coprime_iff (m)
  4. L15
    specialize euler_multiplier_coprime_iff (i)
  5. L16
    specialize euler_multiplier_coprime_iff (r)
  6. L17
    apply euler_multiplier_coprime_iff
  7. L18
    exact ha
  8. L19
    exact hmod
04Separate the logical casesL20–20

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L20
    cases hequiv
05Establish heL21–27

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply euler unit product factor unit value.

  1. L21
    have he : u=i
  2. L22
    specialize euler_unit_product_factor_unit_value (m)
  3. L23
    specialize euler_unit_product_factor_unit_value (i)
  4. L24
    specialize euler_unit_product_factor_unit_value (u)
  5. L25
    apply euler_unit_product_factor_unit_value
  6. L26
    exact hi
  7. L27
    exact hu
06Establish hfL28–37

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply euler unit product factor unit value.

  1. L28
    have hf : v=r
  2. L29
    specialize euler_unit_product_factor_unit_value (m)
  3. L30
    specialize euler_unit_product_factor_unit_value (r)
  4. L31
    specialize euler_unit_product_factor_unit_value (v)
  5. L32
    apply euler_unit_product_factor_unit_value
  6. L33
    apply hequiv_left
  7. L34
    exact hi
  8. L35
    exact hv
  9. L36
    rewrite he
  10. L37
    rewrite hf
07Use earlier factsL38–38

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L38
    exact hmod

Library-wide reading audit

Original defined command ledger · 38 lines
  1. 0001intro a
  2. 0002intro m
  3. 0003intro i
  4. 0004intro r
  5. 0005intro u
  6. 0006intro v
  7. 0007intro ha
  8. 0008intro hmod
  9. 0009intro hu
  10. 0010intro hv
  11. 0011intro hi
  12. 0012have hequiv : (Coprime(i,m) → Coprime(r,m)) ∧ (Coprime(r,m) → Coprime(i,m))
  13. 0013specialize euler_multiplier_coprime_iff (a)
  14. 0014specialize euler_multiplier_coprime_iff (m)
  15. 0015specialize euler_multiplier_coprime_iff (i)
  16. 0016specialize euler_multiplier_coprime_iff (r)
  17. 0017apply euler_multiplier_coprime_iff
  18. 0018exact ha
  19. 0019exact hmod
  20. 0020cases hequiv
  21. 0021have he : u=i
  22. 0022specialize euler_unit_product_factor_unit_value (m)
  23. 0023specialize euler_unit_product_factor_unit_value (i)
  24. 0024specialize euler_unit_product_factor_unit_value (u)
  25. 0025apply euler_unit_product_factor_unit_value
  26. 0026exact hi
  27. 0027exact hu
  28. 0028have hf : v=r
  29. 0029specialize euler_unit_product_factor_unit_value (m)
  30. 0030specialize euler_unit_product_factor_unit_value (r)
  31. 0031specialize euler_unit_product_factor_unit_value (v)
  32. 0032apply euler_unit_product_factor_unit_value
  33. 0033apply hequiv_left
  34. 0034exact hi
  35. 0035exact hv
  36. 0036rewrite he
  37. 0037rewrite hf
  38. 0038exact hmod