aks6d1c7lem4 - Mathbox for metakunt

	Mathbox for metakunt		< Previous Next > Nearby theorems
Mirrors > Home > MPE Home > Th. List > Mathboxes > aks6d1c7lem4		Structured version Visualization version GIF version

Theorem aks6d1c7lem4 42142

Description: In the AKS algorithm there exists a unique prime number 𝑝 that divides 𝑁. (Contributed by metakunt, 16-May-2025.)

**Hypotheses**
Ref	Expression
aks6d1c7.1	⊢ ∼ = {⟨𝑒, 𝑓⟩ ∣ (𝑒 ∈ ℕ ∧ 𝑓 ∈ (Base‘(Poly₁‘𝐾)) ∧ ∀𝑦 ∈ ((mulGrp‘𝐾) PrimRoots 𝑅)(𝑒(._g‘(mulGrp‘𝐾))(((eval₁‘𝐾)‘𝑓)‘𝑦)) = (((eval₁‘𝐾)‘𝑓)‘(𝑒(._g‘(mulGrp‘𝐾))𝑦)))}
aks6d1c7.2	⊢ 𝑃 = (chr‘𝐾)
aks6d1c7.3	⊢ (𝜑 → 𝐾 ∈ Field)
aks6d1c7.4	⊢ (𝜑 → 𝑃 ∈ ℙ)
aks6d1c7.5	⊢ (𝜑 → 𝑅 ∈ ℕ)
aks6d1c7.6	⊢ (𝜑 → 𝑁 ∈ (ℤ_≥‘3))
aks6d1c7.7	⊢ (𝜑 → 𝑃 ∥ 𝑁)
aks6d1c7.8	⊢ (𝜑 → (𝑁 gcd 𝑅) = 1)
aks6d1c7.9	⊢ 𝐴 = (⌊‘((√‘(ϕ‘𝑅)) · (2 log_b 𝑁)))
aks6d1c7.10	⊢ (𝜑 → ((2 log_b 𝑁)↑2) < ((od_ℤ‘𝑅)‘𝑁))
aks6d1c7.11	⊢ (𝜑 → (𝑥 ∈ (Base‘𝐾) ↦ (𝑃(._g‘(mulGrp‘𝐾))𝑥)) ∈ (𝐾 RingIso 𝐾))
aks6d1c7.12	⊢ (𝜑 → 𝑀 ∈ ((mulGrp‘𝐾) PrimRoots 𝑅))
aks6d1c7.13	⊢ (𝜑 → ∀𝑏 ∈ (1...𝐴)(𝑏 gcd 𝑁) = 1)
aks6d1c7.14	⊢ (𝜑 → ∀𝑎 ∈ (1...𝐴)𝑁 ∼ ((var₁‘𝐾)(+_g‘(Poly₁‘𝐾))((algSc‘(Poly₁‘𝐾))‘((ℤRHom‘𝐾)‘𝑎))))

**Assertion**
Ref	Expression
aks6d1c7lem4	⊢ (𝜑 → ∃!𝑝 ∈ ℙ 𝑝 ∥ 𝑁)

Distinct variable groups: ∼ ,𝑎 𝐴,𝑎 𝐴,𝑏 𝐴,𝑒,𝑓,𝑦 𝑥,𝐴,𝑦 𝐾,𝑎 𝐾,𝑏 𝑒,𝐾,𝑓,𝑦 𝑥,𝐾 𝑀,𝑎 𝑀,𝑏 𝑥,𝑀,𝑦 𝑁,𝑎,𝑝 𝑁,𝑏,𝑝 𝑒,𝑁,𝑓,𝑦 𝑥,𝑁,𝑝,𝑦 𝑃,𝑎,𝑝 𝑃,𝑏 𝑃,𝑒,𝑓,𝑦 𝑥,𝑃 𝑅,𝑎 𝑅,𝑒,𝑓,𝑦 𝑥,𝑅 𝜑,𝑎,𝑝 𝜑,𝑏 𝜑,𝑥,𝑦 Allowed substitution hints: 𝜑(𝑒,𝑓) 𝐴(𝑝) ∼ (𝑥,𝑦,𝑒,𝑓,𝑝,𝑏) 𝑅(𝑝,𝑏) 𝐾(𝑝) 𝑀(𝑒,𝑓,𝑝)

