PA00BN

bounded_euler_criterion_dichotomy

Alpha v16 checked-use theorem · independently closed; not Stable

Every bounded nonzero input lands constructively in exactly the appropriate Euler endpoint.

Exact expanded PA statement

forall p a n h A. p = S n -> ((~(p = 1) /\ forall esi_prime_left_ecb_prime esi_prime_right_ecb_prime. p = esi_prime_left_ecb_prime * esi_prime_right_ecb_prime -> esi_prime_left_ecb_prime = 1 \/ esi_prime_right_ecb_prime = 1)) -> ~(a = 0) -> (exists wpo_gap_ecb_a_lt_p. wpo_gap_ecb_a_lt_p + S (a) = p) -> n = h + h -> (exists ff_b_ecb_power ff_c_ecb_power. ((forall ff_i_ecb_power_repeat. (exists ff_lt_ecb_power_repeat_bound. ff_lt_ecb_power_repeat_bound + S ff_i_ecb_power_repeat = h) -> (((exists ff_h_ecb_power_repeat_decoded. ff_h_ecb_power_repeat_decoded + S (a) = S ((S (ff_i_ecb_power_repeat)) * ff_c_ecb_power)) /\ exists ff_q_ecb_power_repeat_decoded. ff_b_ecb_power = ff_q_ecb_power_repeat_decoded * S ((S (ff_i_ecb_power_repeat)) * ff_c_ecb_power) + (a)))) /\ (exists ff_u_ecb_power_product ff_v_ecb_power_product. ((((exists ff_h_ecb_power_product_start. ff_h_ecb_power_product_start + S (1) = S ((S (0)) * ff_v_ecb_power_product)) /\ exists ff_q_ecb_power_product_start. ff_u_ecb_power_product = ff_q_ecb_power_product_start * S ((S (0)) * ff_v_ecb_power_product) + (1))) /\ ((((exists ff_h_ecb_power_product_terminal. ff_h_ecb_power_product_terminal + S (A) = S ((S (h)) * ff_v_ecb_power_product)) /\ exists ff_q_ecb_power_product_terminal. ff_u_ecb_power_product = ff_q_ecb_power_product_terminal * S ((S (h)) * ff_v_ecb_power_product) + (A))) /\ forall ff_i_ecb_power_product. (exists ff_lt_ecb_power_product_bound. ff_lt_ecb_power_product_bound + S ff_i_ecb_power_product = h) -> exists ff_p_ecb_power_product ff_r_ecb_power_product ff_s_ecb_power_product. ((((exists ff_h_ecb_power_product_factor. ff_h_ecb_power_product_factor + S (ff_p_ecb_power_product) = S ((S (ff_i_ecb_power_product)) * ff_c_ecb_power)) /\ exists ff_q_ecb_power_product_factor. ff_b_ecb_power = ff_q_ecb_power_product_factor * S ((S (ff_i_ecb_power_product)) * ff_c_ecb_power) + (ff_p_ecb_power_product))) /\ ((((exists ff_h_ecb_power_product_partial. ff_h_ecb_power_product_partial + S (ff_r_ecb_power_product) = S ((S (ff_i_ecb_power_product)) * ff_v_ecb_power_product)) /\ exists ff_q_ecb_power_product_partial. ff_u_ecb_power_product = ff_q_ecb_power_product_partial * S ((S (ff_i_ecb_power_product)) * ff_v_ecb_power_product) + (ff_r_ecb_power_product))) /\ ((((exists ff_h_ecb_power_product_successor. ff_h_ecb_power_product_successor + S (ff_s_ecb_power_product) = S ((S (S ff_i_ecb_power_product)) * ff_v_ecb_power_product)) /\ exists ff_q_ecb_power_product_successor. ff_u_ecb_power_product = ff_q_ecb_power_product_successor * S ((S (S ff_i_ecb_power_product)) * ff_v_ecb_power_product) + (ff_s_ecb_power_product))) /\ ff_s_ecb_power_product = ff_r_ecb_power_product * ff_p_ecb_power_product)))))))) -> ((((exists qr_x_ecb_qres. exists qr_u_ecb_qres qr_v_ecb_qres. qr_x_ecb_qres * qr_x_ecb_qres + p * qr_u_ecb_qres = a + p * qr_v_ecb_qres) /\ (exists wpp_mod_left_ecb_mod_one wpp_mod_right_ecb_mod_one. (A) + p * wpp_mod_left_ecb_mod_one = (1) + p * wpp_mod_right_ecb_mod_one)) \/ ((~(exists qr_x_ecb_qres. exists qr_u_ecb_qres qr_v_ecb_qres. qr_x_ecb_qres * qr_x_ecb_qres + p * qr_u_ecb_qres = a + p * qr_v_ecb_qres)) /\ (exists wpp_mod_left_ecb_mod_predecessor wpp_mod_right_ecb_mod_predecessor. (A) + p * wpp_mod_left_ecb_mod_predecessor = (n) + p * wpp_mod_right_ecb_mod_predecessor))))

