Metamath Proof Explorer


Theorem aks6d1c7

Description: N is a prime power if the hypotheses of the AKS algorithm hold. Claim 7 of Theorem 6.1 https://www3.nd.edu/%7eandyp/notes/AKS.pdf . (Contributed by metakunt, 16-May-2025)

Ref Expression
Hypotheses aks6d1c7.1 ˙ = e f | e f Base Poly 1 K y mulGrp K PrimRoots R e mulGrp K eval 1 K f y = eval 1 K f e mulGrp K y
aks6d1c7.2 P = chr K
aks6d1c7.3 φ K Field
aks6d1c7.4 φ P
aks6d1c7.5 φ R
aks6d1c7.6 φ N 3
aks6d1c7.7 φ P N
aks6d1c7.8 φ N gcd R = 1
aks6d1c7.9 A = ϕ R log 2 N
aks6d1c7.10 φ log 2 N 2 < od R N
aks6d1c7.11 φ x Base K P mulGrp K x K RingIso K
aks6d1c7.12 φ M mulGrp K PrimRoots R
aks6d1c7.13 φ b 1 A b gcd N = 1
aks6d1c7.14 φ a 1 A N ˙ var 1 K + Poly 1 K algSc Poly 1 K ℤRHom K a
Assertion aks6d1c7 φ N = P P pCnt N

Proof

