BT00QN · Bertrand theorem

prime_power_successor_cancel_cofactor

Alpha v34 checked-use theorem · independently kernel and Lean verified; not Stable

A successor power divisor cancels to a prime divisor of the exact cofactor.

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.

Statement with defined notation

∀ p. ∀ e. ∀ a. ∀ r. ∀ q. Prime(p)Pow(p,e,r) → a = r · q → PowerDivides(p,S e,a)Dvd(p,q)

Every purple notation token opens its conservative definition. Expanding the displayed statement recovers the exact first-order Peano-arithmetic formula checked by the unchanged kernel.

Definitions used by this theorem

In the theorem statement

4 occurrences

In local proof propositions

1 occurrences

Exact expanded native-PA statement
forall p e a r q. ((~(p = 1) /\ forall frm_prime_left_bpd_prime frm_prime_right_bpd_prime. p = frm_prime_left_bpd_prime * frm_prime_right_bpd_prime -> frm_prime_left_bpd_prime = 1 \/ frm_prime_right_bpd_prime = 1)) -> (exists ff_b_bpd_cancel_prefix ff_c_bpd_cancel_prefix. ((forall ff_i_bpd_cancel_prefix_repeat. (exists ff_lt_bpd_cancel_prefix_repeat_bound. ff_lt_bpd_cancel_prefix_repeat_bound + S ff_i_bpd_cancel_prefix_repeat = e) -> (((exists ff_h_bpd_cancel_prefix_repeat_decoded. ff_h_bpd_cancel_prefix_repeat_decoded + S (p) = S ((S (ff_i_bpd_cancel_prefix_repeat)) * ff_c_bpd_cancel_prefix)) /\ exists ff_q_bpd_cancel_prefix_repeat_decoded. ff_b_bpd_cancel_prefix = ff_q_bpd_cancel_prefix_repeat_decoded * S ((S (ff_i_bpd_cancel_prefix_repeat)) * ff_c_bpd_cancel_prefix) + (p)))) /\ (exists ff_u_bpd_cancel_prefix_product ff_v_bpd_cancel_prefix_product. ((((exists ff_h_bpd_cancel_prefix_product_start. ff_h_bpd_cancel_prefix_product_start + S (1) = S ((S (0)) * ff_v_bpd_cancel_prefix_product)) /\ exists ff_q_bpd_cancel_prefix_product_start. ff_u_bpd_cancel_prefix_product = ff_q_bpd_cancel_prefix_product_start * S ((S (0)) * ff_v_bpd_cancel_prefix_product) + (1))) /\ ((((exists ff_h_bpd_cancel_prefix_product_terminal. ff_h_bpd_cancel_prefix_product_terminal + S (r) = S ((S (e)) * ff_v_bpd_cancel_prefix_product)) /\ exists ff_q_bpd_cancel_prefix_product_terminal. ff_u_bpd_cancel_prefix_product = ff_q_bpd_cancel_prefix_product_terminal * S ((S (e)) * ff_v_bpd_cancel_prefix_product) + (r))) /\ forall ff_i_bpd_cancel_prefix_product. (exists ff_lt_bpd_cancel_prefix_product_bound. ff_lt_bpd_cancel_prefix_product_bound + S ff_i_bpd_cancel_prefix_product = e) -> exists ff_p_bpd_cancel_prefix_product ff_r_bpd_cancel_prefix_product ff_s_bpd_cancel_prefix_product. ((((exists ff_h_bpd_cancel_prefix_product_factor. ff_h_bpd_cancel_prefix_product_factor + S (ff_p_bpd_cancel_prefix_product) = S ((S (ff_i_bpd_cancel_prefix_product)) * ff_c_bpd_cancel_prefix)) /\ exists ff_q_bpd_cancel_prefix_product_factor. ff_b_bpd_cancel_prefix = ff_q_bpd_cancel_prefix_product_factor * S ((S (ff_i_bpd_cancel_prefix_product)) * ff_c_bpd_cancel_prefix) + (ff_p_bpd_cancel_prefix_product))) /\ ((((exists ff_h_bpd_cancel_prefix_product_partial. ff_h_bpd_cancel_prefix_product_partial + S (ff_r_bpd_cancel_prefix_product) = S ((S (ff_i_bpd_cancel_prefix_product)) * ff_v_bpd_cancel_prefix_product)) /\ exists ff_q_bpd_cancel_prefix_product_partial. ff_u_bpd_cancel_prefix_product = ff_q_bpd_cancel_prefix_product_partial * S ((S (ff_i_bpd_cancel_prefix_product)) * ff_v_bpd_cancel_prefix_product) + (ff_r_bpd_cancel_prefix_product))) /\ ((((exists ff_h_bpd_cancel_prefix_product_successor. ff_h_bpd_cancel_prefix_product_successor + S (ff_s_bpd_cancel_prefix_product) = S ((S (S ff_i_bpd_cancel_prefix_product)) * ff_v_bpd_cancel_prefix_product)) /\ exists ff_q_bpd_cancel_prefix_product_successor. ff_u_bpd_cancel_prefix_product = ff_q_bpd_cancel_prefix_product_successor * S ((S (S ff_i_bpd_cancel_prefix_product)) * ff_v_bpd_cancel_prefix_product) + (ff_s_bpd_cancel_prefix_product))) /\ ff_s_bpd_cancel_prefix_product = ff_r_bpd_cancel_prefix_product * ff_p_bpd_cancel_prefix_product)))))))) -> a = r * q -> (exists bpvi_result_cancel_successor. ((exists bpvi_b_cancel_successor_power bpvi_c_cancel_successor_power. ((forall bpvi_i_cancel_successor_power. (exists bpvi_repeat_gap_cancel_successor_power. bpvi_repeat_gap_cancel_successor_power + S bpvi_i_cancel_successor_power = S e) -> (((exists bpvi_h_cancel_successor_power_repeat. bpvi_h_cancel_successor_power_repeat + S (p) = S ((S (bpvi_i_cancel_successor_power)) * bpvi_c_cancel_successor_power)) /\ exists bpvi_q_cancel_successor_power_repeat. bpvi_b_cancel_successor_power = bpvi_q_cancel_successor_power_repeat * S ((S (bpvi_i_cancel_successor_power)) * bpvi_c_cancel_successor_power) + (p)))) /\ (exists bpvi_u_cancel_successor_power bpvi_v_cancel_successor_power. ((((exists bpvi_h_cancel_successor_power_start. bpvi_h_cancel_successor_power_start + S (1) = S ((S (0)) * bpvi_v_cancel_successor_power)) /\ exists bpvi_q_cancel_successor_power_start. bpvi_u_cancel_successor_power = bpvi_q_cancel_successor_power_start * S ((S (0)) * bpvi_v_cancel_successor_power) + (1))) /\ ((((exists bpvi_h_cancel_successor_power_terminal. bpvi_h_cancel_successor_power_terminal + S (bpvi_result_cancel_successor) = S ((S (S e)) * bpvi_v_cancel_successor_power)) /\ exists bpvi_q_cancel_successor_power_terminal. bpvi_u_cancel_successor_power = bpvi_q_cancel_successor_power_terminal * S ((S (S e)) * bpvi_v_cancel_successor_power) + (bpvi_result_cancel_successor))) /\ forall bpvi_j_cancel_successor_power. (exists bpvi_product_gap_cancel_successor_power. bpvi_product_gap_cancel_successor_power + S bpvi_j_cancel_successor_power = S e) -> exists bpvi_factor_cancel_successor_power bpvi_partial_cancel_successor_power bpvi_successor_cancel_successor_power. ((((exists bpvi_h_cancel_successor_power_factor. bpvi_h_cancel_successor_power_factor + S (bpvi_factor_cancel_successor_power) = S ((S (bpvi_j_cancel_successor_power)) * bpvi_c_cancel_successor_power)) /\ exists bpvi_q_cancel_successor_power_factor. bpvi_b_cancel_successor_power = bpvi_q_cancel_successor_power_factor * S ((S (bpvi_j_cancel_successor_power)) * bpvi_c_cancel_successor_power) + (bpvi_factor_cancel_successor_power))) /\ ((((exists bpvi_h_cancel_successor_power_partial. bpvi_h_cancel_successor_power_partial + S (bpvi_partial_cancel_successor_power) = S ((S (bpvi_j_cancel_successor_power)) * bpvi_v_cancel_successor_power)) /\ exists bpvi_q_cancel_successor_power_partial. bpvi_u_cancel_successor_power = bpvi_q_cancel_successor_power_partial * S ((S (bpvi_j_cancel_successor_power)) * bpvi_v_cancel_successor_power) + (bpvi_partial_cancel_successor_power))) /\ ((((exists bpvi_h_cancel_successor_power_successor. bpvi_h_cancel_successor_power_successor + S (bpvi_successor_cancel_successor_power) = S ((S (S bpvi_j_cancel_successor_power)) * bpvi_v_cancel_successor_power)) /\ exists bpvi_q_cancel_successor_power_successor. bpvi_u_cancel_successor_power = bpvi_q_cancel_successor_power_successor * S ((S (S bpvi_j_cancel_successor_power)) * bpvi_v_cancel_successor_power) + (bpvi_successor_cancel_successor_power))) /\ bpvi_successor_cancel_successor_power = bpvi_partial_cancel_successor_power * bpvi_factor_cancel_successor_power)))))))) /\ exists bpvi_divisor_factor_cancel_successor. a = bpvi_result_cancel_successor * bpvi_divisor_factor_cancel_successor)) -> (exists bpd_factor_cancel_cofactor_result. q = (p) * bpd_factor_cancel_cofactor_result)

Proof neighborhood

Direct theorem prerequisites

Direct theorem dependents

Definition-aware tactic body

Only local propositions introduced by have or suffices are compacted. Every changed line has an exact-AST conservative-expansion receipt; the kernel still receives the immutable original tactic script.

Read the argument

Proof checkpoints

59 script commands · 10 reading checkpoints · 5 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 (6)
01Fix variables and assumptionsL1–9

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

  1. L1
    intro p
  2. L2
    intro e
  3. L3
    intro a
  4. L4
    intro r
  5. L5
    intro q
  6. L6
    intro hp
  7. L7
    intro hr
  8. L8
    intro harq
  9. L9
    intro hsuccessor
02Separate the logical casesL10–12

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

  1. L10
    cases hsuccessor
  2. L11
    cases hsuccessor_witness
  3. L12
    cases hsuccessor_witness_right
03Establish hp0L13–18

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply prime nonzero.

  1. L13
    have hp0 : ~(p = 0)
  2. L14
    intro hpzero
  3. L15
    specialize prime_nonzero p
  4. L16
    apply prime_nonzero
  5. L17
    exact hp
  6. L18
    exact hpzero
04Establish hp1L19–22

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply one le of ne zero.

  1. L19
  2. L20
    specialize one_le_of_ne_zero p
  3. L21
    apply one_le_of_ne_zero
  4. L22
    exact hp0