Structural proof guide

Generated structural guide

Every bounded nonzero input lands constructively in exactly the appropriate Euler endpoint.

Use the direct prerequisites prime_nonzero, bounded_nonzero_not_divides, quadratic_residue_decidable_nonzero, quadratic_residue_half_power_mod_one, quadratic_nonresidue_half_power_mod_predecessor, add_succ_left, mul_comm, zero_add as previously established PA formulas.

The proof proceeds by case analysis (1), intermediate claims (5), equality transport (2), certified simplification (2).

Referenced ingredients

Proof neighborhood

Direct dependencies

Direct dependents

Formal native tactic body

Dependencies are introduced as named hypotheses before line 1. Linked names are exact direct references. This Alpha-v16 checked-use theorem is independently kernel-checked when replayed; it is not a Stable theorem.

  1. 0001intro p
  2. 0002intro a
  3. 0003intro n
  4. 0004intro h
  5. 0005intro A
  6. 0006intro hpn
  7. 0007intro hp
  8. 0008intro ha0
  9. 0009intro hap
  10. 0010intro heven
  11. 0011intro hpower
  12. 0012have hp0 : ~(p = 0)
  13. 0013intro hpzero
  14. 0014specialize prime_nonzero p
  15. 0015apply prime_nonzero
  16. 0016exact hp
  17. 0017exact hpzero
  18. 0018have hnotdiv : ~(exists frm_factor_ecb_not_divisor. a = p * frm_factor_ecb_not_divisor)
  19. 0019intro hdiv
  20. 0020specialize bounded_nonzero_not_divides p
  21. 0021specialize bounded_nonzero_not_divides a
  22. 0022apply bounded_nonzero_not_divides
  23. 0023exact ha0
  24. 0024exact hap
  25. 0025exact hdiv
  26. 0026have hdouble : h + h = 2 * h
  27. 0027trans h * 2
  28. 0028simp [zero_add]
  29. 0029specialize mul_comm h
  30. 0030specialize mul_comm 2
  31. 0031apply mul_comm
  32. 0032have hodd : p = 2 * h + 1
  33. 0033trans S n
  34. 0034exact hpn
  35. 0035rewrite heven
  36. 0036rewrite hdouble
  37. 0037simp [add_succ_left]
  38. 0038have hdec : (exists qr_x_ecb_qres. exists qr_u_ecb_qres qr_v_ecb_qres. qr_x_ecb_qres * qr_x_ecb_qres + p * qr_u_ecb_qres = a + p * qr_v_ecb_qres) \/ ~(exists qr_x_ecb_qres. exists qr_u_ecb_qres qr_v_ecb_qres. qr_x_ecb_qres * qr_x_ecb_qres + p * qr_u_ecb_qres = a + p * qr_v_ecb_qres)
  39. 0039specialize quadratic_residue_decidable_nonzero p
  40. 0040specialize quadratic_residue_decidable_nonzero a
  41. 0041apply quadratic_residue_decidable_nonzero
  42. 0042exact hp0
  43. 0043cases hdec
  44. 0044left
  45. 0045split
  46. 0046exact hdec_left
  47. 0047specialize quadratic_residue_half_power_mod_one p
  48. 0048specialize quadratic_residue_half_power_mod_one h
  49. 0049specialize quadratic_residue_half_power_mod_one a
  50. 0050specialize quadratic_residue_half_power_mod_one A
  51. 0051apply quadratic_residue_half_power_mod_one
  52. 0052exact hodd
  53. 0053exact hp
  54. 0054exact hnotdiv
  55. 0055exact hdec_left
  56. 0056exact hpower
  57. 0057right
  58. 0058split
  59. 0059exact hdec_right
  60. 0060specialize quadratic_nonresidue_half_power_mod_predecessor p
  61. 0061specialize quadratic_nonresidue_half_power_mod_predecessor a
  62. 0062specialize quadratic_nonresidue_half_power_mod_predecessor n
  63. 0063specialize quadratic_nonresidue_half_power_mod_predecessor h
  64. 0064specialize quadratic_nonresidue_half_power_mod_predecessor A
  65. 0065apply quadratic_nonresidue_half_power_mod_predecessor
  66. 0066exact hpn
  67. 0067exact hp
  68. 0068exact ha0
  69. 0069exact hap
  70. 0070exact hdec_right
  71. 0071exact heven
  72. 0072exact hpower