PA0082

prime_positive_bounded_product_coprime

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

A product of positive residues below a prime is coprime to that prime.

Exact expanded PA statement

forall p b c l F. ((~(p = 1) /\ forall frp_prime_left_prime_product_prime frp_prime_right_prime_product_prime. p = frp_prime_left_prime_product_prime * frp_prime_right_prime_product_prime -> frp_prime_left_prime_product_prime = 1 \/ frp_prime_right_prime_product_prime = 1)) -> (forall fppc_index_prime_product_bounds fppc_factor_prime_product_bounds. (exists frp_gap_prime_product_bounds_index_bound. frp_gap_prime_product_bounds_index_bound + S fppc_index_prime_product_bounds = l) -> (((exists ff_h_fppc_prime_product_bounds_decoded. ff_h_fppc_prime_product_bounds_decoded + S (fppc_factor_prime_product_bounds) = S ((S (fppc_index_prime_product_bounds)) * c)) /\ exists ff_q_fppc_prime_product_bounds_decoded. b = ff_q_fppc_prime_product_bounds_decoded * S ((S (fppc_index_prime_product_bounds)) * c) + (fppc_factor_prime_product_bounds))) -> (~(fppc_factor_prime_product_bounds = 0) /\ (exists frp_gap_prime_product_bounds_factor_bound. frp_gap_prime_product_bounds_factor_bound + S fppc_factor_prime_product_bounds = p))) -> (exists ff_u_prime_product_product ff_v_prime_product_product. ((((exists ff_h_prime_product_product_start. ff_h_prime_product_product_start + S (1) = S ((S (0)) * ff_v_prime_product_product)) /\ exists ff_q_prime_product_product_start. ff_u_prime_product_product = ff_q_prime_product_product_start * S ((S (0)) * ff_v_prime_product_product) + (1))) /\ ((((exists ff_h_prime_product_product_terminal. ff_h_prime_product_product_terminal + S (F) = S ((S (l)) * ff_v_prime_product_product)) /\ exists ff_q_prime_product_product_terminal. ff_u_prime_product_product = ff_q_prime_product_product_terminal * S ((S (l)) * ff_v_prime_product_product) + (F))) /\ forall ff_i_prime_product_product. (exists ff_lt_prime_product_product_bound. ff_lt_prime_product_product_bound + S ff_i_prime_product_product = l) -> exists ff_p_prime_product_product ff_r_prime_product_product ff_s_prime_product_product. ((((exists ff_h_prime_product_product_factor. ff_h_prime_product_product_factor + S (ff_p_prime_product_product) = S ((S (ff_i_prime_product_product)) * c)) /\ exists ff_q_prime_product_product_factor. b = ff_q_prime_product_product_factor * S ((S (ff_i_prime_product_product)) * c) + (ff_p_prime_product_product))) /\ ((((exists ff_h_prime_product_product_partial. ff_h_prime_product_product_partial + S (ff_r_prime_product_product) = S ((S (ff_i_prime_product_product)) * ff_v_prime_product_product)) /\ exists ff_q_prime_product_product_partial. ff_u_prime_product_product = ff_q_prime_product_product_partial * S ((S (ff_i_prime_product_product)) * ff_v_prime_product_product) + (ff_r_prime_product_product))) /\ ((((exists ff_h_prime_product_product_successor. ff_h_prime_product_product_successor + S (ff_s_prime_product_product) = S ((S (S ff_i_prime_product_product)) * ff_v_prime_product_product)) /\ exists ff_q_prime_product_product_successor. ff_u_prime_product_product = ff_q_prime_product_product_successor * S ((S (S ff_i_prime_product_product)) * ff_v_prime_product_product) + (ff_s_prime_product_product))) /\ ff_s_prime_product_product = ff_r_prime_product_product * ff_p_prime_product_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

A product of positive residues below a prime is coprime to that prime.

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

The proof proceeds by case analysis (1), intermediate claims (5).

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 b
  3. 0003intro c
  4. 0004intro l
  5. 0005intro F
  6. 0006intro hp
  7. 0007intro hbounded
  8. 0008intro hproduct
  9. 0009have hpointwise : forall frp_index_prime_product_pointwise frp_factor_prime_product_pointwise. (exists frp_gap_prime_product_pointwise_bound. frp_gap_prime_product_pointwise_bound + S frp_index_prime_product_pointwise = l) -> (((exists ff_h_frp_prime_product_pointwise_decoded. ff_h_frp_prime_product_pointwise_decoded + S (frp_factor_prime_product_pointwise) = S ((S (frp_index_prime_product_pointwise)) * c)) /\ exists ff_q_frp_prime_product_pointwise_decoded. b = ff_q_frp_prime_product_pointwise_decoded * S ((S (frp_index_prime_product_pointwise)) * c) + (frp_factor_prime_product_pointwise))) -> (forall frp_divisor_prime_product_pointwise_coprime. (exists frp_left_factor_prime_product_pointwise_coprime. frp_factor_prime_product_pointwise = frp_divisor_prime_product_pointwise_coprime * frp_left_factor_prime_product_pointwise_coprime) -> (exists frp_right_factor_prime_product_pointwise_coprime. p = frp_divisor_prime_product_pointwise_coprime * frp_right_factor_prime_product_pointwise_coprime) -> frp_divisor_prime_product_pointwise_coprime = 1)
  10. 0010intro i
  11. 0011intro x
  12. 0012intro hi
  13. 0013intro hx
  14. 0014have hbounds : (~(x = 0) /\ (exists frp_gap_prime_product_local_bound. frp_gap_prime_product_local_bound + S x = p))
  15. 0015specialize hbounded i
  16. 0016specialize hbounded x
  17. 0017apply hbounded
  18. 0018exact hi
  19. 0019exact hx
  20. 0020cases hbounds
  21. 0021have hnotdiv : ~(exists k. x = p * k)
  22. 0022intro hdiv
  23. 0023have hle : exists k. k + p = x
  24. 0024specialize divisor_le_nonzero p
  25. 0025specialize divisor_le_nonzero x
  26. 0026apply divisor_le_nonzero
  27. 0027exact hbounds_left
  28. 0028exact hdiv
  29. 0029specialize lt_not_le x
  30. 0030specialize lt_not_le p
  31. 0031apply lt_not_le
  32. 0032exact hbounds_right
  33. 0033exact hle
  34. 0034have hprimecop : forall frp_divisor_prime_product_factor. (exists frp_left_factor_prime_product_factor. p = frp_divisor_prime_product_factor * frp_left_factor_prime_product_factor) -> (exists frp_right_factor_prime_product_factor. x = frp_divisor_prime_product_factor * frp_right_factor_prime_product_factor) -> frp_divisor_prime_product_factor = 1
  35. 0035specialize prime_not_divides_coprime p
  36. 0036specialize prime_not_divides_coprime x
  37. 0037apply prime_not_divides_coprime
  38. 0038exact hp
  39. 0039exact hnotdiv
  40. 0040specialize coprime_symm p
  41. 0041specialize coprime_symm x
  42. 0042apply coprime_symm
  43. 0043exact hprimecop
  44. 0044specialize beta_product_pointwise_coprime p
  45. 0045specialize beta_product_pointwise_coprime b
  46. 0046specialize beta_product_pointwise_coprime c
  47. 0047specialize beta_product_pointwise_coprime l
  48. 0048specialize beta_product_pointwise_coprime F
  49. 0049apply beta_product_pointwise_coprime
  50. 0050exact hpointwise
  51. 0051exact hproduct