MX0012

coprime_divisor_factor_pair_cofactors

Alpha v34 independently verified · alpha_closed; checked-use authorized; not Stable

Real positive bounded cofactor witnesses have all cross-input coprimality relations and multiply to the true quotient.

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

Exact expanded first-order arithmetic statement

forall m n d a b. ~(m=0) -> ~(n=0) -> (forall sfd_common_divisor_cdp_cofactor_coprime. (exists pvs_factor_cdp_cofactor_coprimeleft. (m) = (sfd_common_divisor_cdp_cofactor_coprime) * pvs_factor_cdp_cofactor_coprimeleft) -> (exists pvs_factor_cdp_cofactor_coprimeright. (n) = (sfd_common_divisor_cdp_cofactor_coprime) * pvs_factor_cdp_cofactor_coprimeright) -> sfd_common_divisor_cdp_cofactor_coprime = 1) -> (((~((a)=0)) /\ (((~((b)=0)) /\ (((exists pvs_factor_cdp_cofactor_pairleft. (m) = (a) * pvs_factor_cdp_cofactor_pairleft) /\ (((exists pvs_factor_cdp_cofactor_pairright. (n) = (b) * pvs_factor_cdp_cofactor_pairright) /\ ((d)=(a)*(b)))))))))) -> exists u v. ((((m)=(a)*(u)) /\ ((((n)=(b)*(v)) /\ (((~((u)=0)) /\ (((~((v)=0)) /\ (((exists pvs_le_gap_cdp_cofactor_resultubound. pvs_le_gap_cdp_cofactor_resultubound + (u) = (m)) /\ (((exists pvs_le_gap_cdp_cofactor_resultvbound. pvs_le_gap_cdp_cofactor_resultvbound + (v) = (n)) /\ (((forall sfd_common_divisor_cdp_cofactor_resultab. (exists pvs_factor_cdp_cofactor_resultableft. (a) = (sfd_common_divisor_cdp_cofactor_resultab) * pvs_factor_cdp_cofactor_resultableft) -> (exists pvs_factor_cdp_cofactor_resultabright. (b) = (sfd_common_divisor_cdp_cofactor_resultab) * pvs_factor_cdp_cofactor_resultabright) -> sfd_common_divisor_cdp_cofactor_resultab = 1) /\ (((forall sfd_common_divisor_cdp_cofactor_resultav. (exists pvs_factor_cdp_cofactor_resultavleft. (a) = (sfd_common_divisor_cdp_cofactor_resultav) * pvs_factor_cdp_cofactor_resultavleft) -> (exists pvs_factor_cdp_cofactor_resultavright. (v) = (sfd_common_divisor_cdp_cofactor_resultav) * pvs_factor_cdp_cofactor_resultavright) -> sfd_common_divisor_cdp_cofactor_resultav = 1) /\ (((forall sfd_common_divisor_cdp_cofactor_resultub. (exists pvs_factor_cdp_cofactor_resultubleft. (u) = (sfd_common_divisor_cdp_cofactor_resultub) * pvs_factor_cdp_cofactor_resultubleft) -> (exists pvs_factor_cdp_cofactor_resultubright. (b) = (sfd_common_divisor_cdp_cofactor_resultub) * pvs_factor_cdp_cofactor_resultubright) -> sfd_common_divisor_cdp_cofactor_resultub = 1) /\ (((forall sfd_common_divisor_cdp_cofactor_resultuv. (exists pvs_factor_cdp_cofactor_resultuvleft. (u) = (sfd_common_divisor_cdp_cofactor_resultuv) * pvs_factor_cdp_cofactor_resultuvleft) -> (exists pvs_factor_cdp_cofactor_resultuvright. (v) = (sfd_common_divisor_cdp_cofactor_resultuv) * pvs_factor_cdp_cofactor_resultuvright) -> sfd_common_divisor_cdp_cofactor_resultuv = 1) /\ ((m)*(n)=(d)*((u)*(v)))))))))))))))))))))))

Constructive proof overview

Generated structural guide

Real positive bounded cofactor witnesses have all cross-input coprimality relations and multiply to the true quotient.

The unchanged tactic script uses 4 declared prerequisites and contains 107 exact native proof lines.

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

Proof neighborhood

Direct dependencies

positive_divisor_quotient_exists_unique Alpha theorem; checked-use authorized crt_coprime_divisor_pair Alpha theorem; checked-use authorized mul_assoc Stable theorem; checked-use authorized mul_comm Stable theorem; checked-use authorized

