HL0009

beta_horner_simple_canonical_representative

Alpha v34 independently verified · alpha_closed; checked-use authorized; not Stable

An unrestricted natural input can be normalized without losing its exact polynomial root or simple derivative.

Current library: Alpha v34, 4,223 checked-use theorems; Stable remains 432. Historical first admissions, original proof editions, and non-admitted aliases are preserved. Exact original first-admission records.

Exact expanded first-order arithmetic statement

forall b c a l n d m p s. ~(p = 0) -> ~(m = 0) -> (exists ff_u_hd_hpl_pair ff_v_hd_hpl_pair ff_d_hd_hpl_pair ff_e_hd_hpl_pair. ((((((exists fs_h_ph_hd_hpl_pair_body_value_start. fs_h_ph_hd_hpl_pair_body_value_start + S (0) = S ((S (0)) * ff_v_hd_hpl_pair)) /\ exists fs_q_ph_hd_hpl_pair_body_value_start. ff_u_hd_hpl_pair = fs_q_ph_hd_hpl_pair_body_value_start * S ((S (0)) * ff_v_hd_hpl_pair) + (0))) /\ ((((exists fs_h_ph_hd_hpl_pair_body_value_terminal. fs_h_ph_hd_hpl_pair_body_value_terminal + S (n) = S ((S (l)) * ff_v_hd_hpl_pair)) /\ exists fs_q_ph_hd_hpl_pair_body_value_terminal. ff_u_hd_hpl_pair = fs_q_ph_hd_hpl_pair_body_value_terminal * S ((S (l)) * ff_v_hd_hpl_pair) + (n))) /\ forall ff_i_ph_hd_hpl_pair_body_value_steps. (exists ph_bound_hd_hpl_pair_body_value_steps. ph_bound_hd_hpl_pair_body_value_steps + S ff_i_ph_hd_hpl_pair_body_value_steps = l) -> exists ff_coefficient_ph_hd_hpl_pair_body_value_steps ff_previous_ph_hd_hpl_pair_body_value_steps ff_current_ph_hd_hpl_pair_body_value_steps. ((((exists fs_h_ph_hd_hpl_pair_body_value_steps_coefficient. fs_h_ph_hd_hpl_pair_body_value_steps_coefficient + S (ff_coefficient_ph_hd_hpl_pair_body_value_steps) = S ((S (ff_i_ph_hd_hpl_pair_body_value_steps)) * c)) /\ exists fs_q_ph_hd_hpl_pair_body_value_steps_coefficient. b = fs_q_ph_hd_hpl_pair_body_value_steps_coefficient * S ((S (ff_i_ph_hd_hpl_pair_body_value_steps)) * c) + (ff_coefficient_ph_hd_hpl_pair_body_value_steps))) /\ ((((exists fs_h_ph_hd_hpl_pair_body_value_steps_before. fs_h_ph_hd_hpl_pair_body_value_steps_before + S (ff_previous_ph_hd_hpl_pair_body_value_steps) = S ((S (ff_i_ph_hd_hpl_pair_body_value_steps)) * ff_v_hd_hpl_pair)) /\ exists fs_q_ph_hd_hpl_pair_body_value_steps_before. ff_u_hd_hpl_pair = fs_q_ph_hd_hpl_pair_body_value_steps_before * S ((S (ff_i_ph_hd_hpl_pair_body_value_steps)) * ff_v_hd_hpl_pair) + (ff_previous_ph_hd_hpl_pair_body_value_steps))) /\ ((((exists fs_h_ph_hd_hpl_pair_body_value_steps_after. fs_h_ph_hd_hpl_pair_body_value_steps_after + S (ff_current_ph_hd_hpl_pair_body_value_steps) = S ((S (S ff_i_ph_hd_hpl_pair_body_value_steps)) * ff_v_hd_hpl_pair)) /\ exists fs_q_ph_hd_hpl_pair_body_value_steps_after. ff_u_hd_hpl_pair = fs_q_ph_hd_hpl_pair_body_value_steps_after * S ((S (S ff_i_ph_hd_hpl_pair_body_value_steps)) * ff_v_hd_hpl_pair) + (ff_current_ph_hd_hpl_pair_body_value_steps))) /\ ff_current_ph_hd_hpl_pair_body_value_steps = ff_previous_ph_hd_hpl_pair_body_value_steps * a + ff_coefficient_ph_hd_hpl_pair_body_value_steps)))))) /\ (((((exists fs_h_ph_hd_hpl_pair_body_derivative_start. fs_h_ph_hd_hpl_pair_body_derivative_start + S (0) = S ((S (0)) * ff_e_hd_hpl_pair)) /\ exists fs_q_ph_hd_hpl_pair_body_derivative_start. ff_d_hd_hpl_pair = fs_q_ph_hd_hpl_pair_body_derivative_start * S ((S (0)) * ff_e_hd_hpl_pair) + (0))) /\ ((((exists fs_h_ph_hd_hpl_pair_body_derivative_terminal. fs_h_ph_hd_hpl_pair_body_derivative_terminal + S (d) = S ((S (l)) * ff_e_hd_hpl_pair)) /\ exists fs_q_ph_hd_hpl_pair_body_derivative_terminal. ff_d_hd_hpl_pair = fs_q_ph_hd_hpl_pair_body_derivative_terminal * S ((S (l)) * ff_e_hd_hpl_pair) + (d))) /\ forall ff_i_ph_hd_hpl_pair_body_derivative_steps. (exists ph_bound_hd_hpl_pair_body_derivative_steps. ph_bound_hd_hpl_pair_body_derivative_steps + S ff_i_ph_hd_hpl_pair_body_derivative_steps = l) -> exists ff_coefficient_ph_hd_hpl_pair_body_derivative_steps ff_previous_ph_hd_hpl_pair_body_derivative_steps ff_current_ph_hd_hpl_pair_body_derivative_steps. ((((exists fs_h_ph_hd_hpl_pair_body_derivative_steps_coefficient. fs_h_ph_hd_hpl_pair_body_derivative_steps_coefficient + S (ff_coefficient_ph_hd_hpl_pair_body_derivative_steps) = S ((S (ff_i_ph_hd_hpl_pair_body_derivative_steps)) * ff_v_hd_hpl_pair)) /\ exists fs_q_ph_hd_hpl_pair_body_derivative_steps_coefficient. ff_u_hd_hpl_pair = fs_q_ph_hd_hpl_pair_body_derivative_steps_coefficient * S ((S (ff_i_ph_hd_hpl_pair_body_derivative_steps)) * ff_v_hd_hpl_pair) + (ff_coefficient_ph_hd_hpl_pair_body_derivative_steps))) /\ ((((exists fs_h_ph_hd_hpl_pair_body_derivative_steps_before. fs_h_ph_hd_hpl_pair_body_derivative_steps_before + S (ff_previous_ph_hd_hpl_pair_body_derivative_steps) = S ((S (ff_i_ph_hd_hpl_pair_body_derivative_steps)) * ff_e_hd_hpl_pair)) /\ exists fs_q_ph_hd_hpl_pair_body_derivative_steps_before. ff_d_hd_hpl_pair = fs_q_ph_hd_hpl_pair_body_derivative_steps_before * S ((S (ff_i_ph_hd_hpl_pair_body_derivative_steps)) * ff_e_hd_hpl_pair) + (ff_previous_ph_hd_hpl_pair_body_derivative_steps))) /\ ((((exists fs_h_ph_hd_hpl_pair_body_derivative_steps_after. fs_h_ph_hd_hpl_pair_body_derivative_steps_after + S (ff_current_ph_hd_hpl_pair_body_derivative_steps) = S ((S (S ff_i_ph_hd_hpl_pair_body_derivative_steps)) * ff_e_hd_hpl_pair)) /\ exists fs_q_ph_hd_hpl_pair_body_derivative_steps_after. ff_d_hd_hpl_pair = fs_q_ph_hd_hpl_pair_body_derivative_steps_after * S ((S (S ff_i_ph_hd_hpl_pair_body_derivative_steps)) * ff_e_hd_hpl_pair) + (ff_current_ph_hd_hpl_pair_body_derivative_steps))) /\ ff_current_ph_hd_hpl_pair_body_derivative_steps = ff_previous_ph_hd_hpl_pair_body_derivative_steps * a + ff_coefficient_ph_hd_hpl_pair_body_derivative_steps)))))))) -> m = p * s -> (exists hgcrt_mod_left_hpl_mod hgcrt_mod_right_hpl_mod. n + m * hgcrt_mod_left_hpl_mod = 0 + m * hgcrt_mod_right_hpl_mod) -> (forall hmi_divisor_hpl_coprime. (exists hmi_left_factor_hpl_coprime. d = hmi_divisor_hpl_coprime * hmi_left_factor_hpl_coprime) -> (exists hmi_right_factor_hpl_coprime. p = hmi_divisor_hpl_coprime * hmi_right_factor_hpl_coprime) -> hmi_divisor_hpl_coprime = 1) -> exists r. ((exists hpl_gap_bound. hpl_gap_bound + S (r) = (m)) /\ ((exists hgcrt_mod_left_hpl_mod hgcrt_mod_right_hpl_mod. r + m * hgcrt_mod_left_hpl_mod = a + m * hgcrt_mod_right_hpl_mod) /\ (exists hpl_value_simple hpl_derivative_simple. ((exists ff_u_hd_hpl_simple ff_v_hd_hpl_simple ff_d_hd_hpl_simple ff_e_hd_hpl_simple. ((((((exists fs_h_ph_hd_hpl_simple_body_value_start. fs_h_ph_hd_hpl_simple_body_value_start + S (0) = S ((S (0)) * ff_v_hd_hpl_simple)) /\ exists fs_q_ph_hd_hpl_simple_body_value_start. ff_u_hd_hpl_simple = fs_q_ph_hd_hpl_simple_body_value_start * S ((S (0)) * ff_v_hd_hpl_simple) + (0))) /\ ((((exists fs_h_ph_hd_hpl_simple_body_value_terminal. fs_h_ph_hd_hpl_simple_body_value_terminal + S (hpl_value_simple) = S ((S (l)) * ff_v_hd_hpl_simple)) /\ exists fs_q_ph_hd_hpl_simple_body_value_terminal. ff_u_hd_hpl_simple = fs_q_ph_hd_hpl_simple_body_value_terminal * S ((S (l)) * ff_v_hd_hpl_simple) + (hpl_value_simple))) /\ forall ff_i_ph_hd_hpl_simple_body_value_steps. (exists ph_bound_hd_hpl_simple_body_value_steps. ph_bound_hd_hpl_simple_body_value_steps + S ff_i_ph_hd_hpl_simple_body_value_steps = l) -> exists ff_coefficient_ph_hd_hpl_simple_body_value_steps ff_previous_ph_hd_hpl_simple_body_value_steps ff_current_ph_hd_hpl_simple_body_value_steps. ((((exists fs_h_ph_hd_hpl_simple_body_value_steps_coefficient. fs_h_ph_hd_hpl_simple_body_value_steps_coefficient + S (ff_coefficient_ph_hd_hpl_simple_body_value_steps) = S ((S (ff_i_ph_hd_hpl_simple_body_value_steps)) * c)) /\ exists fs_q_ph_hd_hpl_simple_body_value_steps_coefficient. b = fs_q_ph_hd_hpl_simple_body_value_steps_coefficient * S ((S (ff_i_ph_hd_hpl_simple_body_value_steps)) * c) + (ff_coefficient_ph_hd_hpl_simple_body_value_steps))) /\ ((((exists fs_h_ph_hd_hpl_simple_body_value_steps_before. fs_h_ph_hd_hpl_simple_body_value_steps_before + S (ff_previous_ph_hd_hpl_simple_body_value_steps) = S ((S (ff_i_ph_hd_hpl_simple_body_value_steps)) * ff_v_hd_hpl_simple)) /\ exists fs_q_ph_hd_hpl_simple_body_value_steps_before. ff_u_hd_hpl_simple = fs_q_ph_hd_hpl_simple_body_value_steps_before * S ((S (ff_i_ph_hd_hpl_simple_body_value_steps)) * ff_v_hd_hpl_simple) + (ff_previous_ph_hd_hpl_simple_body_value_steps))) /\ ((((exists fs_h_ph_hd_hpl_simple_body_value_steps_after. fs_h_ph_hd_hpl_simple_body_value_steps_after + S (ff_current_ph_hd_hpl_simple_body_value_steps) = S ((S (S ff_i_ph_hd_hpl_simple_body_value_steps)) * ff_v_hd_hpl_simple)) /\ exists fs_q_ph_hd_hpl_simple_body_value_steps_after. ff_u_hd_hpl_simple = fs_q_ph_hd_hpl_simple_body_value_steps_after * S ((S (S ff_i_ph_hd_hpl_simple_body_value_steps)) * ff_v_hd_hpl_simple) + (ff_current_ph_hd_hpl_simple_body_value_steps))) /\ ff_current_ph_hd_hpl_simple_body_value_steps = ff_previous_ph_hd_hpl_simple_body_value_steps * r + ff_coefficient_ph_hd_hpl_simple_body_value_steps)))))) /\ (((((exists fs_h_ph_hd_hpl_simple_body_derivative_start. fs_h_ph_hd_hpl_simple_body_derivative_start + S (0) = S ((S (0)) * ff_e_hd_hpl_simple)) /\ exists fs_q_ph_hd_hpl_simple_body_derivative_start. ff_d_hd_hpl_simple = fs_q_ph_hd_hpl_simple_body_derivative_start * S ((S (0)) * ff_e_hd_hpl_simple) + (0))) /\ ((((exists fs_h_ph_hd_hpl_simple_body_derivative_terminal. fs_h_ph_hd_hpl_simple_body_derivative_terminal + S (hpl_derivative_simple) = S ((S (l)) * ff_e_hd_hpl_simple)) /\ exists fs_q_ph_hd_hpl_simple_body_derivative_terminal. ff_d_hd_hpl_simple = fs_q_ph_hd_hpl_simple_body_derivative_terminal * S ((S (l)) * ff_e_hd_hpl_simple) + (hpl_derivative_simple))) /\ forall ff_i_ph_hd_hpl_simple_body_derivative_steps. (exists ph_bound_hd_hpl_simple_body_derivative_steps. ph_bound_hd_hpl_simple_body_derivative_steps + S ff_i_ph_hd_hpl_simple_body_derivative_steps = l) -> exists ff_coefficient_ph_hd_hpl_simple_body_derivative_steps ff_previous_ph_hd_hpl_simple_body_derivative_steps ff_current_ph_hd_hpl_simple_body_derivative_steps. ((((exists fs_h_ph_hd_hpl_simple_body_derivative_steps_coefficient. fs_h_ph_hd_hpl_simple_body_derivative_steps_coefficient + S (ff_coefficient_ph_hd_hpl_simple_body_derivative_steps) = S ((S (ff_i_ph_hd_hpl_simple_body_derivative_steps)) * ff_v_hd_hpl_simple)) /\ exists fs_q_ph_hd_hpl_simple_body_derivative_steps_coefficient. ff_u_hd_hpl_simple = fs_q_ph_hd_hpl_simple_body_derivative_steps_coefficient * S ((S (ff_i_ph_hd_hpl_simple_body_derivative_steps)) * ff_v_hd_hpl_simple) + (ff_coefficient_ph_hd_hpl_simple_body_derivative_steps))) /\ ((((exists fs_h_ph_hd_hpl_simple_body_derivative_steps_before. fs_h_ph_hd_hpl_simple_body_derivative_steps_before + S (ff_previous_ph_hd_hpl_simple_body_derivative_steps) = S ((S (ff_i_ph_hd_hpl_simple_body_derivative_steps)) * ff_e_hd_hpl_simple)) /\ exists fs_q_ph_hd_hpl_simple_body_derivative_steps_before. ff_d_hd_hpl_simple = fs_q_ph_hd_hpl_simple_body_derivative_steps_before * S ((S (ff_i_ph_hd_hpl_simple_body_derivative_steps)) * ff_e_hd_hpl_simple) + (ff_previous_ph_hd_hpl_simple_body_derivative_steps))) /\ ((((exists fs_h_ph_hd_hpl_simple_body_derivative_steps_after. fs_h_ph_hd_hpl_simple_body_derivative_steps_after + S (ff_current_ph_hd_hpl_simple_body_derivative_steps) = S ((S (S ff_i_ph_hd_hpl_simple_body_derivative_steps)) * ff_e_hd_hpl_simple)) /\ exists fs_q_ph_hd_hpl_simple_body_derivative_steps_after. ff_d_hd_hpl_simple = fs_q_ph_hd_hpl_simple_body_derivative_steps_after * S ((S (S ff_i_ph_hd_hpl_simple_body_derivative_steps)) * ff_e_hd_hpl_simple) + (ff_current_ph_hd_hpl_simple_body_derivative_steps))) /\ ff_current_ph_hd_hpl_simple_body_derivative_steps = ff_previous_ph_hd_hpl_simple_body_derivative_steps * r + ff_coefficient_ph_hd_hpl_simple_body_derivative_steps)))))))) /\ ((exists hgcrt_mod_left_hpl_simple hgcrt_mod_right_hpl_simple. hpl_value_simple + m * hgcrt_mod_left_hpl_simple = 0 + m * hgcrt_mod_right_hpl_simple) /\ (forall hmi_divisor_hpl_simple. (exists hmi_left_factor_hpl_simple. hpl_derivative_simple = hmi_divisor_hpl_simple * hmi_left_factor_hpl_simple) -> (exists hmi_right_factor_hpl_simple. p = hmi_divisor_hpl_simple * hmi_right_factor_hpl_simple) -> hmi_divisor_hpl_simple = 1))))))

