BT0117 · Bertrand theorem

factor_pair_has_small_member_below_square

Alpha v34 checked-use theorem · independently kernel and Lean verified; not Stable

A factor pair below (B+1)^2 has a member at most B.

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.

Statement with defined notation

∀ B. ∀ n. ∀ a. ∀ b. n = a · b → Lt(n,S B · S B) → Le(a,B) ∨ Le(b,B)

Every purple notation token opens its conservative definition. Expanding the displayed statement recovers the exact first-order Peano-arithmetic formula checked by the unchanged kernel.

Definitions used by this theorem

In the theorem statement

PD0001 Le PD0002 Lt

3 occurrences

In local proof propositions

PD0001 Le PD0002 Lt

14 occurrences

Exact expanded native-PA statement
forall B n a b. n = a * b -> (exists bpr_gap_bb8fps_bound. bpr_gap_bb8fps_bound + S (n) = S B * S B) -> (exists bpr_le_gap_bb8fps_left. bpr_le_gap_bb8fps_left + (a) = (B)) \/ (exists bpr_le_gap_bb8fps_right. bpr_le_gap_bb8fps_right + (b) = (B))

Proof neighborhood

Direct theorem prerequisites

BT000K le_total BT001G le_or_lt BT001M mul_le_mul_right BT001L mul_le_mul_left BT000F le_trans BT001I lt_not_le

Direct theorem dependents

BT0118 nonprime_has_small_prime_divisor_below_square

Definition-aware tactic body

Only local propositions introduced by have or suffices are compacted. Every changed line has an exact-AST conservative-expansion receipt; the kernel still receives the immutable original tactic script.

Read the argument

Proof checkpoints

91 script commands · 23 reading checkpoints · 11 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.

Definition notation is shown below. Open the paired exact edition for the original native formulas. Source pairing is not a new equivalence certificate.

Named ingredients (6)
le totalle or ltmul le mul rightmul le mul leftle translt not le
01Fix variables and assumptionsL1–6

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

  1. L1
    intro B
  2. L2
    intro n
  3. L3
    intro a
  4. L4
    intro b
  5. L5
    intro hfactor
  6. L6
    intro hbound
02Use earlier factsL7–8

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

  1. L7
    specialize le_total a
  2. L8
    specialize le_total b
03Establish horderL9–10

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

  1. L9
    have horder : Le(a,b) ∨ Le(b,a)Definitions: Le(a,b)Le(b,a)Original native command in the exact edition
  2. L10
    exact le_total
04Separate the logical casesL11–11

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

  1. L11
    cases horder
05Use earlier factsL12–13

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

  1. L12
    specialize le_or_lt a
  2. L13
    specialize le_or_lt B
06Establish hsmallL14–15

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

  1. L14
    have hsmall : Le(a,B) ∨ Lt(B,a)Definitions: Le(a,B)Lt(B,a)Original native command in the exact edition
  2. L15
    exact le_or_lt
07Separate the logical casesL16–17

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

  1. L16
    cases hsmall
  2. L17
    left
08Use earlier factsL18–18

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

  1. L18
    exact hsmall_left
09Separate the logical casesL19–19

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

  1. L19
    exfalso
10Establish hsbL20–26

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

  1. L20
  2. L21
    specialize le_trans (S B)
  3. L22
    specialize le_trans a
  4. L23
    specialize le_trans b
  5. L24
    apply le_trans
  6. L25
    exact hsmall_right
  7. L26
    exact horder_left
11Establish hfirstL27–32

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

  1. L27
    have hfirst : Le(S B · S B,a · S B)Definitions: Le(S B · S B,a · S B)Original native command in the exact edition
  2. L28
    specialize mul_le_mul_right (S B)
  3. L29
    specialize mul_le_mul_right a
  4. L30
    specialize mul_le_mul_right (S B)
  5. L31
    apply mul_le_mul_right
  6. L32
    exact hsmall_right
12Establish hsquareL33–36

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

  1. L33
    have hsquare : Le(S B · S B,a · b)Definitions: Le(S B · S B,a · b)Original native command in the exact edition
  2. L34
    specialize mul_le_mul_left (S B)
  3. L35
    specialize mul_le_mul_left b
  4. L36
    specialize mul_le_mul_left a
