PA008L

fermat_predecessor_exponent_mod_one

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

Fermat's theorem for the native predecessor exponent p-1.

Exact expanded PA statement

forall p n a A. p = S n -> ((~(p = 1) /\ forall frm_prime_left_predecessor_prime frm_prime_right_predecessor_prime. p = frm_prime_left_predecessor_prime * frm_prime_right_predecessor_prime -> frm_prime_left_predecessor_prime = 1 \/ frm_prime_right_predecessor_prime = 1)) -> (~(exists frm_factor_predecessor_multiplier. a = p * frm_factor_predecessor_multiplier)) -> (exists ff_b_predecessor_power ff_c_predecessor_power. ((forall ff_i_predecessor_power_repeat. (exists ff_lt_predecessor_power_repeat_bound. ff_lt_predecessor_power_repeat_bound + S ff_i_predecessor_power_repeat = n) -> (((exists ff_h_predecessor_power_repeat_decoded. ff_h_predecessor_power_repeat_decoded + S (a) = S ((S (ff_i_predecessor_power_repeat)) * ff_c_predecessor_power)) /\ exists ff_q_predecessor_power_repeat_decoded. ff_b_predecessor_power = ff_q_predecessor_power_repeat_decoded * S ((S (ff_i_predecessor_power_repeat)) * ff_c_predecessor_power) + (a)))) /\ (exists ff_u_predecessor_power_product ff_v_predecessor_power_product. ((((exists ff_h_predecessor_power_product_start. ff_h_predecessor_power_product_start + S (1) = S ((S (0)) * ff_v_predecessor_power_product)) /\ exists ff_q_predecessor_power_product_start. ff_u_predecessor_power_product = ff_q_predecessor_power_product_start * S ((S (0)) * ff_v_predecessor_power_product) + (1))) /\ ((((exists ff_h_predecessor_power_product_terminal. ff_h_predecessor_power_product_terminal + S (A) = S ((S (n)) * ff_v_predecessor_power_product)) /\ exists ff_q_predecessor_power_product_terminal. ff_u_predecessor_power_product = ff_q_predecessor_power_product_terminal * S ((S (n)) * ff_v_predecessor_power_product) + (A))) /\ forall ff_i_predecessor_power_product. (exists ff_lt_predecessor_power_product_bound. ff_lt_predecessor_power_product_bound + S ff_i_predecessor_power_product = n) -> exists ff_p_predecessor_power_product ff_r_predecessor_power_product ff_s_predecessor_power_product. ((((exists ff_h_predecessor_power_product_factor. ff_h_predecessor_power_product_factor + S (ff_p_predecessor_power_product) = S ((S (ff_i_predecessor_power_product)) * ff_c_predecessor_power)) /\ exists ff_q_predecessor_power_product_factor. ff_b_predecessor_power = ff_q_predecessor_power_product_factor * S ((S (ff_i_predecessor_power_product)) * ff_c_predecessor_power) + (ff_p_predecessor_power_product))) /\ ((((exists ff_h_predecessor_power_product_partial. ff_h_predecessor_power_product_partial + S (ff_r_predecessor_power_product) = S ((S (ff_i_predecessor_power_product)) * ff_v_predecessor_power_product)) /\ exists ff_q_predecessor_power_product_partial. ff_u_predecessor_power_product = ff_q_predecessor_power_product_partial * S ((S (ff_i_predecessor_power_product)) * ff_v_predecessor_power_product) + (ff_r_predecessor_power_product))) /\ ((((exists ff_h_predecessor_power_product_successor. ff_h_predecessor_power_product_successor + S (ff_s_predecessor_power_product) = S ((S (S ff_i_predecessor_power_product)) * ff_v_predecessor_power_product)) /\ exists ff_q_predecessor_power_product_successor. ff_u_predecessor_power_product = ff_q_predecessor_power_product_successor * S ((S (S ff_i_predecessor_power_product)) * ff_v_predecessor_power_product) + (ff_s_predecessor_power_product))) /\ ff_s_predecessor_power_product = ff_r_predecessor_power_product * ff_p_predecessor_power_product)))))))) -> (exists fep_mod_left_predecessor_result fep_mod_right_predecessor_result. A + p * fep_mod_left_predecessor_result = 1 + p * fep_mod_right_predecessor_result)

Structural proof guide

Generated structural guide

Fermat's theorem for the native predecessor exponent p-1.

Use the direct prerequisites factorial_exists, prime_mul_residue_product_balance, prime_range_product_coprime, prime_nonzero, mod_eq_cancel_coprime, mul_comm, mul_one as previously established PA formulas.

The proof proceeds by case analysis (6), intermediate claims (4).

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 a
  4. 0004intro A
  5. 0005intro hpn
  6. 0006intro hp
  7. 0007intro hnotdiv
  8. 0008intro hA
  9. 0009specialize factorial_exists n
  10. 0010cases factorial_exists
  11. 0011cases factorial_exists_witness
  12. 0012cases factorial_exists_witness_witness
  13. 0013cases factorial_exists_witness_witness_witness
  14. 0014have hbalance : exists fsp_product_mod_left_predecessor_balance fsp_product_mod_right_predecessor_balance. (A * x) + p * fsp_product_mod_left_predecessor_balance = x + p * fsp_product_mod_right_predecessor_balance
  15. 0015specialize prime_mul_residue_product_balance p
  16. 0016specialize prime_mul_residue_product_balance n
  17. 0017specialize prime_mul_residue_product_balance a
  18. 0018specialize prime_mul_residue_product_balance x1
  19. 0019specialize prime_mul_residue_product_balance x2
  20. 0020specialize prime_mul_residue_product_balance x
  21. 0021specialize prime_mul_residue_product_balance A
  22. 0022apply prime_mul_residue_product_balance
  23. 0023exact hpn
  24. 0024exact hp
  25. 0025exact hnotdiv
  26. 0026exact factorial_exists_witness_witness_witness_left
  27. 0027exact factorial_exists_witness_witness_witness_right
  28. 0028exact hA
  29. 0029have hcop : forall frp_divisor_predecessor_coprime. (exists frp_left_factor_predecessor_coprime. x = frp_divisor_predecessor_coprime * frp_left_factor_predecessor_coprime) -> (exists frp_right_factor_predecessor_coprime. p = frp_divisor_predecessor_coprime * frp_right_factor_predecessor_coprime) -> frp_divisor_predecessor_coprime = 1
  30. 0030specialize prime_range_product_coprime p
  31. 0031specialize prime_range_product_coprime n
  32. 0032specialize prime_range_product_coprime x1
  33. 0033specialize prime_range_product_coprime x2
  34. 0034specialize prime_range_product_coprime x
  35. 0035apply prime_range_product_coprime
  36. 0036exact hpn
  37. 0037exact hp
  38. 0038exact factorial_exists_witness_witness_witness_left
  39. 0039exact factorial_exists_witness_witness_witness_right
  40. 0040have hp0 : ~(p = 0)
  41. 0041intro hpzero
  42. 0042specialize prime_nonzero p
  43. 0043apply prime_nonzero
  44. 0044exact hp
  45. 0045exact hpzero
  46. 0046have hscaled : exists fep_product_mod_left_predecessor_normalized fep_product_mod_right_predecessor_normalized. (x * A) + p * fep_product_mod_left_predecessor_normalized = (x * 1) + p * fep_product_mod_right_predecessor_normalized
  47. 0047cases hbalance
  48. 0048cases hbalance_witness
  49. 0049exists x3
  50. 0050exists x4
  51. 0051trans (A * x) + p * x3
  52. 0052congr
  53. 0053apply mul_comm
  54. 0054refl
  55. 0055trans x + p * x4
  56. 0056exact hbalance_witness_witness
  57. 0057congr
  58. 0058symm
  59. 0059apply mul_one
  60. 0060refl
  61. 0061specialize mod_eq_cancel_coprime p
  62. 0062specialize mod_eq_cancel_coprime x
  63. 0063specialize mod_eq_cancel_coprime A
  64. 0064specialize mod_eq_cancel_coprime 1
  65. 0065apply mod_eq_cancel_coprime
  66. 0066exact hp0
  67. 0067exact hcop
  68. 0068exact hscaled