Constructive proof overview

Generated structural guide

An unrestricted natural input can be normalized without losing its exact polynomial root or simple derivative.

The unchanged tactic script uses 7 declared prerequisites and contains 85 exact native proof lines.

Alpha v34 checked-use · first admitted v27 · independently kernel and Lean verified; not Stable

Proof neighborhood

Direct dependencies

HL0003 hensel_canonical_residue_exists beta_horner_derivative_value_exists Alpha theorem; checked-use authorized beta_horner_derivative_mod_congruence Alpha theorem; checked-use authorized mod_eq_trans Stable theorem; checked-use authorized mod_eq_symm Stable theorem; checked-use authorized mod_eq_of_mod_eq_multiple Stable theorem; checked-use authorized HL0002 hensel_coprime_mod_transport

Direct dependents

HL000A beta_horner_simple_root_hensel_lift_exists_unique

Formal native tactic body

Dependencies are introduced as named hypotheses before line 1. Local theorem links identify exact declared prerequisites. This exact body belongs to a complete independently kernel-checked constructive proof bundle and has Alpha checked-use authority; it does not imply Stable membership.

Read the argument

Proof checkpoints

85 script commands · 23 reading checkpoints · 3 local claims

This is a reading aid, not a new proof or a proof-tree certificate. Checkpoint groups are consecutive commands, not inferred branch boundaries. Every step links to the preserved script.