05Establish hr0L23–31

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply pow nonzero of one le.

  1. L23
    have hr0 : ~(r = 0)
  2. L24
    intro hrzero
  3. L25
    specialize pow_nonzero_of_one_le p
  4. L26
    specialize pow_nonzero_of_one_le e
  5. L27
    specialize pow_nonzero_of_one_le r
  6. L28
    apply pow_nonzero_of_one_le
  7. L29
    exact hp1
  8. L30
    exact hr
  9. L31
    exact hrzero
06Establish hsuccessor_valueL32–41

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply pow successor pair mul.

  1. L32
    have hsuccessor_value : x = r * p
  2. L33
    specialize pow_successor_pair_mul p
  3. L34
    specialize pow_successor_pair_mul e
  4. L35
    specialize pow_successor_pair_mul (S e)
  5. L36
    specialize pow_successor_pair_mul r
  6. L37
    specialize pow_successor_pair_mul x
  7. L38
    apply pow_successor_pair_mul
  8. L39
    refl
  9. L40
    exact hr
  10. L41
    exact hsuccessor_witness_left
07Establish hcancelL42–51

Establish this local claim before using it. It is not an additional assumption.

  1. L42
    have hcancel : r * q = r * (p * x1)
  2. L43
    trans a
  3. L44
    symm
  4. L45
    exact harq
  5. L46
    trans x * x1
  6. L47
    exact hsuccessor_witness_right_witness
  7. L48
    trans (r * p) * x1
  8. L49
    congr
  9. L50
    exact hsuccessor_value
  10. L51
    refl
