PX0043

polynomial_diagonal_term_right_add_congruent

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

At one actual antidiagonal position, right multiplication carries the genuine padded coefficient sum to the sum of the two genuine multiplication terms modulo the same modulus.

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 expanded first-order arithmetic statement

forall p ab ac bb bc cb cc L db dc M i j u v w. (forall pfp_index_term_add_right_source. (exists pfa_gap_term_add_right_sourceindex. pfa_gap_term_add_right_sourceindex + S (pfp_index_term_add_right_source) = (L)) -> exists pfp_left_term_add_right_source pfp_right_term_add_right_source pfp_value_term_add_right_source. ((((exists ff_h_pfp_term_add_right_sourceleft. ff_h_pfp_term_add_right_sourceleft + S (pfp_left_term_add_right_source) = S ((S (pfp_index_term_add_right_source)) * ac)) /\ exists ff_q_pfp_term_add_right_sourceleft. ab = ff_q_pfp_term_add_right_sourceleft * S ((S (pfp_index_term_add_right_source)) * ac) + (pfp_left_term_add_right_source))) /\ (((((exists ff_h_pfp_term_add_right_sourceright. ff_h_pfp_term_add_right_sourceright + S (pfp_right_term_add_right_source) = S ((S (pfp_index_term_add_right_source)) * bc)) /\ exists ff_q_pfp_term_add_right_sourceright. bb = ff_q_pfp_term_add_right_sourceright * S ((S (pfp_index_term_add_right_source)) * bc) + (pfp_right_term_add_right_source))) /\ (((((exists ff_h_pfp_term_add_right_sourcetarget. ff_h_pfp_term_add_right_sourcetarget + S (pfp_value_term_add_right_source) = S ((S (pfp_index_term_add_right_source)) * cc)) /\ exists ff_q_pfp_term_add_right_sourcetarget. cb = ff_q_pfp_term_add_right_sourcetarget * S ((S (pfp_index_term_add_right_source)) * cc) + (pfp_value_term_add_right_source))) /\ ((((exists pfa_gap_term_add_right_sourceoperationleft. pfa_gap_term_add_right_sourceoperationleft + S (pfp_left_term_add_right_source) = (p)) /\ (((exists pfa_gap_term_add_right_sourceoperationright. pfa_gap_term_add_right_sourceoperationright + S (pfp_right_term_add_right_source) = (p)) /\ ((((exists pfa_gap_term_add_right_sourceoperationresultbound. pfa_gap_term_add_right_sourceoperationresultbound + S (pfp_value_term_add_right_source) = (p)) /\ ((exists pfa_offset_left_term_add_right_sourceoperationresultcongruence pfa_offset_right_term_add_right_sourceoperationresultcongruence. ((pfp_left_term_add_right_source) + (pfp_right_term_add_right_source)) + (p) * pfa_offset_left_term_add_right_sourceoperationresultcongruence = (pfp_value_term_add_right_source) + (p) * pfa_offset_right_term_add_right_sourceoperationresultcongruence)))))))))))))))) -> (exists pfc_complement_term_add_right_u pfc_left_term_add_right_u pfc_right_term_add_right_u. (((j)+pfc_complement_term_add_right_u=(i)) /\ ((((((exists pfa_gap_term_add_right_uleftinside. pfa_gap_term_add_right_uleftinside + S (j) = (L)) /\ ((((exists ff_h_pfp_term_add_right_uleftentry. ff_h_pfp_term_add_right_uleftentry + S (pfc_left_term_add_right_u) = S ((S (j)) * ac)) /\ exists ff_q_pfp_term_add_right_uleftentry. ab = ff_q_pfp_term_add_right_uleftentry * S ((S (j)) * ac) + (pfc_left_term_add_right_u)))))) \/ (((exists pfc_gap_term_add_right_uleftoutside. pfc_gap_term_add_right_uleftoutside+(L)=(j)) /\ (((pfc_left_term_add_right_u)=0))))) /\ ((((((exists pfa_gap_term_add_right_urightinside. pfa_gap_term_add_right_urightinside + S (pfc_complement_term_add_right_u) = (M)) /\ ((((exists ff_h_pfp_term_add_right_urightentry. ff_h_pfp_term_add_right_urightentry + S (pfc_right_term_add_right_u) = S ((S (pfc_complement_term_add_right_u)) * dc)) /\ exists ff_q_pfp_term_add_right_urightentry. db = ff_q_pfp_term_add_right_urightentry * S ((S (pfc_complement_term_add_right_u)) * dc) + (pfc_right_term_add_right_u)))))) \/ (((exists pfc_gap_term_add_right_urightoutside. pfc_gap_term_add_right_urightoutside+(M)=(pfc_complement_term_add_right_u)) /\ (((pfc_right_term_add_right_u)=0))))) /\ (((u)=pfc_left_term_add_right_u*pfc_right_term_add_right_u)))))))) -> (exists pfc_complement_term_add_right_v pfc_left_term_add_right_v pfc_right_term_add_right_v. (((j)+pfc_complement_term_add_right_v=(i)) /\ ((((((exists pfa_gap_term_add_right_vleftinside. pfa_gap_term_add_right_vleftinside + S (j) = (L)) /\ ((((exists ff_h_pfp_term_add_right_vleftentry. ff_h_pfp_term_add_right_vleftentry + S (pfc_left_term_add_right_v) = S ((S (j)) * bc)) /\ exists ff_q_pfp_term_add_right_vleftentry. bb = ff_q_pfp_term_add_right_vleftentry * S ((S (j)) * bc) + (pfc_left_term_add_right_v)))))) \/ (((exists pfc_gap_term_add_right_vleftoutside. pfc_gap_term_add_right_vleftoutside+(L)=(j)) /\ (((pfc_left_term_add_right_v)=0))))) /\ ((((((exists pfa_gap_term_add_right_vrightinside. pfa_gap_term_add_right_vrightinside + S (pfc_complement_term_add_right_v) = (M)) /\ ((((exists ff_h_pfp_term_add_right_vrightentry. ff_h_pfp_term_add_right_vrightentry + S (pfc_right_term_add_right_v) = S ((S (pfc_complement_term_add_right_v)) * dc)) /\ exists ff_q_pfp_term_add_right_vrightentry. db = ff_q_pfp_term_add_right_vrightentry * S ((S (pfc_complement_term_add_right_v)) * dc) + (pfc_right_term_add_right_v)))))) \/ (((exists pfc_gap_term_add_right_vrightoutside. pfc_gap_term_add_right_vrightoutside+(M)=(pfc_complement_term_add_right_v)) /\ (((pfc_right_term_add_right_v)=0))))) /\ (((v)=pfc_left_term_add_right_v*pfc_right_term_add_right_v)))))))) -> (exists pfc_complement_term_add_right_w pfc_left_term_add_right_w pfc_right_term_add_right_w. (((j)+pfc_complement_term_add_right_w=(i)) /\ ((((((exists pfa_gap_term_add_right_wleftinside. pfa_gap_term_add_right_wleftinside + S (j) = (L)) /\ ((((exists ff_h_pfp_term_add_right_wleftentry. ff_h_pfp_term_add_right_wleftentry + S (pfc_left_term_add_right_w) = S ((S (j)) * cc)) /\ exists ff_q_pfp_term_add_right_wleftentry. cb = ff_q_pfp_term_add_right_wleftentry * S ((S (j)) * cc) + (pfc_left_term_add_right_w)))))) \/ (((exists pfc_gap_term_add_right_wleftoutside. pfc_gap_term_add_right_wleftoutside+(L)=(j)) /\ (((pfc_left_term_add_right_w)=0))))) /\ ((((((exists pfa_gap_term_add_right_wrightinside. pfa_gap_term_add_right_wrightinside + S (pfc_complement_term_add_right_w) = (M)) /\ ((((exists ff_h_pfp_term_add_right_wrightentry. ff_h_pfp_term_add_right_wrightentry + S (pfc_right_term_add_right_w) = S ((S (pfc_complement_term_add_right_w)) * dc)) /\ exists ff_q_pfp_term_add_right_wrightentry. db = ff_q_pfp_term_add_right_wrightentry * S ((S (pfc_complement_term_add_right_w)) * dc) + (pfc_right_term_add_right_w)))))) \/ (((exists pfc_gap_term_add_right_wrightoutside. pfc_gap_term_add_right_wrightoutside+(M)=(pfc_complement_term_add_right_w)) /\ (((pfc_right_term_add_right_w)=0))))) /\ (((w)=pfc_left_term_add_right_w*pfc_right_term_add_right_w)))))))) -> (exists pfa_offset_left_term_add_right_result pfa_offset_right_term_add_right_result. (u+v) + (p) * pfa_offset_left_term_add_right_result = (w) + (p) * pfa_offset_right_term_add_right_result)

Constructive proof overview

Generated structural guide

At one actual antidiagonal position, right multiplication carries the genuine padded coefficient sum to the sum of the two genuine multiplication terms modulo the same modulus.

The unchanged tactic script uses 5 declared prerequisites and contains 120 exact native proof lines.

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

Proof neighborhood

Direct dependencies

add_left_cancel Alpha theorem; checked-use authorized polynomial_zero_extended_entry_functional Alpha theorem; checked-use authorized PX0041 polynomial_zero_extended_add_congruent add_mul Alpha theorem; checked-use authorized mod_eq_mul_right Alpha theorem; checked-use authorized

Direct dependents

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

120 script commands · 15 reading checkpoints · 6 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 (1)
01Fix variables and assumptionsL1–10

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

  1. L1
    intro p
  2. L2
    intro ab
  3. L3
    intro ac
  4. L4
    intro bb
  5. L5
    intro bc
  6. L6
    intro cb
  7. L7
    intro cc
  8. L8
    intro L
  9. L9
    intro db
  10. L10
    intro dc
02Fix variables and assumptionsL11–20

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

  1. L11
    intro M
  2. L12
    intro i
  3. L13
    intro j
  4. L14
    intro u
  5. L15
    intro v
  6. L16
    intro w
  7. L17
    intro hs
  8. L18
    intro hu
  9. L19
    intro hv
  10. L20
    intro hw