**Proof of Theorem aks6d1c7lem4**
Step	Hyp	Ref	Expression
1		aks6d1c7.4	. . 3 ⊢ (𝜑 → 𝑃 ∈ ℙ)
2		aks6d1c7.7	. . 3 ⊢ (𝜑 → 𝑃 ∥ 𝑁)
3		aks6d1c7.1	. . . . . . 7 ⊢ ∼ = {⟨𝑒, 𝑓⟩ ∣ (𝑒 ∈ ℕ ∧ 𝑓 ∈ (Base‘(Poly₁‘𝐾)) ∧ ∀𝑦 ∈ ((mulGrp‘𝐾) PrimRoots 𝑅)(𝑒(._g‘(mulGrp‘𝐾))(((eval₁‘𝐾)‘𝑓)‘𝑦)) = (((eval₁‘𝐾)‘𝑓)‘(𝑒(._g‘(mulGrp‘𝐾))𝑦)))}
4		aks6d1c7.2	. . . . . . 7 ⊢ 𝑃 = (chr‘𝐾)
5		aks6d1c7.3	. . . . . . . 8 ⊢ (𝜑 → 𝐾 ∈ Field)
6	5	ad2antrr 725	. . . . . . 7 ⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ 𝑁) → 𝐾 ∈ Field)
7	1	ad2antrr 725	. . . . . . 7 ⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ 𝑁) → 𝑃 ∈ ℙ)
8		aks6d1c7.5	. . . . . . . 8 ⊢ (𝜑 → 𝑅 ∈ ℕ)
9	8	ad2antrr 725	. . . . . . 7 ⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ 𝑁) → 𝑅 ∈ ℕ)
10		aks6d1c7.6	. . . . . . . 8 ⊢ (𝜑 → 𝑁 ∈ (ℤ_≥‘3))
11	10	ad2antrr 725	. . . . . . 7 ⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ 𝑁) → 𝑁 ∈ (ℤ_≥‘3))
12	2	ad2antrr 725	. . . . . . 7 ⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ 𝑁) → 𝑃 ∥ 𝑁)
13		aks6d1c7.8	. . . . . . . 8 ⊢ (𝜑 → (𝑁 gcd 𝑅) = 1)
14	13	ad2antrr 725	. . . . . . 7 ⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ 𝑁) → (𝑁 gcd 𝑅) = 1)
15		aks6d1c7.9	. . . . . . 7 ⊢ 𝐴 = (⌊‘((√‘(ϕ‘𝑅)) · (2 log_b 𝑁)))
16		aks6d1c7.10	. . . . . . . 8 ⊢ (𝜑 → ((2 log_b 𝑁)↑2) < ((od_ℤ‘𝑅)‘𝑁))
17	16	ad2antrr 725	. . . . . . 7 ⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ 𝑁) → ((2 log_b 𝑁)↑2) < ((od_ℤ‘𝑅)‘𝑁))
18		aks6d1c7.11	. . . . . . . 8 ⊢ (𝜑 → (𝑥 ∈ (Base‘𝐾) ↦ (𝑃(._g‘(mulGrp‘𝐾))𝑥)) ∈ (𝐾 RingIso 𝐾))
19	18	ad2antrr 725	. . . . . . 7 ⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ 𝑁) → (𝑥 ∈ (Base‘𝐾) ↦ (𝑃(._g‘(mulGrp‘𝐾))𝑥)) ∈ (𝐾 RingIso 𝐾))
20		aks6d1c7.12	. . . . . . . 8 ⊢ (𝜑 → 𝑀 ∈ ((mulGrp‘𝐾) PrimRoots 𝑅))
21	20	ad2antrr 725	. . . . . . 7 ⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ 𝑁) → 𝑀 ∈ ((mulGrp‘𝐾) PrimRoots 𝑅))
22		aks6d1c7.13	. . . . . . . 8 ⊢ (𝜑 → ∀𝑏 ∈ (1...𝐴)(𝑏 gcd 𝑁) = 1)
23	22	ad2antrr 725	. . . . . . 7 ⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ 𝑁) → ∀𝑏 ∈ (1...𝐴)(𝑏 gcd 𝑁) = 1)
24		aks6d1c7.14	. . . . . . . 8 ⊢ (𝜑 → ∀𝑎 ∈ (1...𝐴)𝑁 ∼ ((var₁‘𝐾)(+_g‘(Poly₁‘𝐾))((algSc‘(Poly₁‘𝐾))‘((ℤRHom‘𝐾)‘𝑎))))
25	24	ad2antrr 725	. . . . . . 7 ⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ 𝑁) → ∀𝑎 ∈ (1...𝐴)𝑁 ∼ ((var₁‘𝐾)(+_g‘(Poly₁‘𝐾))((algSc‘(Poly₁‘𝐾))‘((ℤRHom‘𝐾)‘𝑎))))
26		simplr 768	. . . . . . . 8 ⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ 𝑁) → 𝑝 ∈ ℙ)
27		simpr 484	. . . . . . . 8 ⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ 𝑁) → 𝑝 ∥ 𝑁)
28	26, 27	jca 511	. . . . . . 7 ⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ 𝑁) → (𝑝 ∈ ℙ ∧ 𝑝 ∥ 𝑁))
29	3, 4, 6, 7, 9, 11, 12, 14, 15, 17, 19, 21, 23, 25, 28	aks6d1c7lem3 42141	. . . . . 6 ⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ 𝑁) → 𝑃 = 𝑝)
30	29	eqcomd 2746	. . . . 5 ⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ 𝑁) → 𝑝 = 𝑃)
31	30	ex 412	. . . 4 ⊢ ((𝜑 ∧ 𝑝 ∈ ℙ) → (𝑝 ∥ 𝑁 → 𝑝 = 𝑃))
32	31	ralrimiva 3152	. . 3 ⊢ (𝜑 → ∀𝑝 ∈ ℙ (𝑝 ∥ 𝑁 → 𝑝 = 𝑃))
33	1, 2, 32	3jca 1128	. 2 ⊢ (𝜑 → (𝑃 ∈ ℙ ∧ 𝑃 ∥ 𝑁 ∧ ∀𝑝 ∈ ℙ (𝑝 ∥ 𝑁 → 𝑝 = 𝑃)))
34		breq1 5169	. . 3 ⊢ (𝑝 = 𝑃 → (𝑝 ∥ 𝑁 ↔ 𝑃 ∥ 𝑁))
35	34	eqreu 3751	. 2 ⊢ ((𝑃 ∈ ℙ ∧ 𝑃 ∥ 𝑁 ∧ ∀𝑝 ∈ ℙ (𝑝 ∥ 𝑁 → 𝑝 = 𝑃)) → ∃!𝑝 ∈ ℙ 𝑝 ∥ 𝑁)
36	33, 35	syl 17	1 ⊢ (𝜑 → ∃!𝑝 ∈ ℙ 𝑝 ∥ 𝑁)