Direct dependents

MX004F dirichlet_multiplicative_pair_factorization

Formal native tactic body

Dependencies are introduced as named hypotheses before line 1. Local theorem links identify exact declared prerequisites. This exact body belongs to a complete independently kernel-checked constructive proof bundle and has Alpha checked-use authority; it does not imply Stable membership.

Read the argument

Proof checkpoints

107 script commands · 37 reading checkpoints · 2 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.

01Fix variables and assumptionsL1–9

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

  1. L1
    intro m
  2. L2
    intro n
  3. L3
    intro d
  4. L4
    intro a
  5. L5
    intro b
  6. L6
    intro hm
  7. L7
    intro hn
  8. L8
    intro hc
  9. L9
    intro hp
02Separate the logical casesL10–13

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

  1. L10
    cases hp
  2. L11
    cases hp_right
  3. L12
    cases hp_right_right
  4. L13
    cases hp_right_right_right
03Establish huL14–19

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply positive divisor quotient exists unique.

  1. L14
    have hu : exists q. (((m=a*q) /\ (((~(q=0)) /\ (((exists pvs_factor_cdp_cofactor_udivisor. (m) = (q) * pvs_factor_cdp_cofactor_udivisor) /\ (((exists pvs_le_gap_cdp_cofactor_ubound. pvs_le_gap_cdp_cofactor_ubound + (q) = (m)) /\ (forall r. m=a*r -> r=q)))))))))
  2. L15
    specialize positive_divisor_quotient_exists_unique (m)
  3. L16
    specialize positive_divisor_quotient_exists_unique (a)
  4. L17
    apply positive_divisor_quotient_exists_unique
  5. L18
    exact hm
  6. L19
    exact hp_right_right_left
04Separate the logical casesL20–24

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

  1. L20
    cases hu
  2. L21
    cases hu_witness
  3. L22
    cases hu_witness_right
  4. L23
    cases hu_witness_right_right
  5. L24
    cases hu_witness_right_right_right
05Establish hvL25–30

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply positive divisor quotient exists unique.

  1. L25
    have hv : exists q. (((n=b*q) /\ (((~(q=0)) /\ (((exists pvs_factor_cdp_cofactor_vdivisor. (n) = (q) * pvs_factor_cdp_cofactor_vdivisor) /\ (((exists pvs_le_gap_cdp_cofactor_vbound. pvs_le_gap_cdp_cofactor_vbound + (q) = (n)) /\ (forall r. n=b*r -> r=q)))))))))
  2. L26
    specialize positive_divisor_quotient_exists_unique (n)
  3. L27
    specialize positive_divisor_quotient_exists_unique (b)
  4. L28
    apply positive_divisor_quotient_exists_unique
  5. L29
    exact hn
  6. L30
    exact hp_right_right_right_left
06Separate the logical casesL31–35

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

  1. L31
    cases hv
  2. L32
    cases hv_witness
  3. L33
    cases hv_witness_right
  4. L34
    cases hv_witness_right_right
  5. L35
    cases hv_witness_right_right_right
07Construct an explicit witnessL36–37

Supply the displayed value, then prove that it has the required property.

  1. L36
    exists x
  2. L37
    exists x1
08Separate the logical casesL38–38

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

  1. L38
    split
09Use earlier factsL39–39

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

  1. L39
    exact hu_witness_left
10Separate the logical casesL40–40

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

  1. L40
    split
11Use earlier factsL41–41

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

  1. L41
    exact hv_witness_left
12Separate the logical casesL42–42

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

  1. L42
    split
13Use earlier factsL43–43

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

  1. L43
    exact hu_witness_right_left
14Separate the logical casesL44–44

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

  1. L44
    split
15Use earlier factsL45–45

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

  1. L45
    exact hv_witness_right_left
16Separate the logical casesL46–46

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

  1. L46
    split
17Use earlier factsL47–47

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

  1. L47
    exact hu_witness_right_right_right_left
18Separate the logical casesL48–48

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

  1. L48
    split
19Use earlier factsL49–49

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

  1. L49
    exact hv_witness_right_right_right_left
20Separate the logical casesL50–50

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

  1. L50
    split
21Use earlier factsL51–58

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

  1. L51
    specialize crt_coprime_divisor_pair (m)
  2. L52
    specialize crt_coprime_divisor_pair (n)
  3. L53
    specialize crt_coprime_divisor_pair (a)
  4. L54
    specialize crt_coprime_divisor_pair (b)
  5. L55
    apply crt_coprime_divisor_pair
  6. L56
    exact hc
  7. L57
    exact hp_right_right_left
  8. L58
    exact hp_right_right_right_left
