Exact expanded PA statement
forall p q h k i tb tc qb qc ub uc rb rc n d. p = 2 * h + 1 -> q = 2 * k + 1 -> ((~(p = 1) /\ forall frp_prime_left_row_quotient_prime_p frp_prime_right_row_quotient_prime_p. p = frp_prime_left_row_quotient_prime_p * frp_prime_right_row_quotient_prime_p -> frp_prime_left_row_quotient_prime_p = 1 \/ frp_prime_right_row_quotient_prime_p = 1)) -> ((~(q = 1) /\ forall frp_prime_left_row_quotient_prime_q frp_prime_right_row_quotient_prime_q. q = frp_prime_left_row_quotient_prime_q * frp_prime_right_row_quotient_prime_q -> frp_prime_left_row_quotient_prime_q = 1 \/ frp_prime_right_row_quotient_prime_q = 1)) -> ~(p = q) -> (exists edt_lt_gap_row_quotient_row_bound. edt_lt_gap_row_quotient_row_bound + S (i) = h) -> (forall esd_index_row_quotient_scaled esd_value_row_quotient_scaled. (exists esd_gap_row_quotient_scaled. esd_gap_row_quotient_scaled + S esd_index_row_quotient_scaled = h) -> (((exists ff_h_esd_row_quotient_scaled_decoded. ff_h_esd_row_quotient_scaled_decoded + S (esd_value_row_quotient_scaled) = S ((S (esd_index_row_quotient_scaled)) * tc)) /\ exists ff_q_esd_row_quotient_scaled_decoded. tb = ff_q_esd_row_quotient_scaled_decoded * S ((S (esd_index_row_quotient_scaled)) * tc) + (esd_value_row_quotient_scaled))) -> esd_value_row_quotient_scaled = q * (1 + esd_index_row_quotient_scaled)) -> (forall fdp_index_row_quotient_division. (exists gsp_lt_gap_row_quotient_division_index_bound. gsp_lt_gap_row_quotient_division_index_bound + S fdp_index_row_quotient_division = h) -> exists fdp_value_row_quotient_division fdp_quotient_row_quotient_division fdp_remainder_row_quotient_division. (((exists ff_h_fdp_row_quotient_division_source. ff_h_fdp_row_quotient_division_source + S (fdp_value_row_quotient_division) = S ((S (fdp_index_row_quotient_division)) * tc)) /\ exists ff_q_fdp_row_quotient_division_source. tb = ff_q_fdp_row_quotient_division_source * S ((S (fdp_index_row_quotient_division)) * tc) + (fdp_value_row_quotient_division))) /\ ((((exists ff_h_fdp_row_quotient_division_quotient_entry. ff_h_fdp_row_quotient_division_quotient_entry + S (fdp_quotient_row_quotient_division) = S ((S (fdp_index_row_quotient_division)) * qc)) /\ exists ff_q_fdp_row_quotient_division_quotient_entry. qb = ff_q_fdp_row_quotient_division_quotient_entry * S ((S (fdp_index_row_quotient_division)) * qc) + (fdp_quotient_row_quotient_division))) /\ ((((exists ff_h_fdp_row_quotient_division_remainder_entry. ff_h_fdp_row_quotient_division_remainder_entry + S (fdp_remainder_row_quotient_division) = S ((S (fdp_index_row_quotient_division)) * uc)) /\ exists ff_q_fdp_row_quotient_division_remainder_entry. ub = ff_q_fdp_row_quotient_division_remainder_entry * S ((S (fdp_index_row_quotient_division)) * uc) + (fdp_remainder_row_quotient_division))) /\ (fdp_value_row_quotient_division = p * fdp_quotient_row_quotient_division + fdp_remainder_row_quotient_division /\ (exists gsp_lt_gap_row_quotient_division_remainder_bound. gsp_lt_gap_row_quotient_division_remainder_bound + S fdp_remainder_row_quotient_division = p))))) -> (forall eri_column_row_quotient_source. (exists eri_gap_row_quotient_source_bound. eri_gap_row_quotient_source_bound + S (eri_column_row_quotient_source) = k) -> exists eri_bit_row_quotient_source. ((((exists ff_h_eri_row_quotient_source_decoded. ff_h_eri_row_quotient_source_decoded + S (eri_bit_row_quotient_source) = S ((S (eri_column_row_quotient_source)) * rc)) /\ exists ff_q_eri_row_quotient_source_decoded. rb = ff_q_eri_row_quotient_source_decoded * S ((S (eri_column_row_quotient_source)) * rc) + (eri_bit_row_quotient_source))) /\ (((eri_bit_row_quotient_source = 0 /\ ((exists eri_gap_row_quotient_source_choice_left. eri_gap_row_quotient_source_choice_left + S (q * S i) = p * S eri_column_row_quotient_source) /\ ~(exists eri_gap_row_quotient_source_choice_right. eri_gap_row_quotient_source_choice_right + S (p * S eri_column_row_quotient_source) = q * S i))) \/ (eri_bit_row_quotient_source = 1 /\ ((exists eri_gap_row_quotient_source_choice_right. eri_gap_row_quotient_source_choice_right + S (p * S eri_column_row_quotient_source) = q * S i) /\ ~(exists eri_gap_row_quotient_source_choice_left. eri_gap_row_quotient_source_choice_left + S (q * S i) = p * S eri_column_row_quotient_source))))))) -> (((exists ff_u_row_quotient_count_n_sum ff_v_row_quotient_count_n_sum. ((((exists ff_h_row_quotient_count_n_sum_start. ff_h_row_quotient_count_n_sum_start + S (0) = S ((S (0)) * ff_v_row_quotient_count_n_sum)) /\ exists ff_q_row_quotient_count_n_sum_start. ff_u_row_quotient_count_n_sum = ff_q_row_quotient_count_n_sum_start * S ((S (0)) * ff_v_row_quotient_count_n_sum) + (0))) /\ ((((exists ff_h_row_quotient_count_n_sum_terminal. ff_h_row_quotient_count_n_sum_terminal + S (n) = S ((S (k)) * ff_v_row_quotient_count_n_sum)) /\ exists ff_q_row_quotient_count_n_sum_terminal. ff_u_row_quotient_count_n_sum = ff_q_row_quotient_count_n_sum_terminal * S ((S (k)) * ff_v_row_quotient_count_n_sum) + (n))) /\ forall ff_i_row_quotient_count_n_sum. (exists ff_lt_row_quotient_count_n_sum_bound. ff_lt_row_quotient_count_n_sum_bound + S ff_i_row_quotient_count_n_sum = k) -> exists ff_a_row_quotient_count_n_sum ff_r_row_quotient_count_n_sum ff_s_row_quotient_count_n_sum. ((((exists ff_h_row_quotient_count_n_sum_summand. ff_h_row_quotient_count_n_sum_summand + S (ff_a_row_quotient_count_n_sum) = S ((S (ff_i_row_quotient_count_n_sum)) * rc)) /\ exists ff_q_row_quotient_count_n_sum_summand. rb = ff_q_row_quotient_count_n_sum_summand * S ((S (ff_i_row_quotient_count_n_sum)) * rc) + (ff_a_row_quotient_count_n_sum))) /\ ((((exists ff_h_row_quotient_count_n_sum_partial. ff_h_row_quotient_count_n_sum_partial + S (ff_r_row_quotient_count_n_sum) = S ((S (ff_i_row_quotient_count_n_sum)) * ff_v_row_quotient_count_n_sum)) /\ exists ff_q_row_quotient_count_n_sum_partial. ff_u_row_quotient_count_n_sum = ff_q_row_quotient_count_n_sum_partial * S ((S (ff_i_row_quotient_count_n_sum)) * ff_v_row_quotient_count_n_sum) + (ff_r_row_quotient_count_n_sum))) /\ ((((exists ff_h_row_quotient_count_n_sum_successor. ff_h_row_quotient_count_n_sum_successor + S (ff_s_row_quotient_count_n_sum) = S ((S (S ff_i_row_quotient_count_n_sum)) * ff_v_row_quotient_count_n_sum)) /\ exists ff_q_row_quotient_count_n_sum_successor. ff_u_row_quotient_count_n_sum = ff_q_row_quotient_count_n_sum_successor * S ((S (S ff_i_row_quotient_count_n_sum)) * ff_v_row_quotient_count_n_sum) + (ff_s_row_quotient_count_n_sum))) /\ ff_s_row_quotient_count_n_sum = ff_r_row_quotient_count_n_sum + ff_a_row_quotient_count_n_sum)))))) /\ (forall ff_i_row_quotient_count_n_bits. (exists ff_lt_row_quotient_count_n_bits_bound. ff_lt_row_quotient_count_n_bits_bound + S ff_i_row_quotient_count_n_bits = k) -> exists ff_bit_row_quotient_count_n_bits. ((((exists ff_h_row_quotient_count_n_bits_decoded. ff_h_row_quotient_count_n_bits_decoded + S (ff_bit_row_quotient_count_n_bits) = S ((S (ff_i_row_quotient_count_n_bits)) * rc)) /\ exists ff_q_row_quotient_count_n_bits_decoded. rb = ff_q_row_quotient_count_n_bits_decoded * S ((S (ff_i_row_quotient_count_n_bits)) * rc) + (ff_bit_row_quotient_count_n_bits))) /\ (ff_bit_row_quotient_count_n_bits = 0 \/ ff_bit_row_quotient_count_n_bits = 1))))) -> (((exists ff_h_row_quotient_decoded_quotient. ff_h_row_quotient_decoded_quotient + S (d) = S ((S (i)) * qc)) /\ exists ff_q_row_quotient_decoded_quotient. qb = ff_q_row_quotient_decoded_quotient * S ((S (i)) * qc) + (d))) -> n = dStructural proof guide
Generated structural guide
The semantic row count equals the quotient decoded by the scaled division prefix at that row.
Use the direct prerequisites add_succ_left, zero_add, beta_at_unique, distinct_odd_prime_row_bit_count_equals_division_quotient as previously established PA formulas.
The proof proceeds by case analysis (7), intermediate claims (7).
Referenced ingredients
Proof neighborhood
Direct dependencies
PA000E add_succ_left PA0001 zero_add PA002F beta_at_unique PA00E0 distinct_odd_prime_row_bit_count_equals_division_quotientDirect 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.
- 0001
intro p - 0002
intro q - 0003
intro h - 0004
intro k - 0005
intro i - 0006
intro tb - 0007
intro tc - 0008
intro qb - 0009
intro qc - 0010
intro ub - 0011
intro uc - 0012
intro rb - 0013
intro rc - 0014
intro n - 0015
intro d - 0016
intro hpodd - 0017
intro hqodd - 0018
intro hp - 0019
intro hq - 0020
intro hpq - 0021
intro hi - 0022
intro hscaled - 0023
intro hdivisions - 0024
intro hrow - 0025
intro hcount - 0026
intro hdentry - 0027
have hdivision_entry : exists x quotient remainder. (((exists ff_h_row_quotient_source_entry. ff_h_row_quotient_source_entry + S (x) = S ((S (i)) * tc)) /\ exists ff_q_row_quotient_source_entry. tb = ff_q_row_quotient_source_entry * S ((S (i)) * tc) + (x))) /\ ((((exists ff_h_row_quotient_quotient_entry. ff_h_row_quotient_quotient_entry + S (quotient) = S ((S (i)) * qc)) /\ exists ff_q_row_quotient_quotient_entry. qb = ff_q_row_quotient_quotient_entry * S ((S (i)) * qc) + (quotient))) /\ ((((exists ff_h_row_quotient_remainder_entry. ff_h_row_quotient_remainder_entry + S (remainder) = S ((S (i)) * uc)) /\ exists ff_q_row_quotient_remainder_entry. ub = ff_q_row_quotient_remainder_entry * S ((S (i)) * uc) + (remainder))) /\ (x = p * quotient + remainder /\ (exists edt_lt_gap_row_quotient_entry_remainder_bound. edt_lt_gap_row_quotient_entry_remainder_bound + S (remainder) = p)))) - 0028
specialize hdivisions i - 0029
apply hdivisions - 0030
exact hi - 0031
cases hdivision_entry - 0032
cases hdivision_entry_witness - 0033
cases hdivision_entry_witness_witness - 0034
cases hdivision_entry_witness_witness_witness - 0035
cases hdivision_entry_witness_witness_witness_right - 0036
cases hdivision_entry_witness_witness_witness_right_right - 0037
cases hdivision_entry_witness_witness_witness_right_right_right - 0038
have hxscaled : x = q * (1 + i) - 0039
specialize hscaled i - 0040
specialize hscaled x - 0041
apply hscaled - 0042
exact hi - 0043
exact hdivision_entry_witness_witness_witness_left - 0044
have hone : 1 + i = S i - 0045
trans S (0 + i) - 0046
specialize add_succ_left 0 - 0047
specialize add_succ_left i - 0048
exact add_succ_left - 0049
congr - 0050
specialize zero_add i - 0051
exact zero_add - 0052
have hxscaled_succ : x = q * S i - 0053
trans q * (1 + i) - 0054
exact hxscaled - 0055
congr - 0056
refl - 0057
exact hone - 0058
have hquotient_eq : x1 = d - 0059
specialize beta_at_unique qb - 0060
specialize beta_at_unique qc - 0061
specialize beta_at_unique i - 0062
specialize beta_at_unique x1 - 0063
specialize beta_at_unique d - 0064
apply beta_at_unique - 0065
exact hdivision_entry_witness_witness_witness_right_left - 0066
exact hdentry - 0067
have hdivision : q * S i = p * x1 + x2 - 0068
trans x - 0069
symm - 0070
exact hxscaled_succ - 0071
exact hdivision_entry_witness_witness_witness_right_right_right_left - 0072
have hnq : n = x1 - 0073
specialize distinct_odd_prime_row_bit_count_equals_division_quotient p - 0074
specialize distinct_odd_prime_row_bit_count_equals_division_quotient q - 0075
specialize distinct_odd_prime_row_bit_count_equals_division_quotient h - 0076
specialize distinct_odd_prime_row_bit_count_equals_division_quotient k - 0077
specialize distinct_odd_prime_row_bit_count_equals_division_quotient i - 0078
specialize distinct_odd_prime_row_bit_count_equals_division_quotient x1 - 0079
specialize distinct_odd_prime_row_bit_count_equals_division_quotient x2 - 0080
specialize distinct_odd_prime_row_bit_count_equals_division_quotient rb - 0081
specialize distinct_odd_prime_row_bit_count_equals_division_quotient rc - 0082
specialize distinct_odd_prime_row_bit_count_equals_division_quotient n - 0083
apply distinct_odd_prime_row_bit_count_equals_division_quotient - 0084
exact hpodd - 0085
exact hqodd - 0086
exact hp - 0087
exact hq - 0088
exact hpq - 0089
exact hi - 0090
exact hrow - 0091
exact hcount - 0092
exact hdivision - 0093
exact hdivision_entry_witness_witness_witness_right_right_right_right - 0094
trans x1 - 0095
exact hnq - 0096
exact hquotient_eq