BT00QN

prime_power_successor_cancel_cofactor

Alpha body-checked ยท checked-use disabled

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

Exact expanded 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)

Structural proof guide

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

Direct prerequisites: prime_nonzero, one_le_of_ne_zero, pow_nonzero_of_one_le, pow_successor_pair_mul, mul_left_cancel_nonzero, mul_assoc. The authored body proceeds by case analysis (3), intermediate claims (5).

Proof neighborhood

Direct dependencies

Direct dependents

Formal native tactic body

Dependencies are hypotheses of this body receipt. The focused endpoint audits separately check the complete empty-context certificates.

  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 : 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