13Establish hsecondL37–46

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

  1. L37
    have hsecond : Le(a · S B,a · b)Definitions: Le(a · S B,a · b)Original native command in the exact edition
  2. L38
    apply mul_le_mul_left
  3. L39
    exact hsb
  4. L40
    specialize le_trans (S B * S B)
  5. L41
    specialize le_trans (a * S B)
  6. L42
    specialize le_trans (a * b)
  7. L43
    apply le_trans
  8. L44
    exact hfirst
  9. L45
    exact hsecond
  10. L46
    rewrite <- hfactor at hsquare
14Use earlier factsL47–53

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

  1. L47
    specialize lt_not_le n
  2. L48
    specialize lt_not_le (S B * S B)
  3. L49
    apply lt_not_le
  4. L50
    exact hbound
  5. L51
    exact hsquare
  6. L52
    specialize le_or_lt b
  7. L53
    specialize le_or_lt B
15Establish hsmallL54–55

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

  1. L54
    have hsmall : Le(b,B) ∨ Lt(B,b)Definitions: Le(b,B)Lt(B,b)Original native command in the exact edition
  2. L55
    exact le_or_lt
16Separate the logical casesL56–57

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

  1. L56
    cases hsmall
  2. L57
    right
17Use earlier factsL58–58

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

  1. L58
    exact hsmall_left
18Separate the logical casesL59–59

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

  1. L59
    exfalso
19Establish hsaL60–66

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

  1. L60
  2. L61
    specialize le_trans (S B)
  3. L62
    specialize le_trans b
  4. L63
    specialize le_trans a
  5. L64
    apply le_trans
  6. L65
    exact hsmall_right
  7. L66
    exact horder_right
20Establish hfirstL67–72

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

  1. L67
    have hfirst : Le(S B · S B,a · S B)Definitions: Le(S B · S B,a · S B)Original native command in the exact edition
  2. L68
    specialize mul_le_mul_right (S B)
  3. L69
    specialize mul_le_mul_right a
  4. L70
    specialize mul_le_mul_right (S B)
  5. L71
    apply mul_le_mul_right
  6. L72
    exact hsa
21Establish hsecondL73–78

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

  1. L73
    have hsecond : Le(a · S B,a · b)Definitions: Le(a · S B,a · b)Original native command in the exact edition
  2. L74
    specialize mul_le_mul_left (S B)
  3. L75
    specialize mul_le_mul_left b
  4. L76
    specialize mul_le_mul_left a
  5. L77
    apply mul_le_mul_left
  6. L78
    exact hsmall_right
22Establish hsquareL79–88

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

  1. L79
    have hsquare : Le(S B · S B,a · b)Definitions: Le(S B · S B,a · b)Original native command in the exact edition
  2. L80
    specialize le_trans (S B * S B)
  3. L81
    specialize le_trans (a * S B)
  4. L82
    specialize le_trans (a * b)
  5. L83
    apply le_trans
  6. L84
    exact hfirst
  7. L85
    exact hsecond
  8. L86
    rewrite <- hfactor at hsquare
  9. L87
    specialize lt_not_le n
  10. L88
    specialize lt_not_le (S B * S B)
23Use earlier factsL89–91

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

  1. L89
    apply lt_not_le
  2. L90
    exact hbound
  3. L91
    exact hsquare

Library-wide reading audit

