GC0002

crt_coprime_divisor_pair

Any divisors of two coprime naturals are themselves constructively coprime.

Alpha v34 checked-use · first admitted v25 · 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. Exact original first-admission records.

Historical partial components only: this chapter proves canonical solutions under successive-merge compatibility and in the pairwise-compatible dominating-last case. G011 is now closed in the separate Alpha-v27 generalized-crt branch for arbitrary pairwise-compatible finite lists, including noncoprime moduli. Full G011 proof · Alpha v27

Exact theorem in conservative defined notation

∀ a. ∀ b. ∀ d. ∀ e. Coprime(a,b) → Dvd(d,a) → Dvd(e,b) → Coprime(d,e)

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

Definition DAG

Dvd(d,n) · 2Coprime(a,b) · 2

Actual proof prerequisites

multiple_trans · checked external prerequisite
Original expanded first-order statement 
forall a b d e. (forall frp_divisor_gcomp_divisor_source. (exists frp_left_factor_gcomp_divisor_source. a = frp_divisor_gcomp_divisor_source * frp_left_factor_gcomp_divisor_source) -> (exists frp_right_factor_gcomp_divisor_source. b = frp_divisor_gcomp_divisor_source * frp_right_factor_gcomp_divisor_source) -> frp_divisor_gcomp_divisor_source = 1) -> (exists u. a = d * u) -> (exists v. b = e * v) -> (forall frp_divisor_gcomp_divisor_result. (exists frp_left_factor_gcomp_divisor_result. d = frp_divisor_gcomp_divisor_result * frp_left_factor_gcomp_divisor_result) -> (exists frp_right_factor_gcomp_divisor_result. e = frp_divisor_gcomp_divisor_result * frp_right_factor_gcomp_divisor_result) -> frp_divisor_gcomp_divisor_result = 1)

Complete unchanged native tactic proof

All 24 lines are the exact independently kernel-checked original script.

Read the argument

Proof checkpoints

24 script commands · 3 reading checkpoints · 0 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.

01Fix variables and assumptionsL1–10

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

  1. L1
    intro a
  2. L2
    intro b
  3. L3
    intro d
  4. L4
    intro e
  5. L5
    intro hcoprime
  6. L6
    intro hd
  7. L7
    intro he
  8. L8
    intro k
  9. L9
    intro hkd
  10. L10
    intro hke
02Use earlier factsL11–20

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

  1. L11
    specialize hcoprime k
  2. L12
    apply hcoprime
  3. L13
    specialize multiple_trans d
  4. L14
    specialize multiple_trans k
  5. L15
    specialize multiple_trans a
  6. L16
    apply multiple_trans
  7. L17
    exact hd
  8. L18
    exact hkd
  9. L19
    specialize multiple_trans e
  10. L20
    specialize multiple_trans k
03Use earlier factsL21–24

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

  1. L21
    specialize multiple_trans b
  2. L22
    apply multiple_trans
  3. L23
    exact he
  4. L24
    exact hke

Library-wide reading audit

Original defined command ledger · 24 lines
  1. 0001intro a
  2. 0002intro b
  3. 0003intro d
  4. 0004intro e
  5. 0005intro hcoprime
  6. 0006intro hd
  7. 0007intro he
  8. 0008intro k
  9. 0009intro hkd
  10. 0010intro hke
  11. 0011specialize hcoprime k
  12. 0012apply hcoprime
  13. 0013specialize multiple_trans d
  14. 0014specialize multiple_trans k
  15. 0015specialize multiple_trans a
  16. 0016apply multiple_trans
  17. 0017exact hd
  18. 0018exact hkd
  19. 0019specialize multiple_trans e
  20. 0020specialize multiple_trans k
  21. 0021specialize multiple_trans b
  22. 0022apply multiple_trans
  23. 0023exact he
  24. 0024exact hke