PA008K

prime_range_product_coprime

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

The product 1*...*(p-1) is coprime to a prime p.

Exact expanded PA statement

forall p n b c F. p = S n -> ((~(p = 1) /\ forall frp_prime_left_prime_p frp_prime_right_prime_p. p = frp_prime_left_prime_p * frp_prime_right_prime_p -> frp_prime_left_prime_p = 1 \/ frp_prime_right_prime_p = 1)) -> (forall ff_i_frp_range_prime_range. (exists ff_lt_frp_range_prime_range_bound. ff_lt_frp_range_prime_range_bound + S ff_i_frp_range_prime_range = n) -> (((exists ff_h_frp_range_prime_range_decoded. ff_h_frp_range_prime_range_decoded + S (1 + ff_i_frp_range_prime_range) = S ((S (ff_i_frp_range_prime_range)) * c)) /\ exists ff_q_frp_range_prime_range_decoded. b = ff_q_frp_range_prime_range_decoded * S ((S (ff_i_frp_range_prime_range)) * c) + (1 + ff_i_frp_range_prime_range)))) -> (exists ff_u_prime_product ff_v_prime_product. ((((exists ff_h_prime_product_start. ff_h_prime_product_start + S (1) = S ((S (0)) * ff_v_prime_product)) /\ exists ff_q_prime_product_start. ff_u_prime_product = ff_q_prime_product_start * S ((S (0)) * ff_v_prime_product) + (1))) /\ ((((exists ff_h_prime_product_terminal. ff_h_prime_product_terminal + S (F) = S ((S (n)) * ff_v_prime_product)) /\ exists ff_q_prime_product_terminal. ff_u_prime_product = ff_q_prime_product_terminal * S ((S (n)) * ff_v_prime_product) + (F))) /\ forall ff_i_prime_product. (exists ff_lt_prime_product_bound. ff_lt_prime_product_bound + S ff_i_prime_product = n) -> exists ff_p_prime_product ff_r_prime_product ff_s_prime_product. ((((exists ff_h_prime_product_factor. ff_h_prime_product_factor + S (ff_p_prime_product) = S ((S (ff_i_prime_product)) * c)) /\ exists ff_q_prime_product_factor. b = ff_q_prime_product_factor * S ((S (ff_i_prime_product)) * c) + (ff_p_prime_product))) /\ ((((exists ff_h_prime_product_partial. ff_h_prime_product_partial + S (ff_r_prime_product) = S ((S (ff_i_prime_product)) * ff_v_prime_product)) /\ exists ff_q_prime_product_partial. ff_u_prime_product = ff_q_prime_product_partial * S ((S (ff_i_prime_product)) * ff_v_prime_product) + (ff_r_prime_product))) /\ ((((exists ff_h_prime_product_successor. ff_h_prime_product_successor + S (ff_s_prime_product) = S ((S (S ff_i_prime_product)) * ff_v_prime_product)) /\ exists ff_q_prime_product_successor. ff_u_prime_product = ff_q_prime_product_successor * S ((S (S ff_i_prime_product)) * ff_v_prime_product) + (ff_s_prime_product))) /\ ff_s_prime_product = ff_r_prime_product * ff_p_prime_product)))))) -> (forall frp_divisor_prime_product_result. (exists frp_left_factor_prime_product_result. F = frp_divisor_prime_product_result * frp_left_factor_prime_product_result) -> (exists frp_right_factor_prime_product_result. p = frp_divisor_prime_product_result * frp_right_factor_prime_product_result) -> frp_divisor_prime_product_result = 1)

Structural proof guide

Generated structural guide

The product 1*...*(p-1) is coprime to a prime p.

Use the direct prerequisites beta_range_one_entry_eq_succ, beta_product_pointwise_coprime, succ_ne_zero, succ_le_succ, divisor_le_nonzero, lt_not_le, prime_not_divides_coprime, coprime_symm as previously established PA formulas.

The proof proceeds by intermediate claims (7), equality transport (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 n
  3. 0003intro b
  4. 0004intro c
  5. 0005intro F
  6. 0006intro hpn
  7. 0007intro hp
  8. 0008intro hrange
  9. 0009intro hproduct
  10. 0010have hpointwise : forall frp_index_prime_pointwise frp_factor_prime_pointwise. (exists frp_gap_prime_pointwise_bound. frp_gap_prime_pointwise_bound + S frp_index_prime_pointwise = n) -> (((exists ff_h_frp_prime_pointwise_decoded. ff_h_frp_prime_pointwise_decoded + S (frp_factor_prime_pointwise) = S ((S (frp_index_prime_pointwise)) * c)) /\ exists ff_q_frp_prime_pointwise_decoded. b = ff_q_frp_prime_pointwise_decoded * S ((S (frp_index_prime_pointwise)) * c) + (frp_factor_prime_pointwise))) -> (forall frp_divisor_prime_pointwise_coprime. (exists frp_left_factor_prime_pointwise_coprime. frp_factor_prime_pointwise = frp_divisor_prime_pointwise_coprime * frp_left_factor_prime_pointwise_coprime) -> (exists frp_right_factor_prime_pointwise_coprime. p = frp_divisor_prime_pointwise_coprime * frp_right_factor_prime_pointwise_coprime) -> frp_divisor_prime_pointwise_coprime = 1)
  11. 0011intro i
  12. 0012intro x
  13. 0013intro hi
  14. 0014intro hx
  15. 0015have hvalue : x = S i
  16. 0016specialize beta_range_one_entry_eq_succ b
  17. 0017specialize beta_range_one_entry_eq_succ c
  18. 0018specialize beta_range_one_entry_eq_succ n
  19. 0019specialize beta_range_one_entry_eq_succ i
  20. 0020specialize beta_range_one_entry_eq_succ x
  21. 0021apply beta_range_one_entry_eq_succ
  22. 0022exact hrange
  23. 0023exact hi
  24. 0024exact hx
  25. 0025have hx0 : ~(x = 0)
  26. 0026intro hxzero
  27. 0027specialize succ_ne_zero i
  28. 0028apply succ_ne_zero
  29. 0029trans x
  30. 0030symm
  31. 0031exact hvalue
  32. 0032exact hxzero
  33. 0033have hxltp : exists h. h + S x = p
  34. 0034rewrite hvalue
  35. 0035rewrite hpn
  36. 0036specialize succ_le_succ (S i)
  37. 0037specialize succ_le_succ n
  38. 0038apply succ_le_succ
  39. 0039exact hi
  40. 0040have hnotdiv : ~(exists k. x = p * k)
  41. 0041intro hdiv
  42. 0042have hle : exists k. k + p = x
  43. 0043specialize divisor_le_nonzero p
  44. 0044specialize divisor_le_nonzero x
  45. 0045apply divisor_le_nonzero
  46. 0046exact hx0
  47. 0047exact hdiv
  48. 0048specialize lt_not_le x
  49. 0049specialize lt_not_le p
  50. 0050apply lt_not_le
  51. 0051exact hxltp
  52. 0052exact hle
  53. 0053have hpx : forall frp_divisor_prime_factor. (exists frp_left_factor_prime_factor. p = frp_divisor_prime_factor * frp_left_factor_prime_factor) -> (exists frp_right_factor_prime_factor. x = frp_divisor_prime_factor * frp_right_factor_prime_factor) -> frp_divisor_prime_factor = 1
  54. 0054specialize prime_not_divides_coprime p
  55. 0055specialize prime_not_divides_coprime x
  56. 0056apply prime_not_divides_coprime
  57. 0057exact hp
  58. 0058exact hnotdiv
  59. 0059specialize coprime_symm p
  60. 0060specialize coprime_symm x
  61. 0061apply coprime_symm
  62. 0062exact hpx
  63. 0063specialize beta_product_pointwise_coprime p
  64. 0064specialize beta_product_pointwise_coprime b
  65. 0065specialize beta_product_pointwise_coprime c
  66. 0066specialize beta_product_pointwise_coprime n
  67. 0067specialize beta_product_pointwise_coprime F
  68. 0068apply beta_product_pointwise_coprime
  69. 0069exact hpointwise
  70. 0070exact hproduct