Step Hyp Ref Expression
1 aks6d1c7.1 ˙ = e f | e f Base Poly 1 K y mulGrp K PrimRoots R e mulGrp K eval 1 K f y = eval 1 K f e mulGrp K y
2 aks6d1c7.2 P = chr K
3 aks6d1c7.3 φ K Field
4 aks6d1c7.4 φ P
5 aks6d1c7.5 φ R
6 aks6d1c7.6 φ N 3
7 aks6d1c7.7 φ P N
8 aks6d1c7.8 φ N gcd R = 1
9 aks6d1c7.9 A = ϕ R log 2 N
10 aks6d1c7.10 φ log 2 N 2 < od R N
11 aks6d1c7.11 φ x Base K P mulGrp K x K RingIso K
12 aks6d1c7.12 φ M mulGrp K PrimRoots R
13 aks6d1c7.13 φ b 1 A b gcd N = 1
14 aks6d1c7.14 φ a 1 A N ˙ var 1 K + Poly 1 K algSc Poly 1 K ℤRHom K a
15 simpr φ r p p N p = r q q = r q = r
16 7 ad2antrr φ r p p N p = r P N
17 breq1 s = P s N P N
18 eqeq1 s = P s = r P = r
19 17 18 bibi12d s = P s N s = r P N P = r
20 nfv s p N p = r
21 nfv p s N s = r
22 breq1 p = s p N s N
23 equequ1 p = s p = r s = r
24 22 23 bibi12d p = s p N p = r s N s = r
25 20 21 24 cbvralw p p N p = r s s N s = r
26 25 bilani φ r p p N p = r s s N s = r
27 4 ad2antrr φ r p p N p = r P
28 19 26 27 rspcdva φ r p p N p = r P N P = r
29 28 biimpd φ r p p N p = r P N P = r
30 16 29 mpd φ r p p N p = r P = r
31 30 ad2antrr φ r p p N p = r q q = r P = r
32 31 eqcomd φ r p p N p = r q q = r r = P
33 15 32 eqtrd φ r p p N p = r q q = r q = P
34 33 oveq1d φ r p p N p = r q q = r q pCnt N = P pCnt N
35 eluzelz N 3 N
36 6 35 syl φ N
37 0red φ 0
38 3re 3
39 38 a1i φ 3
40 36 zred φ N
41 3pos 0 < 3
42 41 a1i φ 0 < 3
43 eluzle N 3 3 N
44 6 43 syl φ 3 N
45 37 39 40 42 44 ltletrd φ 0 < N
46 36 45 jca φ N 0 < N
47 elnnz N N 0 < N
48 46 47 sylibr φ N
49 pcelnn P N P pCnt N P N
50 4 48 49 syl2anc φ P pCnt N P N
51 7 50 mpbird φ P pCnt N
52 51 nncnd φ P pCnt N
53 52 mulridd φ P pCnt N 1 = P pCnt N
54 53 eqcomd φ P pCnt N = P pCnt N 1
55 1nn0 1 0
56 55 a1i φ 1 0
57 pcidlem P 1 0 P pCnt P 1 = 1
58 4 56 57 syl2anc φ P pCnt P 1 = 1
59 58 eqcomd φ 1 = P pCnt P 1
60 prmnn P P
61 4 60 syl φ P
62 61 nncnd φ P
63 62 exp1d φ P 1 = P
64 63 oveq2d φ P pCnt P 1 = P pCnt P
65 59 64 eqtrd φ 1 = P pCnt P
66 65 oveq2d φ P pCnt N 1 = P pCnt N P pCnt P
67 54 66 eqtrd φ P pCnt N = P pCnt N P pCnt P
68 67 adantr φ r P pCnt N = P pCnt N P pCnt P
69 68 ad3antrrr φ r p p N p = r q q = r P pCnt N = P pCnt N P pCnt P
70 27 ad2antrr φ r p p N p = r q q = r P
71 nnq P P
72 61 71 syl φ P
73 61 nnne0d φ P 0
74 72 73 jca φ P P 0
75 74 adantr φ r P P 0
76 75 ad3antrrr φ r p p N p = r q q = r P P 0
77 51 nnzd φ P pCnt N
78 77 adantr φ r P pCnt N
79 78 adantr φ r p p N p = r P pCnt N
80 79 adantr φ r p p N p = r q P pCnt N
81 80 adantr φ r p p N p = r q q = r P pCnt N
82 pcexp P P P 0 P pCnt N P pCnt P P pCnt N = P pCnt N P pCnt P
83 70 76 81 82 syl3anc φ r p p N p = r q q = r P pCnt P P pCnt N = P pCnt N P pCnt P
84 83 eqcomd φ r p p N p = r q q = r P pCnt N P pCnt P = P pCnt P P pCnt N
85 69 84 eqtrd φ r p p N p = r q q = r P pCnt N = P pCnt P P pCnt N
86 33 eqcomd φ r p p N p = r q q = r P = q
87 86 oveq1d φ r p p N p = r q q = r P pCnt P P pCnt N = q pCnt P P pCnt N
88 85 87 eqtrd φ r p p N p = r q q = r P pCnt N = q pCnt P P pCnt N
89 34 88 eqtrd φ r p p N p = r q q = r q pCnt N = q pCnt P P pCnt N
90 breq1 s = q s N q N
91 equequ1 s = q s = r q = r
92 90 91 bibi12d s = q s N s = r q N q = r
93 26 adantr φ r p p N p = r q s s N s = r
94 simpr φ r p p N p = r q q
95 92 93 94 rspcdva φ r p p N p = r q q N q = r
96 95 bicomd φ r p p N p = r q q = r q N
97 96 notbid φ r p p N p = r q ¬ q = r ¬ q N
98 97 biimpa φ r p p N p = r q ¬ q = r ¬ q N
99 94 adantr φ r p p N p = r q ¬ q = r q
100 48 adantr φ r N
101 100 ad3antrrr φ r p p N p = r q ¬ q = r N
102 pceq0 q N q pCnt N = 0 ¬ q N
103 99 101 102 syl2anc φ r p p N p = r q ¬ q = r q pCnt N = 0 ¬ q N
104 98 103 mpbird φ r p p N p = r q ¬ q = r q pCnt N = 0
105 neqne ¬ q = r q r
106 105 adantl φ r p p N p = r q ¬ q = r q r
107 16 adantr φ r p p N p = r q P N
108 27 adantr φ r p p N p = r q P
109 19 93 108 rspcdva φ r p p N p = r q P N P = r
110 109 biimpd φ r p p N p = r q P N P = r
111 107 110 mpd φ r p p N p = r q P = r
112 111 adantr φ r p p N p = r q ¬ q = r P = r
113 112 eqcomd φ r p p N p = r q ¬ q = r r = P
114 106 113 neeqtrd φ r p p N p = r q ¬ q = r q P
115 114 neneqd φ r p p N p = r q ¬ q = r ¬ q = P
116 prmuz2 q q 2
117 116 adantl φ r p p N p = r q q 2
118 117 adantr φ r p p N p = r q ¬ q = r q 2
119 27 ad2antrr φ r p p N p = r q ¬ q = r P
120 dvdsprm q 2 P q P q = P
121 118 119 120 syl2anc φ r p p N p = r q ¬ q = r q P q = P
122 115 121 mtbird φ r p p N p = r q ¬ q = r ¬ q P
123 61 ad4antr φ r p p N p = r q ¬ q = r P
124 123 nnzd φ r p p N p = r q ¬ q = r P
125 51 adantr φ r P pCnt N
126 125 adantr φ r p p N p = r P pCnt N
127 126 adantr φ r p p N p = r q P pCnt N
128 127 adantr φ r p p N p = r q ¬ q = r P pCnt N
129 prmdvdsexp q P P pCnt N q P P pCnt N q P
130 99 124 128 129 syl3anc φ r p p N p = r q ¬ q = r q P P pCnt N q P
131 122 130 mtbird φ r p p N p = r q ¬ q = r ¬ q P P pCnt N
132 119 101 pccld φ r p p N p = r q ¬ q = r P pCnt N 0
133 123 132 nnexpcld φ r p p N p = r q ¬ q = r P P pCnt N
134 pceq0 q P P pCnt N q pCnt P P pCnt N = 0 ¬ q P P pCnt N
135 99 133 134 syl2anc φ r p p N p = r q ¬ q = r q pCnt P P pCnt N = 0 ¬ q P P pCnt N
136 131 135 mpbird φ r p p N p = r q ¬ q = r q pCnt P P pCnt N = 0
137 136 eqcomd φ r p p N p = r q ¬ q = r 0 = q pCnt P P pCnt N
138 104 137 eqtrd φ r p p N p = r q ¬ q = r q pCnt N = q pCnt P P pCnt N
139 89 138 pm2.61dan φ r p p N p = r q q pCnt N = q pCnt P P pCnt N
140 139 ralrimiva φ r p p N p = r q q pCnt N = q pCnt P P pCnt N
141 1 2 3 4 5 6 7 8 9 10 11 12 13 14 aks6d1c7lem4 φ ∃! p p N
142 reu6 ∃! p p N r p p N p = r
143 141 142 sylib φ r p p N p = r
144 140 143 r19.29a φ q q pCnt N = q pCnt P P pCnt N
145 48 nnnn0d φ N 0
146 61 nnnn0d φ P 0
147 4 48 pccld φ P pCnt N 0
148 146 147 nn0expcld φ P P pCnt N 0
149 pc11 N 0 P P pCnt N 0 N = P P pCnt N q q pCnt N = q pCnt P P pCnt N
150 145 148 149 syl2anc φ N = P P pCnt N q q pCnt N = q pCnt P P pCnt N
151 144 150 mpbird φ N = P P pCnt N