Original defined command ledger · 91 lines
  1. 0001intro B
  2. 0002intro n
  3. 0003intro a
  4. 0004intro b
  5. 0005intro hfactor
  6. 0006intro hbound
  7. 0007specialize le_total a
  8. 0008specialize le_total b
  9. 0009have horder : Le(a,b) ∨ Le(b,a)
    Exact native replay linehave horder : (exists k. k + a = b) \/ (exists k. k + b = a)
  10. 0010exact le_total
  11. 0011cases horder
  12. 0012specialize le_or_lt a
  13. 0013specialize le_or_lt B
  14. 0014have hsmall : Le(a,B) ∨ Lt(B,a)
    Exact native replay linehave hsmall : (exists k. k + a = B) \/ (exists k. k + S B = a)
  15. 0015exact le_or_lt
  16. 0016cases hsmall
  17. 0017left
  18. 0018exact hsmall_left
  19. 0019exfalso
  20. 0020have hsb : Lt(B,b)
    Exact native replay linehave hsb : exists k. k + S B = b
  21. 0021specialize le_trans (S B)
  22. 0022specialize le_trans a
  23. 0023specialize le_trans b
  24. 0024apply le_trans
  25. 0025exact hsmall_right
  26. 0026exact horder_left
  27. 0027have hfirst : Le(S B · S B,a · S B)
    Exact native replay linehave hfirst : exists k. k + S B * S B = a * S B
  28. 0028specialize mul_le_mul_right (S B)
  29. 0029specialize mul_le_mul_right a
  30. 0030specialize mul_le_mul_right (S B)
  31. 0031apply mul_le_mul_right
  32. 0032exact hsmall_right
  33. 0033have hsquare : Le(S B · S B,a · b)
    Exact native replay linehave hsquare : exists k. k + S B * S B = a * b
  34. 0034specialize mul_le_mul_left (S B)
  35. 0035specialize mul_le_mul_left b
  36. 0036specialize mul_le_mul_left a
  37. 0037have hsecond : Le(a · S B,a · b)
    Exact native replay linehave hsecond : exists k. k + a * S B = a * b
  38. 0038apply mul_le_mul_left
  39. 0039exact hsb
  40. 0040specialize le_trans (S B * S B)
  41. 0041specialize le_trans (a * S B)
  42. 0042specialize le_trans (a * b)
  43. 0043apply le_trans
  44. 0044exact hfirst
  45. 0045exact hsecond
  46. 0046rewrite <- hfactor at hsquare
  47. 0047specialize lt_not_le n
  48. 0048specialize lt_not_le (S B * S B)
  49. 0049apply lt_not_le
  50. 0050exact hbound
  51. 0051exact hsquare
  52. 0052specialize le_or_lt b
  53. 0053specialize le_or_lt B
  54. 0054have hsmall : Le(b,B) ∨ Lt(B,b)
    Exact native replay linehave hsmall : (exists k. k + b = B) \/ (exists k. k + S B = b)
  55. 0055exact le_or_lt
  56. 0056cases hsmall
  57. 0057right
  58. 0058exact hsmall_left
  59. 0059exfalso
  60. 0060have hsa : Lt(B,a)
    Exact native replay linehave hsa : exists k. k + S B = a
  61. 0061specialize le_trans (S B)
  62. 0062specialize le_trans b
  63. 0063specialize le_trans a
  64. 0064apply le_trans
  65. 0065exact hsmall_right
  66. 0066exact horder_right
  67. 0067have hfirst : Le(S B · S B,a · S B)
    Exact native replay linehave hfirst : exists k. k + S B * S B = a * S B
  68. 0068specialize mul_le_mul_right (S B)
  69. 0069specialize mul_le_mul_right a
  70. 0070specialize mul_le_mul_right (S B)
  71. 0071apply mul_le_mul_right
  72. 0072exact hsa
  73. 0073have hsecond : Le(a · S B,a · b)
    Exact native replay linehave hsecond : exists k. k + a * S B = a * b
  74. 0074specialize mul_le_mul_left (S B)
  75. 0075specialize mul_le_mul_left b
  76. 0076specialize mul_le_mul_left a
  77. 0077apply mul_le_mul_left
  78. 0078exact hsmall_right
  79. 0079have hsquare : Le(S B · S B,a · b)
    Exact native replay linehave hsquare : exists k. k + S B * S B = a * b
  80. 0080specialize le_trans (S B * S B)
  81. 0081specialize le_trans (a * S B)
  82. 0082specialize le_trans (a * b)
  83. 0083apply le_trans
  84. 0084exact hfirst
  85. 0085exact hsecond
  86. 0086rewrite <- hfactor at hsquare
  87. 0087specialize lt_not_le n
  88. 0088specialize lt_not_le (S B * S B)
  89. 0089apply lt_not_le
  90. 0090exact hbound
  91. 0091exact hsquare