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

Theorem aks4d1 42068
Description: Lemma 4.1 from https://www3.nd.edu/%7eandyp/notes/AKS.pdf, existence of a polynomially bounded number by the digit size of 𝑁 that asserts the polynomial subspace that we need to search to guarantee that 𝑁 is prime. Eventually we want to show that the polynomial searching space is bounded by degree 𝐵. (Contributed by metakunt, 14-Nov-2024.)
Hypotheses
Ref Expression
aks4d1.1 (𝜑𝑁 ∈ (ℤ‘3))
aks4d1.2 𝐵 = (⌈‘((2 logb 𝑁)↑5))
Assertion
Ref Expression
aks4d1 (𝜑 → ∃𝑟 ∈ (1...𝐵)((𝑁 gcd 𝑟) = 1 ∧ ((2 logb 𝑁)↑2) < ((od𝑟)‘𝑁)))
Distinct variable groups:   𝐵,𝑟   𝑁,𝑟   𝜑,𝑟

Proof of Theorem aks4d1
Dummy variables 𝑎 𝑘 𝑏 𝑐 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 aks4d1.1 . . . 4 (𝜑𝑁 ∈ (ℤ‘3))
2 oveq2 7437 . . . . . . 7 (𝑏 = 𝑎 → (𝑁𝑏) = (𝑁𝑎))
32oveq1d 7444 . . . . . 6 (𝑏 = 𝑎 → ((𝑁𝑏) − 1) = ((𝑁𝑎) − 1))
43cbvprodv 15946 . . . . 5 𝑏 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑏) − 1) = ∏𝑎 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑎) − 1)
54oveq2i 7440 . . . 4 ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑏 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑏) − 1)) = ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑎 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑎) − 1))
6 aks4d1.2 . . . 4 𝐵 = (⌈‘((2 logb 𝑁)↑5))
7 id 22 . . . . . . . 8 ( = 𝑘 = 𝑘)
8 oveq2 7437 . . . . . . . . . . . 12 (𝑐 = 𝑏 → (𝑁𝑐) = (𝑁𝑏))
98oveq1d 7444 . . . . . . . . . . 11 (𝑐 = 𝑏 → ((𝑁𝑐) − 1) = ((𝑁𝑏) − 1))
109cbvprodv 15946 . . . . . . . . . 10 𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1) = ∏𝑏 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑏) − 1)
1110oveq2i 7440 . . . . . . . . 9 ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1)) = ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑏 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑏) − 1))
1211a1i 11 . . . . . . . 8 ( = 𝑘 → ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1)) = ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑏 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑏) − 1)))
137, 12breq12d 5154 . . . . . . 7 ( = 𝑘 → ( ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1)) ↔ 𝑘 ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑏 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑏) − 1))))
1413notbid 318 . . . . . 6 ( = 𝑘 → (¬ ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1)) ↔ ¬ 𝑘 ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑏 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑏) − 1))))
1514cbvrabv 3446 . . . . 5 { ∈ (1...𝐵) ∣ ¬ ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1))} = {𝑘 ∈ (1...𝐵) ∣ ¬ 𝑘 ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑏 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑏) − 1))}
1615infeq1i 9514 . . . 4 inf({ ∈ (1...𝐵) ∣ ¬ ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1))}, ℝ, < ) = inf({𝑘 ∈ (1...𝐵) ∣ ¬ 𝑘 ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑏 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑏) − 1))}, ℝ, < )
171, 5, 6, 16aks4d1p4 42058 . . 3 (𝜑 → (inf({ ∈ (1...𝐵) ∣ ¬ ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1))}, ℝ, < ) ∈ (1...𝐵) ∧ ¬ inf({ ∈ (1...𝐵) ∣ ¬ ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1))}, ℝ, < ) ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑏 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑏) − 1))))
1817simpld 494 . 2 (𝜑 → inf({ ∈ (1...𝐵) ∣ ¬ ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1))}, ℝ, < ) ∈ (1...𝐵))
19 oveq2 7437 . . . . 5 (𝑟 = inf({ ∈ (1...𝐵) ∣ ¬ ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1))}, ℝ, < ) → (𝑁 gcd 𝑟) = (𝑁 gcd inf({ ∈ (1...𝐵) ∣ ¬ ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1))}, ℝ, < )))
2019adantl 481 . . . 4 ((𝜑𝑟 = inf({ ∈ (1...𝐵) ∣ ¬ ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1))}, ℝ, < )) → (𝑁 gcd 𝑟) = (𝑁 gcd inf({ ∈ (1...𝐵) ∣ ¬ ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1))}, ℝ, < )))
2120eqeq1d 2738 . . 3 ((𝜑𝑟 = inf({ ∈ (1...𝐵) ∣ ¬ ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1))}, ℝ, < )) → ((𝑁 gcd 𝑟) = 1 ↔ (𝑁 gcd inf({ ∈ (1...𝐵) ∣ ¬ ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1))}, ℝ, < )) = 1))
22 fveq2 6904 . . . . . 6 (𝑟 = inf({ ∈ (1...𝐵) ∣ ¬ ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1))}, ℝ, < ) → (od𝑟) = (od‘inf({ ∈ (1...𝐵) ∣ ¬ ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1))}, ℝ, < )))
2322adantl 481 . . . . 5 ((𝜑𝑟 = inf({ ∈ (1...𝐵) ∣ ¬ ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1))}, ℝ, < )) → (od𝑟) = (od‘inf({ ∈ (1...𝐵) ∣ ¬ ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1))}, ℝ, < )))
2423fveq1d 6906 . . . 4 ((𝜑𝑟 = inf({ ∈ (1...𝐵) ∣ ¬ ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1))}, ℝ, < )) → ((od𝑟)‘𝑁) = ((od‘inf({ ∈ (1...𝐵) ∣ ¬ ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1))}, ℝ, < ))‘𝑁))
2524breq2d 5153 . . 3 ((𝜑𝑟 = inf({ ∈ (1...𝐵) ∣ ¬ ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1))}, ℝ, < )) → (((2 logb 𝑁)↑2) < ((od𝑟)‘𝑁) ↔ ((2 logb 𝑁)↑2) < ((od‘inf({ ∈ (1...𝐵) ∣ ¬ ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1))}, ℝ, < ))‘𝑁)))
2621, 25anbi12d 632 . 2 ((𝜑𝑟 = inf({ ∈ (1...𝐵) ∣ ¬ ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1))}, ℝ, < )) → (((𝑁 gcd 𝑟) = 1 ∧ ((2 logb 𝑁)↑2) < ((od𝑟)‘𝑁)) ↔ ((𝑁 gcd inf({ ∈ (1...𝐵) ∣ ¬ ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1))}, ℝ, < )) = 1 ∧ ((2 logb 𝑁)↑2) < ((od‘inf({ ∈ (1...𝐵) ∣ ¬ ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1))}, ℝ, < ))‘𝑁))))
271, 5, 6, 16aks4d1p8 42066 . . 3 (𝜑 → (𝑁 gcd inf({ ∈ (1...𝐵) ∣ ¬ ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1))}, ℝ, < )) = 1)
281, 5, 6, 16aks4d1p9 42067 . . 3 (𝜑 → ((2 logb 𝑁)↑2) < ((od‘inf({ ∈ (1...𝐵) ∣ ¬ ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1))}, ℝ, < ))‘𝑁))
2927, 28jca 511 . 2 (𝜑 → ((𝑁 gcd inf({ ∈ (1...𝐵) ∣ ¬ ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1))}, ℝ, < )) = 1 ∧ ((2 logb 𝑁)↑2) < ((od‘inf({ ∈ (1...𝐵) ∣ ¬ ∥ ((𝑁↑(⌊‘(2 logb 𝐵))) · ∏𝑐 ∈ (1...(⌊‘((2 logb 𝑁)↑2)))((𝑁𝑐) − 1))}, ℝ, < ))‘𝑁)))
3018, 26, 29rspcedvd 3623 1 (𝜑 → ∃𝑟 ∈ (1...𝐵)((𝑁 gcd 𝑟) = 1 ∧ ((2 logb 𝑁)↑2) < ((od𝑟)‘𝑁)))
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wi 4  wa 395   = wceq 1540  wcel 2108  wrex 3069  {crab 3435   class class class wbr 5141  cfv 6559  (class class class)co 7429  infcinf 9477  cr 11150  1c1 11152   · cmul 11156   < clt 11291  cmin 11488  2c2 12317  3c3 12318  5c5 12320  cuz 12874  ...cfz 13543  cfl 13826  cceil 13827  cexp 14098  cprod 15935  cdvds 16286   gcd cgcd 16527  odcodz 16796   logb clogb 26797
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1795  ax-4 1809  ax-5 1910  ax-6 1967  ax-7 2007  ax-8 2110  ax-9 2118  ax-10 2141  ax-11 2157  ax-12 2177  ax-ext 2707  ax-rep 5277  ax-sep 5294  ax-nul 5304  ax-pow 5363  ax-pr 5430  ax-un 7751  ax-inf2 9677  ax-cc 10471  ax-cnex 11207  ax-resscn 11208  ax-1cn 11209  ax-icn 11210  ax-addcl 11211  ax-addrcl 11212  ax-mulcl 11213  ax-mulrcl 11214  ax-mulcom 11215  ax-addass 11216  ax-mulass 11217  ax-distr 11218  ax-i2m1 11219  ax-1ne0 11220  ax-1rid 11221  ax-rnegex 11222  ax-rrecex 11223  ax-cnre 11224  ax-pre-lttri 11225  ax-pre-lttrn 11226  ax-pre-ltadd 11227  ax-pre-mulgt0 11228  ax-pre-sup 11229  ax-addf 11230
This theorem depends on definitions:  df-bi 207  df-an 396  df-or 849  df-3or 1088  df-3an 1089  df-tru 1543  df-fal 1553  df-ex 1780  df-nf 1784  df-sb 2065  df-mo 2539  df-eu 2568  df-clab 2714  df-cleq 2728  df-clel 2815  df-nfc 2891  df-ne 2940  df-nel 3046  df-ral 3061  df-rex 3070  df-rmo 3379  df-reu 3380  df-rab 3436  df-v 3481  df-sbc 3788  df-csb 3899  df-dif 3953  df-un 3955  df-in 3957  df-ss 3967  df-pss 3970  df-symdif 4252  df-nul 4333  df-if 4525  df-pw 4600  df-sn 4625  df-pr 4627  df-tp 4629  df-op 4631  df-uni 4906  df-int 4945  df-iun 4991  df-iin 4992  df-disj 5109  df-br 5142  df-opab 5204  df-mpt 5224  df-tr 5258  df-id 5576  df-eprel 5582  df-po 5590  df-so 5591  df-fr 5635  df-se 5636  df-we 5637  df-xp 5689  df-rel 5690  df-cnv 5691  df-co 5692  df-dm 5693  df-rn 5694  df-res 5695  df-ima 5696  df-pred 6319  df-ord 6385  df-on 6386  df-lim 6387  df-suc 6388  df-iota 6512  df-fun 6561  df-fn 6562  df-f 6563  df-f1 6564  df-fo 6565  df-f1o 6566  df-fv 6567  df-isom 6568  df-riota 7386  df-ov 7432  df-oprab 7433  df-mpo 7434  df-of 7694  df-ofr 7695  df-om 7884  df-1st 8010  df-2nd 8011  df-supp 8182  df-frecs 8302  df-wrecs 8333  df-recs 8407  df-rdg 8446  df-1o 8502  df-2o 8503  df-oadd 8506  df-omul 8507  df-er 8741  df-map 8864  df-pm 8865  df-ixp 8934  df-en 8982  df-dom 8983  df-sdom 8984  df-fin 8985  df-fsupp 9398  df-fi 9447  df-sup 9478  df-inf 9479  df-oi 9546  df-dju 9937  df-card 9975  df-acn 9978  df-pnf 11293  df-mnf 11294  df-xr 11295  df-ltxr 11296  df-le 11297  df-sub 11490  df-neg 11491  df-div 11917  df-nn 12263  df-2 12325  df-3 12326  df-4 12327  df-5 12328  df-6 12329  df-7 12330  df-8 12331  df-9 12332  df-n0 12523  df-xnn0 12596  df-z 12610  df-dec 12730  df-uz 12875  df-q 12987  df-rp 13031  df-xneg 13150  df-xadd 13151  df-xmul 13152  df-ioo 13387  df-ioc 13388  df-ico 13389  df-icc 13390  df-fz 13544  df-fzo 13691  df-fl 13828  df-ceil 13829  df-mod 13906  df-seq 14039  df-exp 14099  df-fac 14309  df-bc 14338  df-hash 14366  df-shft 15102  df-cj 15134  df-re 15135  df-im 15136  df-sqrt 15270  df-abs 15271  df-limsup 15503  df-clim 15520  df-rlim 15521  df-sum 15719  df-prod 15936  df-ef 16099  df-e 16100  df-sin 16101  df-cos 16102  df-pi 16104  df-dvds 16287  df-gcd 16528  df-lcm 16623  df-lcmf 16624  df-prm 16705  df-odz 16798  df-phi 16799  df-pc 16871  df-struct 17180  df-sets 17197  df-slot 17215  df-ndx 17227  df-base 17244  df-ress 17271  df-plusg 17306  df-mulr 17307  df-starv 17308  df-sca 17309  df-vsca 17310  df-ip 17311  df-tset 17312  df-ple 17313  df-ds 17315  df-unif 17316  df-hom 17317  df-cco 17318  df-rest 17463  df-topn 17464  df-0g 17482  df-gsum 17483  df-topgen 17484  df-pt 17485  df-prds 17488  df-xrs 17543  df-qtop 17548  df-imas 17549  df-xps 17551  df-mre 17625  df-mrc 17626  df-acs 17628  df-mgm 18649  df-sgrp 18728  df-mnd 18744  df-submnd 18793  df-mulg 19082  df-cntz 19331  df-cmn 19796  df-psmet 21348  df-xmet 21349  df-met 21350  df-bl 21351  df-mopn 21352  df-fbas 21353  df-fg 21354  df-cnfld 21357  df-top 22890  df-topon 22907  df-topsp 22929  df-bases 22943  df-cld 23017  df-ntr 23018  df-cls 23019  df-nei 23096  df-lp 23134  df-perf 23135  df-cn 23225  df-cnp 23226  df-haus 23313  df-cmp 23385  df-tx 23560  df-hmeo 23753  df-fil 23844  df-fm 23936  df-flim 23937  df-flf 23938  df-xms 24320  df-ms 24321  df-tms 24322  df-cncf 24894  df-ovol 25489  df-vol 25490  df-mbf 25644  df-itg1 25645  df-itg2 25646  df-ibl 25647  df-itg 25648  df-0p 25695  df-limc 25891  df-dv 25892  df-log 26588  df-cxp 26589  df-logb 26798
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator