PA005K

mod_eq_decidable_nonzero

Stable checked-use theorem · independently closed

Balanced congruence is constructively decidable at nonzero 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 original first-admission records.

Exact expanded PA statement

forall p a b. ~(p = 0) -> (exists qr_u_dec_yes qr_v_dec_yes. a + p * qr_u_dec_yes = b + p * qr_v_dec_yes) \/ ~(exists qr_u_dec_no qr_v_dec_no. a + p * qr_u_dec_no = b + p * qr_v_dec_no)

Structural proof guide

Generated structural guide

Balanced congruence is constructively decidable at nonzero modulus.

Use the direct prerequisites division_remainder_exists, mul_comm, mod_eq_decidable_from_remainders as previously established PA formulas.

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

Referenced ingredients

PA001D division_remainder_exists PA000H mul_comm PA005J mod_eq_decidable_from_remainders

Proof neighborhood

Direct dependencies

PA001D division_remainder_exists PA000H mul_comm PA005J mod_eq_decidable_from_remainders

Direct dependents

PA005L quadratic_residue_search_up_to

Formal native tactic body

Dependencies are introduced as named hypotheses before line 1. Linked names are exact direct references. This Stable checked-use theorem is independently kernel-checked when replayed.

Read the argument

Proof checkpoints

44 script commands · 8 reading checkpoints · 4 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 (3)
division remainder existsmul commmod eq decidable from remainders
01Fix variables and assumptionsL1–4

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

  1. L1
    intro p
  2. L2
    intro a
  3. L3
    intro b
  4. L4
    intro hp
02Establish hdaL5–9

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

  1. L5
    have hda : exists qa ra. a = p * qa + ra /\ exists ha. ha + S ra = p
  2. L6
    specialize division_remainder_exists p
  3. L7
    specialize division_remainder_exists a
  4. L8
    apply division_remainder_exists
  5. L9
    exact hp
03Separate the logical casesL10–12

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

  1. L10
    cases hda
  2. L11
    cases hda_witness
  3. L12
    cases hda_witness_witness
04Establish hdbL13–17

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

  1. L13
    have hdb : exists qb rb. b = p * qb + rb /\ exists hb. hb + S rb = p
  2. L14
    specialize division_remainder_exists p
  3. L15
    specialize division_remainder_exists b
  4. L16
    apply division_remainder_exists
  5. L17
    exact hp
05Separate the logical casesL18–20

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

  1. L18
    cases hdb
  2. L19
    cases hdb_witness
  3. L20
    cases hdb_witness_witness
06Establish ha_commL21–26

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

  1. L21
    have ha_comm : a = x * p + x1
  2. L22
    trans p * x + x1
  3. L23
    exact hda_witness_witness_left
  4. L24
    congr
  5. L25
    apply mul_comm
  6. L26
    refl
07Establish hb_commL27–36

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

  1. L27
    have hb_comm : b = x2 * p + x3
  2. L28
    trans p * x2 + x3
  3. L29
    exact hdb_witness_witness_left
  4. L30
    congr
  5. L31
    apply mul_comm
  6. L32
    refl
  7. L33
    specialize mod_eq_decidable_from_remainders p
  8. L34
    specialize mod_eq_decidable_from_remainders a
  9. L35
    specialize mod_eq_decidable_from_remainders b
  10. L36
    specialize mod_eq_decidable_from_remainders x
08Use earlier factsL37–44

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

  1. L37
    specialize mod_eq_decidable_from_remainders x1
  2. L38
    specialize mod_eq_decidable_from_remainders x2
  3. L39
    specialize mod_eq_decidable_from_remainders x3
  4. L40
    apply mod_eq_decidable_from_remainders
  5. L41
    exact ha_comm
  6. L42
    exact hda_witness_witness_right
  7. L43
    exact hb_comm
  8. L44
    exact hdb_witness_witness_right

Library-wide reading audit

Original exact command ledger · 44 lines
  1. 0001intro p
  2. 0002intro a
  3. 0003intro b
  4. 0004intro hp
  5. 0005have hda : exists qa ra. a = p * qa + ra /\ exists ha. ha + S ra = p
  6. 0006specialize division_remainder_exists p
  7. 0007specialize division_remainder_exists a
  8. 0008apply division_remainder_exists
  9. 0009exact hp
  10. 0010cases hda
  11. 0011cases hda_witness
  12. 0012cases hda_witness_witness
  13. 0013have hdb : exists qb rb. b = p * qb + rb /\ exists hb. hb + S rb = p
  14. 0014specialize division_remainder_exists p
  15. 0015specialize division_remainder_exists b
  16. 0016apply division_remainder_exists
  17. 0017exact hp
  18. 0018cases hdb
  19. 0019cases hdb_witness
  20. 0020cases hdb_witness_witness
  21. 0021have ha_comm : a = x * p + x1
  22. 0022trans p * x + x1
  23. 0023exact hda_witness_witness_left
  24. 0024congr
  25. 0025apply mul_comm
  26. 0026refl
  27. 0027have hb_comm : b = x2 * p + x3
  28. 0028trans p * x2 + x3
  29. 0029exact hdb_witness_witness_left
  30. 0030congr
  31. 0031apply mul_comm
  32. 0032refl
  33. 0033specialize mod_eq_decidable_from_remainders p
  34. 0034specialize mod_eq_decidable_from_remainders a
  35. 0035specialize mod_eq_decidable_from_remainders b
  36. 0036specialize mod_eq_decidable_from_remainders x
  37. 0037specialize mod_eq_decidable_from_remainders x1
  38. 0038specialize mod_eq_decidable_from_remainders x2
  39. 0039specialize mod_eq_decidable_from_remainders x3
  40. 0040apply mod_eq_decidable_from_remainders
  41. 0041exact ha_comm
  42. 0042exact hda_witness_witness_right
  43. 0043exact hb_comm
  44. 0044exact hdb_witness_witness_right