MX000F

coprime_divisor_factor_pair_exists

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

Canonical gcd existence supplies real positive divisor coordinates, without a factorization or choice oracle.

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. ~(d=0) -> (forall sfd_common_divisor_cdp_exists_coprime. (exists pvs_factor_cdp_exists_coprimeleft. (m) = (sfd_common_divisor_cdp_exists_coprime) * pvs_factor_cdp_exists_coprimeleft) -> (exists pvs_factor_cdp_exists_coprimeright. (n) = (sfd_common_divisor_cdp_exists_coprime) * pvs_factor_cdp_exists_coprimeright) -> sfd_common_divisor_cdp_exists_coprime = 1) -> (exists pvs_factor_cdp_exists_divisor. (m*n) = (d) * pvs_factor_cdp_exists_divisor) -> exists a b. (((~((a)=0)) /\ (((~((b)=0)) /\ (((exists pvs_factor_cdp_exists_resultleft. (m) = (a) * pvs_factor_cdp_exists_resultleft) /\ (((exists pvs_factor_cdp_exists_resultright. (n) = (b) * pvs_factor_cdp_exists_resultright) /\ ((d)=(a)*(b))))))))))

Constructive proof overview

Generated structural guide

Canonical gcd existence supplies real positive divisor coordinates, without a factorization or choice oracle.

The unchanged tactic script uses 5 declared prerequisites and contains 61 exact native proof lines.

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

Proof neighborhood

Direct dependencies

canonical_gcd_exists Alpha theorem; checked-use authorized MX000C coprime_divisor_gcd_product factor_nonzero_left Stable theorem; checked-use authorized factor_nonzero_right Alpha theorem; checked-use authorized is_gcd_dvd_left Stable theorem; checked-use authorized

Direct dependents

MX0011 coprime_divisor_factor_pair_exists_unique MX0054 dirichlet_coprime_grid_support_covering

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

61 script commands · 18 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.

Named ingredients (1)
coprime divisor gcd product

Long local formulas use this family’s existing definitions. Each new abbreviation was expanded back to the identical native formula, including its free-variable context. The original edition is preserved below.

01Fix variables and assumptionsL1–6

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 hd
  5. L5
    intro hc
  6. L6
    intro hdiv
02Establish haL7–10

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply canonical gcd exists.

  1. L7
    have ha : ∃ a. IsGCD(a,m,d)Definitions: IsGCD
  2. L8
    specialize canonical_gcd_exists (m)
  3. L9
    specialize canonical_gcd_exists (d)
  4. L10
    apply canonical_gcd_exists
03Separate the logical casesL11–11

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

  1. L11
    cases ha
04Establish hbL12–15

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply canonical gcd exists.

  1. L12
    have hb : ∃ b. IsGCD(b,n,d)Definitions: IsGCD
  2. L13
    specialize canonical_gcd_exists (n)
  3. L14
    specialize canonical_gcd_exists (d)
  4. L15
    apply canonical_gcd_exists
05Separate the logical casesL16–16

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

  1. L16
    cases hb
06Establish heqL17–26

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply coprime divisor gcd product.

  1. L17
    have heq : d=x*x1
  2. L18
    specialize coprime_divisor_gcd_product (m)
  3. L19
    specialize coprime_divisor_gcd_product (n)
  4. L20
    specialize coprime_divisor_gcd_product (d)
  5. L21
    specialize coprime_divisor_gcd_product (x)
  6. L22
    specialize coprime_divisor_gcd_product (x1)
  7. L23
    apply coprime_divisor_gcd_product
  8. L24
    exact hd
  9. L25
    exact hc
  10. L26
    exact hdiv
07Use earlier factsL27–28

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

  1. L27
    exact ha_witness
  2. L28
    exact hb_witness
08Construct an explicit witnessL29–30

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

  1. L29
    exists x
  2. L30
    exists x1
09Separate the logical casesL31–31

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

  1. L31
    split
10Fix variables and assumptionsL32–32

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

  1. L32
    intro hzero
11Use earlier factsL33–39

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

  1. L33
    specialize factor_nonzero_left (d)
  2. L34
    specialize factor_nonzero_left (x)
  3. L35
    specialize factor_nonzero_left (x1)
  4. L36
    apply factor_nonzero_left
  5. L37
    exact hd
  6. L38
    exact heq
  7. L39
    exact hzero
12Separate the logical casesL40–40

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

  1. L40
    split
13Fix variables and assumptionsL41–41

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

  1. L41
    intro hzero
14Use earlier factsL42–48

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

  1. L42
    specialize factor_nonzero_right (d)
  2. L43
    specialize factor_nonzero_right (x)
  3. L44
    specialize factor_nonzero_right (x1)
  4. L45
    apply factor_nonzero_right
  5. L46
    exact hd
  6. L47
    exact heq
  7. L48
    exact hzero
15Separate the logical casesL49–49

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

  1. L49
    split