03Separate the logical casesL21–30

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

  1. L21
    cases hu
  2. L22
    cases hu_witness
  3. L23
    cases hu_witness_witness
  4. L24
    cases hu_witness_witness_witness
  5. L25
    cases hu_witness_witness_witness_right
  6. L26
    cases hu_witness_witness_witness_right_right
  7. L27
    cases hv
  8. L28
    cases hv_witness
  9. L29
    cases hv_witness_witness
  10. L30
    cases hv_witness_witness_witness
04Separate the logical casesL31–38

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

  1. L31
    cases hv_witness_witness_witness_right
  2. L32
    cases hv_witness_witness_witness_right_right
  3. L33
    cases hw
  4. L34
    cases hw_witness
  5. L35
    cases hw_witness_witness
  6. L36
    cases hw_witness_witness_witness
  7. L37
    cases hw_witness_witness_witness_right
  8. L38
    cases hw_witness_witness_witness_right_right
05Establish hkuL39–48

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply add left cancel.

  1. L39
    have hku : x=x6
  2. L40
    specialize add_left_cancel (j)
  3. L41
    specialize add_left_cancel (x)
  4. L42
    specialize add_left_cancel (x6)
  5. L43
    apply add_left_cancel
  6. L44
    trans i
  7. L45
    exact hu_witness_witness_witness_left
  8. L46
    symm
  9. L47
    exact hw_witness_witness_witness_left
  10. L48
    rewrite hku at hu_witness_witness_witness_right_right_left
06Calculate and transport equalitiesL49–51

Carry out the recorded arithmetic or equality steps; inspect the exact commands for their direction and premises.

  1. L49
    rewrite hku at hu_witness_witness_witness_right_right_left
  2. L50
    rewrite hku at hu_witness_witness_witness_right_right_left
  3. L51
    rewrite hku at hu_witness_witness_witness_right_right_left
07Establish hkvL52–61

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply add left cancel.

  1. L52
    have hkv : x3=x6
  2. L53
    specialize add_left_cancel (j)
  3. L54
    specialize add_left_cancel (x3)
  4. L55
    specialize add_left_cancel (x6)
  5. L56
    apply add_left_cancel
  6. L57
    trans i
  7. L58
    exact hv_witness_witness_witness_left
  8. L59
    symm
  9. L60
    exact hw_witness_witness_witness_left
  10. L61
    rewrite hkv at hv_witness_witness_witness_right_right_left
08Calculate and transport equalitiesL62–64

Carry out the recorded arithmetic or equality steps; inspect the exact commands for their direction and premises.

  1. L62
    rewrite hkv at hv_witness_witness_witness_right_right_left
  2. L63
    rewrite hkv at hv_witness_witness_witness_right_right_left
  3. L64
    rewrite hkv at hv_witness_witness_witness_right_right_left
09Establish hfuL65–74

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply polynomial zero extended entry functional.

  1. L65
    have hfu : x2=x8
  2. L66
    specialize polynomial_zero_extended_entry_functional (db)
  3. L67
    specialize polynomial_zero_extended_entry_functional (dc)
  4. L68
    specialize polynomial_zero_extended_entry_functional (M)
  5. L69
    specialize polynomial_zero_extended_entry_functional (x6)
  6. L70
    specialize polynomial_zero_extended_entry_functional (x2)
  7. L71
    specialize polynomial_zero_extended_entry_functional (x8)
  8. L72
    apply polynomial_zero_extended_entry_functional
  9. L73
    exact hu_witness_witness_witness_right_right_left
  10. L74
    exact hw_witness_witness_witness_right_right_left
10Establish hfvL75–84

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply polynomial zero extended entry functional.

  1. L75
    have hfv : x5=x8
  2. L76
    specialize polynomial_zero_extended_entry_functional (db)
  3. L77
    specialize polynomial_zero_extended_entry_functional (dc)
  4. L78
    specialize polynomial_zero_extended_entry_functional (M)
  5. L79
    specialize polynomial_zero_extended_entry_functional (x6)
  6. L80
    specialize polynomial_zero_extended_entry_functional (x5)
  7. L81
    specialize polynomial_zero_extended_entry_functional (x8)
  8. L82
    apply polynomial_zero_extended_entry_functional
  9. L83
    exact hv_witness_witness_witness_right_right_left
  10. L84
    exact hw_witness_witness_witness_right_right_left
11Establish hsumL85–94

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

  1. L85
    have hsum : exists pfa_offset_left_term_add_right_sum pfa_offset_right_term_add_right_sum. (x1+x4) + (p) * pfa_offset_left_term_add_right_sum = (x7) + (p) * pfa_offset_right_term_add_right_sum
  2. L86
    specialize polynomial_zero_extended_add_congruent (p)
  3. L87
    specialize polynomial_zero_extended_add_congruent (ab)
  4. L88
    specialize polynomial_zero_extended_add_congruent (ac)
  5. L89
    specialize polynomial_zero_extended_add_congruent (bb)
  6. L90
    specialize polynomial_zero_extended_add_congruent (bc)
  7. L91
    specialize polynomial_zero_extended_add_congruent (cb)
  8. L92
    specialize polynomial_zero_extended_add_congruent (cc)
  9. L93
    specialize polynomial_zero_extended_add_congruent (L)
  10. L94
    specialize polynomial_zero_extended_add_congruent (j)
12Use earlier factsL95–102

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

  1. L95
    specialize polynomial_zero_extended_add_congruent (x1)
  2. L96
    specialize polynomial_zero_extended_add_congruent (x4)
  3. L97
    specialize polynomial_zero_extended_add_congruent (x7)
  4. L98
    apply polynomial_zero_extended_add_congruent
  5. L99
    exact hs
  6. L100
    exact hu_witness_witness_witness_right_left
  7. L101
    exact hv_witness_witness_witness_right_left
  8. L102
    exact hw_witness_witness_witness_right_left