22Separate the logical casesL59–59

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

  1. L59
    split
23Use earlier factsL60–67

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

  1. L60
    specialize crt_coprime_divisor_pair (m)
  2. L61
    specialize crt_coprime_divisor_pair (n)
  3. L62
    specialize crt_coprime_divisor_pair (a)
  4. L63
    specialize crt_coprime_divisor_pair (x1)
  5. L64
    apply crt_coprime_divisor_pair
  6. L65
    exact hc
  7. L66
    exact hp_right_right_left
  8. L67
    exact hv_witness_right_right_left
24Separate the logical casesL68–68

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

  1. L68
    split
25Use earlier factsL69–76

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

  1. L69
    specialize crt_coprime_divisor_pair (m)
  2. L70
    specialize crt_coprime_divisor_pair (n)
  3. L71
    specialize crt_coprime_divisor_pair (x)
  4. L72
    specialize crt_coprime_divisor_pair (b)
  5. L73
    apply crt_coprime_divisor_pair
  6. L74
    exact hc
  7. L75
    exact hu_witness_right_right_left
  8. L76
    exact hp_right_right_right_left
26Separate the logical casesL77–77

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

  1. L77
    split
27Use earlier factsL78–85

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

  1. L78
    specialize crt_coprime_divisor_pair (m)
  2. L79
    specialize crt_coprime_divisor_pair (n)
  3. L80
    specialize crt_coprime_divisor_pair (x)
  4. L81
    specialize crt_coprime_divisor_pair (x1)
  5. L82
    apply crt_coprime_divisor_pair
  6. L83
    exact hc
  7. L84
    exact hu_witness_right_right_left
  8. L85
    exact hv_witness_right_right_left
28Calculate and transport equalitiesL86–89

Carry out the recorded arithmetic or equality steps; inspect the exact commands for their direction and premises.

  1. L86
    rewrite hu_witness_left
  2. L87
    rewrite hv_witness_left
  3. L88
    rewrite hp_right_right_right_right
  4. L89
    trans a*(x*(b*x1))
29Use earlier factsL90–90

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

  1. L90
    apply mul_assoc
30Calculate and transport equalitiesL91–94

Carry out the recorded arithmetic or equality steps; inspect the exact commands for their direction and premises.

  1. L91
    trans a*((x*b)*x1)
  2. L92
    congr
  3. L93
    refl
  4. L94
    symm
31Use earlier factsL95–95

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

  1. L95
    apply mul_assoc
32Calculate and transport equalitiesL96–99

Carry out the recorded arithmetic or equality steps; inspect the exact commands for their direction and premises.

  1. L96
    trans a*((b*x)*x1)
  2. L97
    congr
  3. L98
    refl
  4. L99
    congr
33Use earlier factsL100–100

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

  1. L100
    apply mul_comm
34Calculate and transport equalitiesL101–104

Carry out the recorded arithmetic or equality steps; inspect the exact commands for their direction and premises.

  1. L101
    refl
  2. L102
    trans a*(b*(x*x1))
  3. L103
    congr
  4. L104
    refl
35Use earlier factsL105–105

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

  1. L105
    apply mul_assoc
36Calculate and transport equalitiesL106–106

Carry out the recorded arithmetic or equality steps; inspect the exact commands for their direction and premises.

  1. L106
    symm
37Use earlier factsL107–107

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

  1. L107
    apply mul_assoc

Library-wide reading audit