Named ingredients (2)
hensel canonical residue existshensel coprime mod transport

Long local formulas use this family’s existing definitions. Each new abbreviation was expanded back to the identical native formula, including its free-variable context. The original edition is preserved below.

01Fix variables and assumptionsL1–10

Work with arbitrary variables or the premises of the current implication.

  1. L1
    intro b
  2. L2
    intro c
  3. L3
    intro a
  4. L4
    intro l
  5. L5
    intro n
  6. L6
    intro d
  7. L7
    intro m
  8. L8
    intro p
  9. L9
    intro s
  10. L10
    intro hp
02Fix variables and assumptionsL11–15

Work with arbitrary variables or the premises of the current implication.

  1. L11
    intro hm
  2. L12
    intro hpair
  3. L13
    intro hfactor
  4. L14
    intro hroot
  5. L15
    intro hcop
03Establish hresidueL16–20

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply hensel canonical residue exists.

  1. L16
    have hresidue : exists r. ((exists hpl_gap_bound. hpl_gap_bound + S (r) = (m)) /\ (exists hgcrt_mod_left_hpl_mod hgcrt_mod_right_hpl_mod. a + m * hgcrt_mod_left_hpl_mod = r + m * hgcrt_mod_right_hpl_mod))
  2. L17
    specialize hensel_canonical_residue_exists m
  3. L18
    specialize hensel_canonical_residue_exists a
  4. L19
    apply hensel_canonical_residue_exists
  5. L20
    exact hm