16Use earlier factsL50–54

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

  1. L50
    specialize is_gcd_dvd_left (x)
  2. L51
    specialize is_gcd_dvd_left (m)
  3. L52
    specialize is_gcd_dvd_left (d)
  4. L53
    apply is_gcd_dvd_left
  5. L54
    exact ha_witness
17Separate the logical casesL55–55

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

  1. L55
    split
18Use earlier factsL56–61

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

  1. L56
    specialize is_gcd_dvd_left (x1)
  2. L57
    specialize is_gcd_dvd_left (n)
  3. L58
    specialize is_gcd_dvd_left (d)
  4. L59
    apply is_gcd_dvd_left
  5. L60
    exact hb_witness
  6. L61
    exact heq

Library-wide reading audit

Original exact command ledger · 61 lines
  1. 0001intro m
  2. 0002intro n
  3. 0003intro d
  4. 0004intro hd
  5. 0005intro hc
  6. 0006intro hdiv
  7. 0007have ha : exists a. (((exists ec_gcd_left_cor_cdp_exists_left. m = a * ec_gcd_left_cor_cdp_exists_left) /\ (exists ec_gcd_right_cor_cdp_exists_left. d = a * ec_gcd_right_cor_cdp_exists_left)) /\ forall ec_gcd_common_cor_cdp_exists_left. (exists ec_gcd_common_left_cor_cdp_exists_left. m = ec_gcd_common_cor_cdp_exists_left * ec_gcd_common_left_cor_cdp_exists_left) -> (exists ec_gcd_common_right_cor_cdp_exists_left. d = ec_gcd_common_cor_cdp_exists_left * ec_gcd_common_right_cor_cdp_exists_left) -> exists ec_gcd_greatest_cor_cdp_exists_left. a = ec_gcd_common_cor_cdp_exists_left * ec_gcd_greatest_cor_cdp_exists_left)
  8. 0008specialize canonical_gcd_exists (m)
  9. 0009specialize canonical_gcd_exists (d)
  10. 0010apply canonical_gcd_exists
  11. 0011cases ha
  12. 0012have hb : exists b. (((exists ec_gcd_left_cor_cdp_exists_right. n = b * ec_gcd_left_cor_cdp_exists_right) /\ (exists ec_gcd_right_cor_cdp_exists_right. d = b * ec_gcd_right_cor_cdp_exists_right)) /\ forall ec_gcd_common_cor_cdp_exists_right. (exists ec_gcd_common_left_cor_cdp_exists_right. n = ec_gcd_common_cor_cdp_exists_right * ec_gcd_common_left_cor_cdp_exists_right) -> (exists ec_gcd_common_right_cor_cdp_exists_right. d = ec_gcd_common_cor_cdp_exists_right * ec_gcd_common_right_cor_cdp_exists_right) -> exists ec_gcd_greatest_cor_cdp_exists_right. b = ec_gcd_common_cor_cdp_exists_right * ec_gcd_greatest_cor_cdp_exists_right)
  13. 0013specialize canonical_gcd_exists (n)
  14. 0014specialize canonical_gcd_exists (d)
  15. 0015apply canonical_gcd_exists
  16. 0016cases hb
  17. 0017have heq : d=x*x1
  18. 0018specialize coprime_divisor_gcd_product (m)
  19. 0019specialize coprime_divisor_gcd_product (n)
  20. 0020specialize coprime_divisor_gcd_product (d)
  21. 0021specialize coprime_divisor_gcd_product (x)
  22. 0022specialize coprime_divisor_gcd_product (x1)
  23. 0023apply coprime_divisor_gcd_product
  24. 0024exact hd
  25. 0025exact hc
  26. 0026exact hdiv
  27. 0027exact ha_witness
  28. 0028exact hb_witness
  29. 0029exists x
  30. 0030exists x1
  31. 0031split
  32. 0032intro hzero
  33. 0033specialize factor_nonzero_left (d)
  34. 0034specialize factor_nonzero_left (x)
  35. 0035specialize factor_nonzero_left (x1)
  36. 0036apply factor_nonzero_left
  37. 0037exact hd
  38. 0038exact heq
  39. 0039exact hzero
  40. 0040split
  41. 0041intro hzero
  42. 0042specialize factor_nonzero_right (d)
  43. 0043specialize factor_nonzero_right (x)
  44. 0044specialize factor_nonzero_right (x1)
  45. 0045apply factor_nonzero_right
  46. 0046exact hd
  47. 0047exact heq
  48. 0048exact hzero
  49. 0049split
  50. 0050specialize is_gcd_dvd_left (x)
  51. 0051specialize is_gcd_dvd_left (m)
  52. 0052specialize is_gcd_dvd_left (d)
  53. 0053apply is_gcd_dvd_left
  54. 0054exact ha_witness
  55. 0055split
  56. 0056specialize is_gcd_dvd_left (x1)
  57. 0057specialize is_gcd_dvd_left (n)
  58. 0058specialize is_gcd_dvd_left (d)
  59. 0059apply is_gcd_dvd_left
  60. 0060exact hb_witness
  61. 0061exact heq