Original exact command ledger · 107 lines
  1. 0001intro m
  2. 0002intro n
  3. 0003intro d
  4. 0004intro a
  5. 0005intro b
  6. 0006intro hm
  7. 0007intro hn
  8. 0008intro hc
  9. 0009intro hp
  10. 0010cases hp
  11. 0011cases hp_right
  12. 0012cases hp_right_right
  13. 0013cases hp_right_right_right
  14. 0014have hu : exists q. (((m=a*q) /\ (((~(q=0)) /\ (((exists pvs_factor_cdp_cofactor_udivisor. (m) = (q) * pvs_factor_cdp_cofactor_udivisor) /\ (((exists pvs_le_gap_cdp_cofactor_ubound. pvs_le_gap_cdp_cofactor_ubound + (q) = (m)) /\ (forall r. m=a*r -> r=q)))))))))
  15. 0015specialize positive_divisor_quotient_exists_unique (m)
  16. 0016specialize positive_divisor_quotient_exists_unique (a)
  17. 0017apply positive_divisor_quotient_exists_unique
  18. 0018exact hm
  19. 0019exact hp_right_right_left
  20. 0020cases hu
  21. 0021cases hu_witness
  22. 0022cases hu_witness_right
  23. 0023cases hu_witness_right_right
  24. 0024cases hu_witness_right_right_right
  25. 0025have hv : exists q. (((n=b*q) /\ (((~(q=0)) /\ (((exists pvs_factor_cdp_cofactor_vdivisor. (n) = (q) * pvs_factor_cdp_cofactor_vdivisor) /\ (((exists pvs_le_gap_cdp_cofactor_vbound. pvs_le_gap_cdp_cofactor_vbound + (q) = (n)) /\ (forall r. n=b*r -> r=q)))))))))
  26. 0026specialize positive_divisor_quotient_exists_unique (n)
  27. 0027specialize positive_divisor_quotient_exists_unique (b)
  28. 0028apply positive_divisor_quotient_exists_unique
  29. 0029exact hn
  30. 0030exact hp_right_right_right_left
  31. 0031cases hv
  32. 0032cases hv_witness
  33. 0033cases hv_witness_right
  34. 0034cases hv_witness_right_right
  35. 0035cases hv_witness_right_right_right
  36. 0036exists x
  37. 0037exists x1
  38. 0038split
  39. 0039exact hu_witness_left
  40. 0040split
  41. 0041exact hv_witness_left
  42. 0042split
  43. 0043exact hu_witness_right_left
  44. 0044split
  45. 0045exact hv_witness_right_left
  46. 0046split
  47. 0047exact hu_witness_right_right_right_left
  48. 0048split
  49. 0049exact hv_witness_right_right_right_left
  50. 0050split
  51. 0051specialize crt_coprime_divisor_pair (m)
  52. 0052specialize crt_coprime_divisor_pair (n)
  53. 0053specialize crt_coprime_divisor_pair (a)
  54. 0054specialize crt_coprime_divisor_pair (b)
  55. 0055apply crt_coprime_divisor_pair
  56. 0056exact hc
  57. 0057exact hp_right_right_left
  58. 0058exact hp_right_right_right_left
  59. 0059split
  60. 0060specialize crt_coprime_divisor_pair (m)
  61. 0061specialize crt_coprime_divisor_pair (n)
  62. 0062specialize crt_coprime_divisor_pair (a)
  63. 0063specialize crt_coprime_divisor_pair (x1)
  64. 0064apply crt_coprime_divisor_pair
  65. 0065exact hc
  66. 0066exact hp_right_right_left
  67. 0067exact hv_witness_right_right_left
  68. 0068split
  69. 0069specialize crt_coprime_divisor_pair (m)
  70. 0070specialize crt_coprime_divisor_pair (n)
  71. 0071specialize crt_coprime_divisor_pair (x)
  72. 0072specialize crt_coprime_divisor_pair (b)
  73. 0073apply crt_coprime_divisor_pair
  74. 0074exact hc
  75. 0075exact hu_witness_right_right_left
  76. 0076exact hp_right_right_right_left
  77. 0077split
  78. 0078specialize crt_coprime_divisor_pair (m)
  79. 0079specialize crt_coprime_divisor_pair (n)
  80. 0080specialize crt_coprime_divisor_pair (x)
  81. 0081specialize crt_coprime_divisor_pair (x1)
  82. 0082apply crt_coprime_divisor_pair
  83. 0083exact hc
  84. 0084exact hu_witness_right_right_left
  85. 0085exact hv_witness_right_right_left
  86. 0086rewrite hu_witness_left
  87. 0087rewrite hv_witness_left
  88. 0088rewrite hp_right_right_right_right
  89. 0089trans a*(x*(b*x1))
  90. 0090apply mul_assoc
  91. 0091trans a*((x*b)*x1)
  92. 0092congr
  93. 0093refl
  94. 0094symm
  95. 0095apply mul_assoc
  96. 0096trans a*((b*x)*x1)
  97. 0097congr
  98. 0098refl
  99. 0099congr
  100. 0100apply mul_comm
  101. 0101refl
  102. 0102trans a*(b*(x*x1))
  103. 0103congr
  104. 0104refl
  105. 0105apply mul_assoc
  106. 0106symm
  107. 0107apply mul_assoc