04Separate the logical casesL21–22

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L21
    cases hresidue
  2. L22
    cases hresidue_witness
05Establish hnewpairL23–28

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply beta horner derivative value exists.

  1. L23
    have hnewpair : ∃ v. ∃ e. HornerDerivative(b,c,x,l,v,e)Definitions: HornerDerivative
  2. L24
    specialize beta_horner_derivative_value_exists b
  3. L25
    specialize beta_horner_derivative_value_exists c
  4. L26
    specialize beta_horner_derivative_value_exists x
  5. L27
    specialize beta_horner_derivative_value_exists l
  6. L28
    apply beta_horner_derivative_value_exists
06Separate the logical casesL29–30

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L29
    cases hnewpair
  2. L30
    cases hnewpair_witness
07Establish hbothL31–40

Establish this local claim before using it. It is not an additional assumption.

  1. L31
    have hboth : (exists hgcrt_mod_left_hpl_mod hgcrt_mod_right_hpl_mod. n + m * hgcrt_mod_left_hpl_mod = x1 + m * hgcrt_mod_right_hpl_mod) /\ (exists hgcrt_mod_left_hpl_mod hgcrt_mod_right_hpl_mod. d + m * hgcrt_mod_left_hpl_mod = x2 + m * hgcrt_mod_right_hpl_mod)
  2. L32
    specialize beta_horner_derivative_mod_congruence b
  3. L33
    specialize beta_horner_derivative_mod_congruence c
  4. L34
    specialize beta_horner_derivative_mod_congruence m
  5. L35
    specialize beta_horner_derivative_mod_congruence a
  6. L36
    specialize beta_horner_derivative_mod_congruence x
  7. L37
    specialize beta_horner_derivative_mod_congruence l
  8. L38
    specialize beta_horner_derivative_mod_congruence n
  9. L39
    specialize beta_horner_derivative_mod_congruence d
  10. L40
    specialize beta_horner_derivative_mod_congruence x1
08Use earlier factsL41–45

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L41
    specialize beta_horner_derivative_mod_congruence x2
  2. L42
    apply beta_horner_derivative_mod_congruence
  3. L43
    exact hresidue_witness_right
  4. L44
    exact hpair
  5. L45
    exact hnewpair_witness_witness
09Separate the logical casesL46–46

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L46
    cases hboth
10Construct an explicit witnessL47–47

Supply the displayed value, then prove that it has the required property.

  1. L47
    exists x
11Separate the logical casesL48–48

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L48
    split
12Use earlier factsL49–49

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L49
    exact hresidue_witness_left
13Separate the logical casesL50–50

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L50
    split
14Use earlier factsL51–55

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L51
    specialize mod_eq_symm m
  2. L52
    specialize mod_eq_symm a
  3. L53
    specialize mod_eq_symm x
  4. L54
    apply mod_eq_symm
  5. L55
    exact hresidue_witness_right
15Construct an explicit witnessL56–57

Supply the displayed value, then prove that it has the required property.

  1. L56
    exists x1
  2. L57
    exists x2
16Separate the logical casesL58–58

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L58
    split
17Use earlier factsL59–59

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L59
    exact hnewpair_witness_witness
18Separate the logical casesL60–60

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L60
    split
19Use earlier factsL61–70

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L61
    specialize mod_eq_trans m
  2. L62
    specialize mod_eq_trans x1
  3. L63
    specialize mod_eq_trans n
  4. L64
    specialize mod_eq_trans 0
  5. L65
    apply mod_eq_trans
  6. L66
    specialize mod_eq_symm m
  7. L67
    specialize mod_eq_symm n
  8. L68
    specialize mod_eq_symm x1
  9. L69
    apply mod_eq_symm
  10. L70
    exact hboth_left
20Use earlier factsL71–80

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L71
    exact hroot
  2. L72
    specialize hensel_coprime_mod_transport p
  3. L73
    specialize hensel_coprime_mod_transport d
  4. L74
    specialize hensel_coprime_mod_transport x2
  5. L75
    apply hensel_coprime_mod_transport
  6. L76
    exact hp
  7. L77
    exact hcop
  8. L78
    specialize mod_eq_of_mod_eq_multiple p
  9. L79
    specialize mod_eq_of_mod_eq_multiple m
  10. L80
    specialize mod_eq_of_mod_eq_multiple d
21Use earlier factsL81–82

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L81
    specialize mod_eq_of_mod_eq_multiple x2
  2. L82
    apply mod_eq_of_mod_eq_multiple
22Construct an explicit witnessL83–83

Supply the displayed value, then prove that it has the required property.

  1. L83
    exists s
23Use earlier factsL84–85

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L84
    exact hfactor
  2. L85
    exact hboth_right

Library-wide reading audit

Original exact command ledger · 85 lines
  1. 0001intro b
  2. 0002intro c
  3. 0003intro a
  4. 0004intro l
  5. 0005intro n
  6. 0006intro d
  7. 0007intro m
  8. 0008intro p
  9. 0009intro s
  10. 0010intro hp
  11. 0011intro hm
  12. 0012intro hpair
  13. 0013intro hfactor
  14. 0014intro hroot
  15. 0015intro hcop
  16. 0016have hresidue : exists r. ((exists hpl_gap_bound. hpl_gap_bound + S (r) = (m)) /\ (exists hgcrt_mod_left_hpl_mod hgcrt_mod_right_hpl_mod. a + m * hgcrt_mod_left_hpl_mod = r + m * hgcrt_mod_right_hpl_mod))
  17. 0017specialize hensel_canonical_residue_exists m
  18. 0018specialize hensel_canonical_residue_exists a
  19. 0019apply hensel_canonical_residue_exists
  20. 0020exact hm
  21. 0021cases hresidue
  22. 0022cases hresidue_witness
  23. 0023have hnewpair : exists v e. (exists ff_u_hd_hpl_pair ff_v_hd_hpl_pair ff_d_hd_hpl_pair ff_e_hd_hpl_pair. ((((((exists fs_h_ph_hd_hpl_pair_body_value_start. fs_h_ph_hd_hpl_pair_body_value_start + S (0) = S ((S (0)) * ff_v_hd_hpl_pair)) /\ exists fs_q_ph_hd_hpl_pair_body_value_start. ff_u_hd_hpl_pair = fs_q_ph_hd_hpl_pair_body_value_start * S ((S (0)) * ff_v_hd_hpl_pair) + (0))) /\ ((((exists fs_h_ph_hd_hpl_pair_body_value_terminal. fs_h_ph_hd_hpl_pair_body_value_terminal + S (v) = S ((S (l)) * ff_v_hd_hpl_pair)) /\ exists fs_q_ph_hd_hpl_pair_body_value_terminal. ff_u_hd_hpl_pair = fs_q_ph_hd_hpl_pair_body_value_terminal * S ((S (l)) * ff_v_hd_hpl_pair) + (v))) /\ forall ff_i_ph_hd_hpl_pair_body_value_steps. (exists ph_bound_hd_hpl_pair_body_value_steps. ph_bound_hd_hpl_pair_body_value_steps + S ff_i_ph_hd_hpl_pair_body_value_steps = l) -> exists ff_coefficient_ph_hd_hpl_pair_body_value_steps ff_previous_ph_hd_hpl_pair_body_value_steps ff_current_ph_hd_hpl_pair_body_value_steps. ((((exists fs_h_ph_hd_hpl_pair_body_value_steps_coefficient. fs_h_ph_hd_hpl_pair_body_value_steps_coefficient + S (ff_coefficient_ph_hd_hpl_pair_body_value_steps) = S ((S (ff_i_ph_hd_hpl_pair_body_value_steps)) * c)) /\ exists fs_q_ph_hd_hpl_pair_body_value_steps_coefficient. b = fs_q_ph_hd_hpl_pair_body_value_steps_coefficient * S ((S (ff_i_ph_hd_hpl_pair_body_value_steps)) * c) + (ff_coefficient_ph_hd_hpl_pair_body_value_steps))) /\ ((((exists fs_h_ph_hd_hpl_pair_body_value_steps_before. fs_h_ph_hd_hpl_pair_body_value_steps_before + S (ff_previous_ph_hd_hpl_pair_body_value_steps) = S ((S (ff_i_ph_hd_hpl_pair_body_value_steps)) * ff_v_hd_hpl_pair)) /\ exists fs_q_ph_hd_hpl_pair_body_value_steps_before. ff_u_hd_hpl_pair = fs_q_ph_hd_hpl_pair_body_value_steps_before * S ((S (ff_i_ph_hd_hpl_pair_body_value_steps)) * ff_v_hd_hpl_pair) + (ff_previous_ph_hd_hpl_pair_body_value_steps))) /\ ((((exists fs_h_ph_hd_hpl_pair_body_value_steps_after. fs_h_ph_hd_hpl_pair_body_value_steps_after + S (ff_current_ph_hd_hpl_pair_body_value_steps) = S ((S (S ff_i_ph_hd_hpl_pair_body_value_steps)) * ff_v_hd_hpl_pair)) /\ exists fs_q_ph_hd_hpl_pair_body_value_steps_after. ff_u_hd_hpl_pair = fs_q_ph_hd_hpl_pair_body_value_steps_after * S ((S (S ff_i_ph_hd_hpl_pair_body_value_steps)) * ff_v_hd_hpl_pair) + (ff_current_ph_hd_hpl_pair_body_value_steps))) /\ ff_current_ph_hd_hpl_pair_body_value_steps = ff_previous_ph_hd_hpl_pair_body_value_steps * x + ff_coefficient_ph_hd_hpl_pair_body_value_steps)))))) /\ (((((exists fs_h_ph_hd_hpl_pair_body_derivative_start. fs_h_ph_hd_hpl_pair_body_derivative_start + S (0) = S ((S (0)) * ff_e_hd_hpl_pair)) /\ exists fs_q_ph_hd_hpl_pair_body_derivative_start. ff_d_hd_hpl_pair = fs_q_ph_hd_hpl_pair_body_derivative_start * S ((S (0)) * ff_e_hd_hpl_pair) + (0))) /\ ((((exists fs_h_ph_hd_hpl_pair_body_derivative_terminal. fs_h_ph_hd_hpl_pair_body_derivative_terminal + S (e) = S ((S (l)) * ff_e_hd_hpl_pair)) /\ exists fs_q_ph_hd_hpl_pair_body_derivative_terminal. ff_d_hd_hpl_pair = fs_q_ph_hd_hpl_pair_body_derivative_terminal * S ((S (l)) * ff_e_hd_hpl_pair) + (e))) /\ forall ff_i_ph_hd_hpl_pair_body_derivative_steps. (exists ph_bound_hd_hpl_pair_body_derivative_steps. ph_bound_hd_hpl_pair_body_derivative_steps + S ff_i_ph_hd_hpl_pair_body_derivative_steps = l) -> exists ff_coefficient_ph_hd_hpl_pair_body_derivative_steps ff_previous_ph_hd_hpl_pair_body_derivative_steps ff_current_ph_hd_hpl_pair_body_derivative_steps. ((((exists fs_h_ph_hd_hpl_pair_body_derivative_steps_coefficient. fs_h_ph_hd_hpl_pair_body_derivative_steps_coefficient + S (ff_coefficient_ph_hd_hpl_pair_body_derivative_steps) = S ((S (ff_i_ph_hd_hpl_pair_body_derivative_steps)) * ff_v_hd_hpl_pair)) /\ exists fs_q_ph_hd_hpl_pair_body_derivative_steps_coefficient. ff_u_hd_hpl_pair = fs_q_ph_hd_hpl_pair_body_derivative_steps_coefficient * S ((S (ff_i_ph_hd_hpl_pair_body_derivative_steps)) * ff_v_hd_hpl_pair) + (ff_coefficient_ph_hd_hpl_pair_body_derivative_steps))) /\ ((((exists fs_h_ph_hd_hpl_pair_body_derivative_steps_before. fs_h_ph_hd_hpl_pair_body_derivative_steps_before + S (ff_previous_ph_hd_hpl_pair_body_derivative_steps) = S ((S (ff_i_ph_hd_hpl_pair_body_derivative_steps)) * ff_e_hd_hpl_pair)) /\ exists fs_q_ph_hd_hpl_pair_body_derivative_steps_before. ff_d_hd_hpl_pair = fs_q_ph_hd_hpl_pair_body_derivative_steps_before * S ((S (ff_i_ph_hd_hpl_pair_body_derivative_steps)) * ff_e_hd_hpl_pair) + (ff_previous_ph_hd_hpl_pair_body_derivative_steps))) /\ ((((exists fs_h_ph_hd_hpl_pair_body_derivative_steps_after. fs_h_ph_hd_hpl_pair_body_derivative_steps_after + S (ff_current_ph_hd_hpl_pair_body_derivative_steps) = S ((S (S ff_i_ph_hd_hpl_pair_body_derivative_steps)) * ff_e_hd_hpl_pair)) /\ exists fs_q_ph_hd_hpl_pair_body_derivative_steps_after. ff_d_hd_hpl_pair = fs_q_ph_hd_hpl_pair_body_derivative_steps_after * S ((S (S ff_i_ph_hd_hpl_pair_body_derivative_steps)) * ff_e_hd_hpl_pair) + (ff_current_ph_hd_hpl_pair_body_derivative_steps))) /\ ff_current_ph_hd_hpl_pair_body_derivative_steps = ff_previous_ph_hd_hpl_pair_body_derivative_steps * x + ff_coefficient_ph_hd_hpl_pair_body_derivative_steps))))))))
  24. 0024specialize beta_horner_derivative_value_exists b
  25. 0025specialize beta_horner_derivative_value_exists c
  26. 0026specialize beta_horner_derivative_value_exists x
  27. 0027specialize beta_horner_derivative_value_exists l
  28. 0028apply beta_horner_derivative_value_exists
  29. 0029cases hnewpair
  30. 0030cases hnewpair_witness
  31. 0031have hboth : (exists hgcrt_mod_left_hpl_mod hgcrt_mod_right_hpl_mod. n + m * hgcrt_mod_left_hpl_mod = x1 + m * hgcrt_mod_right_hpl_mod) /\ (exists hgcrt_mod_left_hpl_mod hgcrt_mod_right_hpl_mod. d + m * hgcrt_mod_left_hpl_mod = x2 + m * hgcrt_mod_right_hpl_mod)
  32. 0032specialize beta_horner_derivative_mod_congruence b
  33. 0033specialize beta_horner_derivative_mod_congruence c
  34. 0034specialize beta_horner_derivative_mod_congruence m
  35. 0035specialize beta_horner_derivative_mod_congruence a
  36. 0036specialize beta_horner_derivative_mod_congruence x
  37. 0037specialize beta_horner_derivative_mod_congruence l
  38. 0038specialize beta_horner_derivative_mod_congruence n
  39. 0039specialize beta_horner_derivative_mod_congruence d
  40. 0040specialize beta_horner_derivative_mod_congruence x1
  41. 0041specialize beta_horner_derivative_mod_congruence x2
  42. 0042apply beta_horner_derivative_mod_congruence
  43. 0043exact hresidue_witness_right
  44. 0044exact hpair
  45. 0045exact hnewpair_witness_witness
  46. 0046cases hboth
  47. 0047exists x
  48. 0048split
  49. 0049exact hresidue_witness_left
  50. 0050split
  51. 0051specialize mod_eq_symm m
  52. 0052specialize mod_eq_symm a
  53. 0053specialize mod_eq_symm x
  54. 0054apply mod_eq_symm
  55. 0055exact hresidue_witness_right
  56. 0056exists x1
  57. 0057exists x2
  58. 0058split
  59. 0059exact hnewpair_witness_witness
  60. 0060split
  61. 0061specialize mod_eq_trans m
  62. 0062specialize mod_eq_trans x1
  63. 0063specialize mod_eq_trans n
  64. 0064specialize mod_eq_trans 0
  65. 0065apply mod_eq_trans
  66. 0066specialize mod_eq_symm m
  67. 0067specialize mod_eq_symm n
  68. 0068specialize mod_eq_symm x1
  69. 0069apply mod_eq_symm
  70. 0070exact hboth_left
  71. 0071exact hroot
  72. 0072specialize hensel_coprime_mod_transport p
  73. 0073specialize hensel_coprime_mod_transport d
  74. 0074specialize hensel_coprime_mod_transport x2
  75. 0075apply hensel_coprime_mod_transport
  76. 0076exact hp
  77. 0077exact hcop
  78. 0078specialize mod_eq_of_mod_eq_multiple p
  79. 0079specialize mod_eq_of_mod_eq_multiple m
  80. 0080specialize mod_eq_of_mod_eq_multiple d
  81. 0081specialize mod_eq_of_mod_eq_multiple x2
  82. 0082apply mod_eq_of_mod_eq_multiple
  83. 0083exists s
  84. 0084exact hfactor
  85. 0085exact hboth_right