Colors of variables: wff setvar class

Syntax hints: → wi 4 ∧ wa 395 ∧ w3a 1087 = wceq 1537 ∈ wcel 2108 ∀wral 3067 ∃!wreu 3386 class class class wbr 5166 {copab 5228 ↦ cmpt 5249 ‘cfv 6575 (class class class)co 7450 1c1 11187 · cmul 11191 < clt 11326 ℕcn 12295 2c2 12350 3c3 12351 ℤ_≥cuz 12905 ...cfz 13569 ⌊cfl 13843 ↑cexp 14114 √csqrt 15284 ∥ cdvds 16304 gcd cgcd 16542 ℙcprime 16720 od_ℤcodz 16812 ϕcphi 16813 Basecbs 17260 +_gcplusg 17313 ._gcmg 19109 mulGrpcmgp 20163 RingIso crs 20498 Fieldcfield 20754 ℤRHomczrh 21535 chrcchr 21537 algSccascl 21897 var₁cv1 22200 Poly₁cpl1 22201 eval₁ce1 22341 log_b clogb 26827 PrimRoots cprimroots 42050

This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1793 ax-4 1807 ax-5 1909 ax-6 1967 ax-7 2007 ax-8 2110 ax-9 2118 ax-10 2141 ax-11 2158 ax-12 2178 ax-ext 2711 ax-rep 5303 ax-sep 5317 ax-nul 5324 ax-pow 5383 ax-pr 5447 ax-un 7772 ax-inf2 9712 ax-cnex 11242 ax-resscn 11243 ax-1cn 11244 ax-icn 11245 ax-addcl 11246 ax-addrcl 11247 ax-mulcl 11248 ax-mulrcl 11249 ax-mulcom 11250 ax-addass 11251 ax-mulass 11252 ax-distr 11253 ax-i2m1 11254 ax-1ne0 11255 ax-1rid 11256 ax-rnegex 11257 ax-rrecex 11258 ax-cnre 11259 ax-pre-lttri 11260 ax-pre-lttrn 11261 ax-pre-ltadd 11262 ax-pre-mulgt0 11263 ax-pre-sup 11264 ax-addf 11265 ax-mulf 11266

This theorem depends on definitions: df-bi 207 df-an 396 df-or 847 df-3or 1088 df-3an 1089 df-tru 1540 df-fal 1550 df-ex 1778 df-nf 1782 df-sb 2065 df-mo 2543 df-eu 2572 df-clab 2718 df-cleq 2732 df-clel 2819 df-nfc 2895 df-ne 2947 df-nel 3053 df-ral 3068 df-rex 3077 df-rmo 3388 df-reu 3389 df-rab 3444 df-v 3490 df-sbc 3805 df-csb 3922 df-dif 3979 df-un 3981 df-in 3983 df-ss 3993 df-pss 3996 df-nul 4353 df-if 4549 df-pw 4624 df-sn 4649 df-pr 4651 df-tp 4653 df-op 4655 df-uni 4932 df-int 4971 df-iun 5017 df-iin 5018 df-br 5167 df-opab 5229 df-mpt 5250 df-tr 5284 df-id 5593 df-eprel 5599 df-po 5607 df-so 5608 df-fr 5652 df-se 5653 df-we 5654 df-xp 5706 df-rel 5707 df-cnv 5708 df-co 5709 df-dm 5710 df-rn 5711 df-res 5712 df-ima 5713 df-pred 6334 df-ord 6400 df-on 6401 df-lim 6402 df-suc 6403 df-iota 6527 df-fun 6577 df-fn 6578 df-f 6579 df-f1 6580 df-fo 6581 df-f1o 6582 df-fv 6583 df-isom 6584 df-riota 7406 df-ov 7453 df-oprab 7454 df-mpo 7455 df-of 7716 df-ofr 7717 df-om 7906 df-1st 8032 df-2nd 8033 df-supp 8204 df-tpos 8269 df-frecs 8324 df-wrecs 8355 df-recs 8429 df-rdg 8468 df-1o 8524 df-2o 8525 df-oadd 8528 df-er 8765 df-ec 8767 df-qs 8771 df-map 8888 df-pm 8889 df-ixp 8958 df-en 9006 df-dom 9007 df-sdom 9008 df-fin 9009 df-fsupp 9434 df-fi 9482 df-sup 9513 df-inf 9514 df-oi 9581 df-dju 9972 df-card 10010 df-pnf 11328 df-mnf 11329 df-xr 11330 df-ltxr 11331 df-le 11332 df-sub 11524 df-neg 11525 df-div 11950 df-nn 12296 df-2 12358 df-3 12359 df-4 12360 df-5 12361 df-6 12362 df-7 12363 df-8 12364 df-9 12365 df-n0 12556 df-xnn0 12628 df-z 12642 df-dec 12761 df-uz 12906 df-q 13016 df-rp 13060 df-xneg 13177 df-xadd 13178 df-xmul 13179 df-ioo 13413 df-ioc 13414 df-ico 13415 df-icc 13416 df-fz 13570 df-fzo 13714 df-fl 13845 df-mod 13923 df-seq 14055 df-exp 14115 df-fac 14325 df-bc 14354 df-hash 14382 df-shft 15118 df-cj 15150 df-re 15151 df-im 15152 df-sqrt 15286 df-abs 15287 df-limsup 15519 df-clim 15536 df-rlim 15537 df-sum 15737 df-prod 15954 df-fallfac 16057 df-ef 16117 df-sin 16119 df-cos 16120 df-pi 16122 df-dvds 16305 df-gcd 16543 df-prm 16721 df-odz 16814 df-phi 16815 df-pc 16886 df-struct 17196 df-sets 17213 df-slot 17231 df-ndx 17243 df-base 17261 df-ress 17290 df-plusg 17326 df-mulr 17327 df-starv 17328 df-sca 17329 df-vsca 17330 df-ip 17331 df-tset 17332 df-ple 17333 df-ds 17335 df-unif 17336 df-hom 17337 df-cco 17338 df-rest 17484 df-topn 17485 df-0g 17503 df-gsum 17504 df-topgen 17505 df-pt 17506 df-prds 17509 df-pws 17511 df-xrs 17564 df-qtop 17569 df-imas 17570 df-qus 17571 df-xps 17572 df-mre 17646 df-mrc 17647 df-acs 17649 df-mgm 18680 df-sgrp 18759 df-mnd 18775 df-mhm 18820 df-submnd 18821 df-grp 18978 df-minusg 18979 df-sbg 18980 df-mulg 19110 df-subg 19165 df-nsg 19166 df-eqg 19167 df-ghm 19255 df-gim 19301 df-cntz 19359 df-od 19572 df-cmn 19826 df-abl 19827 df-mgp 20164 df-rng 20182 df-ur 20211 df-srg 20216 df-ring 20264 df-cring 20265 df-oppr 20362 df-dvdsr 20385 df-unit 20386 df-invr 20416 df-dvr 20429 df-rhm 20500 df-rim 20501 df-nzr 20541 df-subrng 20574 df-subrg 20599 df-rlreg 20718 df-domn 20719 df-idom 20720 df-drng 20755 df-field 20756 df-lmod 20884 df-lss 20955 df-lsp 20995 df-sra 21197 df-rgmod 21198 df-lidl 21243 df-rsp 21244 df-2idl 21285 df-psmet 21381 df-xmet 21382 df-met 21383 df-bl 21384 df-mopn 21385 df-fbas 21386 df-fg 21387 df-cnfld 21390 df-zring 21483 df-zrh 21539 df-chr 21541 df-zn 21542 df-assa 21898 df-asp 21899 df-ascl 21900 df-psr 21954 df-mvr 21955 df-mpl 21956 df-opsr 21958 df-evls 22123 df-evl 22124 df-psr1 22204 df-vr1 22205 df-ply1 22206 df-coe1 22207 df-evl1 22343 df-top 22923 df-topon 22940 df-topsp 22962 df-bases 22976 df-cld 23050 df-ntr 23051 df-cls 23052 df-nei 23129 df-lp 23167 df-perf 23168 df-cn 23258 df-cnp 23259 df-haus 23346 df-tx 23593 df-hmeo 23786 df-fil 23877 df-fm 23969 df-flim 23970 df-flf 23971 df-xms 24353 df-ms 24354 df-tms 24355 df-cncf 24925 df-limc 25923 df-dv 25924 df-mdeg 26116 df-deg1 26117 df-mon1 26192 df-uc1p 26193 df-q1p 26194 df-r1p 26195 df-log 26618 df-cxp 26619 df-logb 26828 df-primroots 42051

This theorem is referenced by: aks6d1c7 42143

W3C validator