13Calculate and transport equalitiesL103–107

Carry out the recorded arithmetic or equality steps; inspect the exact commands for their direction and premises.

  1. L103
    rewrite hu_witness_witness_witness_right_right_right
  2. L104
    rewrite hv_witness_witness_witness_right_right_right
  3. L105
    rewrite hw_witness_witness_witness_right_right_right
  4. L106
    rewrite hfu
  5. L107
    rewrite hfv
14Establish hfactorL108–117

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply add mul.

  1. L108
    have hfactor : x1*x8+x4*x8=(x1+x4)*x8
  2. L109
    symm
  3. L110
    specialize add_mul (x1)
  4. L111
    specialize add_mul (x4)
  5. L112
    specialize add_mul (x8)
  6. L113
    apply add_mul
  7. L114
    rewrite hfactor
  8. L115
    specialize mod_eq_mul_right (p)
  9. L116
    specialize mod_eq_mul_right (x1+x4)
  10. L117
    specialize mod_eq_mul_right (x7)
15Use earlier factsL118–120

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

  1. L118
    specialize mod_eq_mul_right (x8)
  2. L119
    apply mod_eq_mul_right
  3. L120
    exact hsum

Library-wide reading audit

Original exact command ledger · 120 lines
  1. 0001intro p
  2. 0002intro ab
  3. 0003intro ac
  4. 0004intro bb
  5. 0005intro bc
  6. 0006intro cb
  7. 0007intro cc
  8. 0008intro L
  9. 0009intro db
  10. 0010intro dc
  11. 0011intro M
  12. 0012intro i
  13. 0013intro j
  14. 0014intro u
  15. 0015intro v
  16. 0016intro w
  17. 0017intro hs
  18. 0018intro hu
  19. 0019intro hv
  20. 0020intro hw
  21. 0021cases hu
  22. 0022cases hu_witness
  23. 0023cases hu_witness_witness
  24. 0024cases hu_witness_witness_witness
  25. 0025cases hu_witness_witness_witness_right
  26. 0026cases hu_witness_witness_witness_right_right
  27. 0027cases hv
  28. 0028cases hv_witness
  29. 0029cases hv_witness_witness
  30. 0030cases hv_witness_witness_witness
  31. 0031cases hv_witness_witness_witness_right
  32. 0032cases hv_witness_witness_witness_right_right
  33. 0033cases hw
  34. 0034cases hw_witness
  35. 0035cases hw_witness_witness
  36. 0036cases hw_witness_witness_witness
  37. 0037cases hw_witness_witness_witness_right
  38. 0038cases hw_witness_witness_witness_right_right
  39. 0039have hku : x=x6
  40. 0040specialize add_left_cancel (j)
  41. 0041specialize add_left_cancel (x)
  42. 0042specialize add_left_cancel (x6)
  43. 0043apply add_left_cancel
  44. 0044trans i
  45. 0045exact hu_witness_witness_witness_left
  46. 0046symm
  47. 0047exact hw_witness_witness_witness_left
  48. 0048rewrite hku at hu_witness_witness_witness_right_right_left
  49. 0049rewrite hku at hu_witness_witness_witness_right_right_left
  50. 0050rewrite hku at hu_witness_witness_witness_right_right_left
  51. 0051rewrite hku at hu_witness_witness_witness_right_right_left
  52. 0052have hkv : x3=x6
  53. 0053specialize add_left_cancel (j)
  54. 0054specialize add_left_cancel (x3)
  55. 0055specialize add_left_cancel (x6)
  56. 0056apply add_left_cancel
  57. 0057trans i
  58. 0058exact hv_witness_witness_witness_left
  59. 0059symm
  60. 0060exact hw_witness_witness_witness_left
  61. 0061rewrite hkv at hv_witness_witness_witness_right_right_left
  62. 0062rewrite hkv at hv_witness_witness_witness_right_right_left
  63. 0063rewrite hkv at hv_witness_witness_witness_right_right_left
  64. 0064rewrite hkv at hv_witness_witness_witness_right_right_left
  65. 0065have hfu : x2=x8
  66. 0066specialize polynomial_zero_extended_entry_functional (db)
  67. 0067specialize polynomial_zero_extended_entry_functional (dc)
  68. 0068specialize polynomial_zero_extended_entry_functional (M)
  69. 0069specialize polynomial_zero_extended_entry_functional (x6)
  70. 0070specialize polynomial_zero_extended_entry_functional (x2)
  71. 0071specialize polynomial_zero_extended_entry_functional (x8)
  72. 0072apply polynomial_zero_extended_entry_functional
  73. 0073exact hu_witness_witness_witness_right_right_left
  74. 0074exact hw_witness_witness_witness_right_right_left
  75. 0075have hfv : x5=x8
  76. 0076specialize polynomial_zero_extended_entry_functional (db)
  77. 0077specialize polynomial_zero_extended_entry_functional (dc)
  78. 0078specialize polynomial_zero_extended_entry_functional (M)
  79. 0079specialize polynomial_zero_extended_entry_functional (x6)
  80. 0080specialize polynomial_zero_extended_entry_functional (x5)
  81. 0081specialize polynomial_zero_extended_entry_functional (x8)
  82. 0082apply polynomial_zero_extended_entry_functional
  83. 0083exact hv_witness_witness_witness_right_right_left
  84. 0084exact hw_witness_witness_witness_right_right_left
  85. 0085have hsum : exists pfa_offset_left_term_add_right_sum pfa_offset_right_term_add_right_sum. (x1+x4) + (p) * pfa_offset_left_term_add_right_sum = (x7) + (p) * pfa_offset_right_term_add_right_sum
  86. 0086specialize polynomial_zero_extended_add_congruent (p)
  87. 0087specialize polynomial_zero_extended_add_congruent (ab)
  88. 0088specialize polynomial_zero_extended_add_congruent (ac)
  89. 0089specialize polynomial_zero_extended_add_congruent (bb)
  90. 0090specialize polynomial_zero_extended_add_congruent (bc)
  91. 0091specialize polynomial_zero_extended_add_congruent (cb)
  92. 0092specialize polynomial_zero_extended_add_congruent (cc)
  93. 0093specialize polynomial_zero_extended_add_congruent (L)
  94. 0094specialize polynomial_zero_extended_add_congruent (j)
  95. 0095specialize polynomial_zero_extended_add_congruent (x1)
  96. 0096specialize polynomial_zero_extended_add_congruent (x4)
  97. 0097specialize polynomial_zero_extended_add_congruent (x7)
  98. 0098apply polynomial_zero_extended_add_congruent
  99. 0099exact hs
  100. 0100exact hu_witness_witness_witness_right_left
  101. 0101exact hv_witness_witness_witness_right_left
  102. 0102exact hw_witness_witness_witness_right_left
  103. 0103rewrite hu_witness_witness_witness_right_right_right
  104. 0104rewrite hv_witness_witness_witness_right_right_right
  105. 0105rewrite hw_witness_witness_witness_right_right_right
  106. 0106rewrite hfu
  107. 0107rewrite hfv
  108. 0108have hfactor : x1*x8+x4*x8=(x1+x4)*x8
  109. 0109symm
  110. 0110specialize add_mul (x1)
  111. 0111specialize add_mul (x4)
  112. 0112specialize add_mul (x8)
  113. 0113apply add_mul
  114. 0114rewrite hfactor
  115. 0115specialize mod_eq_mul_right (p)
  116. 0116specialize mod_eq_mul_right (x1+x4)
  117. 0117specialize mod_eq_mul_right (x7)
  118. 0118specialize mod_eq_mul_right (x8)
  119. 0119apply mod_eq_mul_right
  120. 0120exact hsum