08Use earlier factsL52–52

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

  1. L52
    apply mul_assoc
09Construct an explicit witnessL53–53

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

  1. L53
    exists x1
10Use earlier factsL54–59

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

  1. L54
    specialize mul_left_cancel_nonzero r
  2. L55
    specialize mul_left_cancel_nonzero q
  3. L56
    specialize mul_left_cancel_nonzero (p * x1)
  4. L57
    apply mul_left_cancel_nonzero
  5. L58
    exact hr0
  6. L59
    exact hcancel

Library-wide reading audit

Original defined command ledger · 59 lines
  1. 0001intro p
  2. 0002intro e
  3. 0003intro a
  4. 0004intro r
  5. 0005intro q
  6. 0006intro hp
  7. 0007intro hr
  8. 0008intro harq
  9. 0009intro hsuccessor
  10. 0010cases hsuccessor
  11. 0011cases hsuccessor_witness
  12. 0012cases hsuccessor_witness_right
  13. 0013have hp0 : ~(p = 0)
  14. 0014intro hpzero
  15. 0015specialize prime_nonzero p
  16. 0016apply prime_nonzero
  17. 0017exact hp
  18. 0018exact hpzero
  19. 0019have hp1 : Lt(0,p)
    Exact native replay linehave hp1 : exists k. k + 1 = p
  20. 0020specialize one_le_of_ne_zero p
  21. 0021apply one_le_of_ne_zero
  22. 0022exact hp0
  23. 0023have hr0 : ~(r = 0)
  24. 0024intro hrzero
  25. 0025specialize pow_nonzero_of_one_le p
  26. 0026specialize pow_nonzero_of_one_le e
  27. 0027specialize pow_nonzero_of_one_le r
  28. 0028apply pow_nonzero_of_one_le
  29. 0029exact hp1
  30. 0030exact hr
  31. 0031exact hrzero
  32. 0032have hsuccessor_value : x = r * p
  33. 0033specialize pow_successor_pair_mul p
  34. 0034specialize pow_successor_pair_mul e
  35. 0035specialize pow_successor_pair_mul (S e)
  36. 0036specialize pow_successor_pair_mul r
  37. 0037specialize pow_successor_pair_mul x
  38. 0038apply pow_successor_pair_mul
  39. 0039refl
  40. 0040exact hr
  41. 0041exact hsuccessor_witness_left
  42. 0042have hcancel : r * q = r * (p * x1)
  43. 0043trans a
  44. 0044symm
  45. 0045exact harq
  46. 0046trans x * x1
  47. 0047exact hsuccessor_witness_right_witness
  48. 0048trans (r * p) * x1
  49. 0049congr
  50. 0050exact hsuccessor_value
  51. 0051refl
  52. 0052apply mul_assoc
  53. 0053exists x1
  54. 0054specialize mul_left_cancel_nonzero r
  55. 0055specialize mul_left_cancel_nonzero q
  56. 0056specialize mul_left_cancel_nonzero (p * x1)
  57. 0057apply mul_left_cancel_nonzero
  58. 0058exact hr0
  59. 0059exact hcancel