Current library: Alpha v34, 4,223 checked-use theorems; Stable remains 432. Historical first admissions, original proof editions, and non-admitted aliases are preserved.
The exact G014 theorem covers m>1 and genuinely invertible a. Phi counts coprime residues independently of the conclusion. The broader coprime theorem handles m=1 by congruence, not by asserting that one is a canonical remainder. Multiplicative-order and RSA statements are not claimed.
Exact theorem in conservative defined notation
∀ l. ∀ a. ∀ m. ∀ b. ∀ c. ∀ d. ∀ e. ∀ t. ∀ P. ∀ Q. ∀ w. UnitCount(m,l,t) → UnitScaledPrefix(a,m,b,c,d,e,l) → Product(b,c,l,P) → Product(d,e,l,Q) → Pow(a,t,w) → ModEq(m,w · P,Q)
Every linked abbreviation expands hygienically to the identical original native formula.
Definition DAG
Actual proof prerequisites
Complete tactic proof in conservative notation
All 208 original proof lines are preserved. Only local proposition formulas are abbreviated; every abbreviation has an exact binder-safe expansion check. The linked exact edition contains the unchanged replay script.
Read the argument
Proof checkpoints
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)
01Induction on lL1–10
02Fix variables and assumptionsL11–16
03Establish ht0L17–21
Establish this local claim before using it. It is not an additional assumption. The following proof commands apply totient unit count zero length.
04Establish hw1L22–28
05Establish hP1L29–34
06Establish hQ1L35–41
Establish this local claim before using it. It is not an additional assumption. The following proof commands apply beta product zero.
07Establish heL42–51
Establish this local claim before using it. It is not an additional assumption. The following proof commands apply one mul.
08Fix variables and assumptionsL52–61
09Fix variables and assumptionsL62–65
10Establish hcL66–71
Establish this local claim before using it. It is not an additional assumption. The following proof commands apply totient unit count succ decompose.
- L66
have hc : ∃ r. ∃ f. UnitCount(m,l,r) ∧ ((Coprime(l,m) ∧ f = 1 ∨ ¬Coprime(l,m) ∧ f = 0) ∧ t = r + f)Definitions: UnitCount(m,l,r)Coprime(l,m)Original native command in the exact edition - L67
specialize totient_unit_count_succ_decompose (m) - L68
specialize totient_unit_count_succ_decompose (l) - L69
specialize totient_unit_count_succ_decompose (t) - L70
apply totient_unit_count_succ_decompose - L71
exact ht
11Separate the logical casesL72–75
12Establish hpL76–82
Establish this local claim before using it. It is not an additional assumption. The following proof commands apply beta product succ decompose.
- L76
have hp : ∃ v. ∃ R. BetaAt(b,c,l,v) ∧ (Product(b,c,l,R) ∧ P = R · v)Definitions: BetaAt(b,c,l,v)Product(b,c,l,R)Original native command in the exact edition - L77
specialize beta_product_succ_decompose (b) - L78
specialize beta_product_succ_decompose (c) - L79
specialize beta_product_succ_decompose (l) - L80
specialize beta_product_succ_decompose (P) - L81
apply beta_product_succ_decompose - L82
exact hP
13Separate the logical casesL83–86
14Establish hqL87–93
Establish this local claim before using it. It is not an additional assumption. The following proof commands apply beta product succ decompose.
- L87
have hq : ∃ v. ∃ R. BetaAt(d,e,l,v) ∧ (Product(d,e,l,R) ∧ Q = R · v)Definitions: BetaAt(d,e,l,v)Product(d,e,l,R)Original native command in the exact edition - L88
specialize beta_product_succ_decompose (d) - L89
specialize beta_product_succ_decompose (e) - L90
specialize beta_product_succ_decompose (l) - L91
specialize beta_product_succ_decompose (Q) - L92
apply beta_product_succ_decompose - L93
exact hQ
15Separate the logical casesL94–97
16Establish hzL98–101
Establish this local claim before using it. It is not an additional assumption. The following proof commands apply pow exists.
17Separate the logical casesL102–102
Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.
- L102
cases hz
18Establish hpreviousL103–112
Establish this local claim before using it. It is not an additional assumption.
- L103
have hprevious : ModEq(m,x6 · x3,x5)Definitions: ModEq(m,x6 · x3,x5)Original native command in the exact edition - L104
specialize IH (a) - L105
specialize IH (m) - L106
specialize IH (b) - L107
specialize IH (c) - L108
specialize IH (d) - L109
specialize IH (e) - L110
specialize IH (x) - L111
specialize IH (x3) - L112
specialize IH (x5)
19Use earlier factsL113–122
Instantiate or apply named facts and discharge the corresponding proof obligations.
- L113
specialize IH (x6) - L114
apply IH - L115
exact hc_witness_witness_left - L116
specialize euler_unit_scaled_prefix_drop_last (a) - L117
specialize euler_unit_scaled_prefix_drop_last (m) - L118
specialize euler_unit_scaled_prefix_drop_last (b) - L119
specialize euler_unit_scaled_prefix_drop_last (c) - L120
specialize euler_unit_scaled_prefix_drop_last (d) - L121
specialize euler_unit_scaled_prefix_drop_last (e) - L122
specialize euler_unit_scaled_prefix_drop_last (l)
20Use earlier factsL123–127
21Establish hstepL128–136
Establish this local claim before using it. It is not an additional assumption. The following proof commands apply hs.
- L128
have hstep : (Coprime(l,m) → ModEq(m,a · x2,x4)) ∧ (¬Coprime(l,m) → ModEq(m,x2,x4))Definitions: Coprime(l,m)ModEq(m,a · x2,x4)ModEq(m,x2,x4)Original native command in the exact edition - L129
specialize hs (l) - L130
specialize hs (x2) - L131
specialize hs (x4) - L132
apply hs - L133
specialize le_refl (S l) - L134
apply le_refl - L135
exact hp_witness_witness_left - L136
exact hq_witness_witness_left
22Separate the logical casesL137–139
23Establish htexpL140–143
24Establish hwpL144–153
Establish this local claim before using it. It is not an additional assumption. The following proof commands apply pow successor pair mul.
- L144
have hwp : w=x6*a - L145
specialize pow_successor_pair_mul (a) - L146
specialize pow_successor_pair_mul (x) - L147
specialize pow_successor_pair_mul (t) - L148
specialize pow_successor_pair_mul (x6) - L149
specialize pow_successor_pair_mul (w) - L150
apply pow_successor_pair_mul - L151
exact htexp - L152
exact hz_witness - L153
exact hw
25Establish hproductL154–163
Establish this local claim before using it. It is not an additional assumption. The following proof commands apply mul shuffle four.
- L154
have hproduct : w*P=(x6*x3)*(a*x2) - L155
rewrite hwp - L156
rewrite hp_witness_witness_right_right - L157
specialize mul_shuffle_four (x6) - L158
specialize mul_shuffle_four (a) - L159
specialize mul_shuffle_four (x3) - L160
specialize mul_shuffle_four (x2) - L161
apply mul_shuffle_four - L162
rewrite hproduct - L163
rewrite hq_witness_witness_right_right
26Use earlier factsL164–172
Instantiate or apply named facts and discharge the corresponding proof obligations.
27Separate the logical casesL173–173
Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.
- L173
cases hc_witness_witness_right_left_right
28Establish htexpL174–181
29Establish hwpL182–189
Establish this local claim before using it. It is not an additional assumption. The following proof commands apply pow functional.
30Establish hproductL190–199
Establish this local claim before using it. It is not an additional assumption. The following proof commands apply mul assoc.
31Use earlier factsL200–208
Instantiate or apply named facts and discharge the corresponding proof obligations.
Original defined command ledger · 208 lines
- 0001
induction l - 0002
intro a - 0003
intro m - 0004
intro b - 0005
intro c - 0006
intro d - 0007
intro e - 0008
intro t - 0009
intro P - 0010
intro Q - 0011
intro w - 0012
intro ht - 0013
intro hs - 0014
intro hP - 0015
intro hQ - 0016
intro hw - 0017
have ht0 : t=0 - 0018
specialize totient_unit_count_zero_length (m) - 0019
specialize totient_unit_count_zero_length (t) - 0020
apply totient_unit_count_zero_length - 0021
exact ht - 0022
have hw1 : w=1 - 0023
specialize pow_zero (a) - 0024
specialize pow_zero (t) - 0025
specialize pow_zero (w) - 0026
apply pow_zero - 0027
exact ht0 - 0028
exact hw - 0029
have hP1 : P=1 - 0030
specialize beta_product_zero (b) - 0031
specialize beta_product_zero (c) - 0032
specialize beta_product_zero (P) - 0033
apply beta_product_zero - 0034
exact hP - 0035
have hQ1 : Q=1 - 0036
specialize beta_product_zero (d) - 0037
specialize beta_product_zero (e) - 0038
specialize beta_product_zero (Q) - 0039
apply beta_product_zero - 0040
exact hQ - 0041
rewrite hw1 - 0042
have he : 1*P=P - 0043
specialize one_mul (P) - 0044
apply one_mul - 0045
rewrite he - 0046
rewrite hP1 - 0047
rewrite hQ1 - 0048
specialize mod_eq_refl (m) - 0049
specialize mod_eq_refl (1) - 0050
apply mod_eq_refl - 0051
intro a - 0052
intro m - 0053
intro b - 0054
intro c - 0055
intro d - 0056
intro e - 0057
intro t - 0058
intro P - 0059
intro Q - 0060
intro w - 0061
intro ht - 0062
intro hs - 0063
intro hP - 0064
intro hQ - 0065
intro hw - 0066
have hc : ∃ r. ∃ f. UnitCount(m,l,r) ∧ ((Coprime(l,m) ∧ f = 1 ∨ ¬Coprime(l,m) ∧ f = 0) ∧ t = r + f) - 0067
specialize totient_unit_count_succ_decompose (m) - 0068
specialize totient_unit_count_succ_decompose (l) - 0069
specialize totient_unit_count_succ_decompose (t) - 0070
apply totient_unit_count_succ_decompose - 0071
exact ht - 0072
cases hc - 0073
cases hc_witness - 0074
cases hc_witness_witness - 0075
cases hc_witness_witness_right - 0076
have hp : ∃ v. ∃ R. BetaAt(b,c,l,v) ∧ (Product(b,c,l,R) ∧ P = R · v) - 0077
specialize beta_product_succ_decompose (b) - 0078
specialize beta_product_succ_decompose (c) - 0079
specialize beta_product_succ_decompose (l) - 0080
specialize beta_product_succ_decompose (P) - 0081
apply beta_product_succ_decompose - 0082
exact hP - 0083
cases hp - 0084
cases hp_witness - 0085
cases hp_witness_witness - 0086
cases hp_witness_witness_right - 0087
have hq : ∃ v. ∃ R. BetaAt(d,e,l,v) ∧ (Product(d,e,l,R) ∧ Q = R · v) - 0088
specialize beta_product_succ_decompose (d) - 0089
specialize beta_product_succ_decompose (e) - 0090
specialize beta_product_succ_decompose (l) - 0091
specialize beta_product_succ_decompose (Q) - 0092
apply beta_product_succ_decompose - 0093
exact hQ - 0094
cases hq - 0095
cases hq_witness - 0096
cases hq_witness_witness - 0097
cases hq_witness_witness_right - 0098
have hz : ∃ z. Pow(a,x,z) - 0099
specialize pow_exists (a) - 0100
specialize pow_exists (x) - 0101
apply pow_exists - 0102
cases hz - 0103
have hprevious : ModEq(m,x6 · x3,x5) - 0104
specialize IH (a) - 0105
specialize IH (m) - 0106
specialize IH (b) - 0107
specialize IH (c) - 0108
specialize IH (d) - 0109
specialize IH (e) - 0110
specialize IH (x) - 0111
specialize IH (x3) - 0112
specialize IH (x5) - 0113
specialize IH (x6) - 0114
apply IH - 0115
exact hc_witness_witness_left - 0116
specialize euler_unit_scaled_prefix_drop_last (a) - 0117
specialize euler_unit_scaled_prefix_drop_last (m) - 0118
specialize euler_unit_scaled_prefix_drop_last (b) - 0119
specialize euler_unit_scaled_prefix_drop_last (c) - 0120
specialize euler_unit_scaled_prefix_drop_last (d) - 0121
specialize euler_unit_scaled_prefix_drop_last (e) - 0122
specialize euler_unit_scaled_prefix_drop_last (l) - 0123
apply euler_unit_scaled_prefix_drop_last - 0124
exact hs - 0125
exact hp_witness_witness_right_left - 0126
exact hq_witness_witness_right_left - 0127
exact hz_witness - 0128
have hstep : (Coprime(l,m) → ModEq(m,a · x2,x4)) ∧ (¬Coprime(l,m) → ModEq(m,x2,x4)) - 0129
specialize hs (l) - 0130
specialize hs (x2) - 0131
specialize hs (x4) - 0132
apply hs - 0133
specialize le_refl (S l) - 0134
apply le_refl - 0135
exact hp_witness_witness_left - 0136
exact hq_witness_witness_left - 0137
cases hstep - 0138
cases hc_witness_witness_right_left - 0139
cases hc_witness_witness_right_left_left - 0140
have htexp : t=S x - 0141
rewrite hc_witness_witness_right_right - 0142
rewrite hc_witness_witness_right_left_left_right - 0143
simp - 0144
have hwp : w=x6*a - 0145
specialize pow_successor_pair_mul (a) - 0146
specialize pow_successor_pair_mul (x) - 0147
specialize pow_successor_pair_mul (t) - 0148
specialize pow_successor_pair_mul (x6) - 0149
specialize pow_successor_pair_mul (w) - 0150
apply pow_successor_pair_mul - 0151
exact htexp - 0152
exact hz_witness - 0153
exact hw - 0154
have hproduct : w*P=(x6*x3)*(a*x2) - 0155
rewrite hwp - 0156
rewrite hp_witness_witness_right_right - 0157
specialize mul_shuffle_four (x6) - 0158
specialize mul_shuffle_four (a) - 0159
specialize mul_shuffle_four (x3) - 0160
specialize mul_shuffle_four (x2) - 0161
apply mul_shuffle_four - 0162
rewrite hproduct - 0163
rewrite hq_witness_witness_right_right - 0164
specialize mod_eq_mul (m) - 0165
specialize mod_eq_mul (x6*x3) - 0166
specialize mod_eq_mul (x5) - 0167
specialize mod_eq_mul (a*x2) - 0168
specialize mod_eq_mul (x4) - 0169
apply mod_eq_mul - 0170
exact hprevious - 0171
apply hstep_left - 0172
exact hc_witness_witness_right_left_left_left - 0173
cases hc_witness_witness_right_left_right - 0174
have htexp : t=x - 0175
rewrite hc_witness_witness_right_right - 0176
rewrite hc_witness_witness_right_left_right_right - 0177
simp - 0178
rewrite htexp at hw - 0179
rewrite htexp at hw - 0180
rewrite htexp at hw - 0181
rewrite htexp at hw - 0182
have hwp : w=x6 - 0183
specialize pow_functional (a) - 0184
specialize pow_functional (x) - 0185
specialize pow_functional (w) - 0186
specialize pow_functional (x6) - 0187
apply pow_functional - 0188
exact hw - 0189
exact hz_witness - 0190
have hproduct : w*P=(x6*x3)*x2 - 0191
rewrite hwp - 0192
rewrite hp_witness_witness_right_right - 0193
symm - 0194
specialize mul_assoc (x6) - 0195
specialize mul_assoc (x3) - 0196
specialize mul_assoc (x2) - 0197
apply mul_assoc - 0198
rewrite hproduct - 0199
rewrite hq_witness_witness_right_right - 0200
specialize mod_eq_mul (m) - 0201
specialize mod_eq_mul (x6*x3) - 0202
specialize mod_eq_mul (x5) - 0203
specialize mod_eq_mul (x2) - 0204
specialize mod_eq_mul (x4) - 0205
apply mod_eq_mul - 0206
exact hprevious - 0207
apply hstep_right - 0208
exact hc_witness_witness_right_left_right_left