![]() |
Metamath Proof Explorer |
< Previous
Next >
Nearby theorems |
|
Mirrors > Home > MPE Home > Th. List > dirith | Structured version Visualization version GIF version |
Description: Dirichlet's theorem: there are infinitely many primes in any arithmetic progression coprime to 𝑁. Theorem 9.4.1 of [Shapiro], p. 375. See http://metamath-blog.blogspot.com/2016/05/dirichlets-theorem.html for an informal exposition. This is Metamath 100 proof #48. (Contributed by Mario Carneiro, 12-May-2016.) |
Ref | Expression |
---|---|
dirith | ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → {𝑝 ∈ ℙ ∣ 𝑁 ∥ (𝑝 − 𝐴)} ≈ ℕ) |
Step | Hyp | Ref | Expression |
---|---|---|---|
1 | simp1 1116 | . . . . . . . 8 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → 𝑁 ∈ ℕ) | |
2 | 1 | nnnn0d 11760 | . . . . . . 7 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → 𝑁 ∈ ℕ0) |
3 | 2 | adantr 473 | . . . . . 6 ⊢ (((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) ∧ 𝑝 ∈ ℙ) → 𝑁 ∈ ℕ0) |
4 | eqid 2772 | . . . . . . 7 ⊢ (ℤ/nℤ‘𝑁) = (ℤ/nℤ‘𝑁) | |
5 | eqid 2772 | . . . . . . 7 ⊢ (Base‘(ℤ/nℤ‘𝑁)) = (Base‘(ℤ/nℤ‘𝑁)) | |
6 | eqid 2772 | . . . . . . 7 ⊢ (ℤRHom‘(ℤ/nℤ‘𝑁)) = (ℤRHom‘(ℤ/nℤ‘𝑁)) | |
7 | 4, 5, 6 | znzrhfo 20386 | . . . . . 6 ⊢ (𝑁 ∈ ℕ0 → (ℤRHom‘(ℤ/nℤ‘𝑁)):ℤ–onto→(Base‘(ℤ/nℤ‘𝑁))) |
8 | fofn 6415 | . . . . . 6 ⊢ ((ℤRHom‘(ℤ/nℤ‘𝑁)):ℤ–onto→(Base‘(ℤ/nℤ‘𝑁)) → (ℤRHom‘(ℤ/nℤ‘𝑁)) Fn ℤ) | |
9 | 3, 7, 8 | 3syl 18 | . . . . 5 ⊢ (((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) ∧ 𝑝 ∈ ℙ) → (ℤRHom‘(ℤ/nℤ‘𝑁)) Fn ℤ) |
10 | prmz 15865 | . . . . . 6 ⊢ (𝑝 ∈ ℙ → 𝑝 ∈ ℤ) | |
11 | 10 | adantl 474 | . . . . 5 ⊢ (((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) ∧ 𝑝 ∈ ℙ) → 𝑝 ∈ ℤ) |
12 | fniniseg 6649 | . . . . . 6 ⊢ ((ℤRHom‘(ℤ/nℤ‘𝑁)) Fn ℤ → (𝑝 ∈ (◡(ℤRHom‘(ℤ/nℤ‘𝑁)) “ {((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)}) ↔ (𝑝 ∈ ℤ ∧ ((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝑝) = ((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)))) | |
13 | 12 | baibd 532 | . . . . 5 ⊢ (((ℤRHom‘(ℤ/nℤ‘𝑁)) Fn ℤ ∧ 𝑝 ∈ ℤ) → (𝑝 ∈ (◡(ℤRHom‘(ℤ/nℤ‘𝑁)) “ {((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)}) ↔ ((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝑝) = ((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴))) |
14 | 9, 11, 13 | syl2anc 576 | . . . 4 ⊢ (((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) ∧ 𝑝 ∈ ℙ) → (𝑝 ∈ (◡(ℤRHom‘(ℤ/nℤ‘𝑁)) “ {((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)}) ↔ ((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝑝) = ((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴))) |
15 | simp2 1117 | . . . . . 6 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → 𝐴 ∈ ℤ) | |
16 | 15 | adantr 473 | . . . . 5 ⊢ (((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) ∧ 𝑝 ∈ ℙ) → 𝐴 ∈ ℤ) |
17 | 4, 6 | zndvds 20388 | . . . . 5 ⊢ ((𝑁 ∈ ℕ0 ∧ 𝑝 ∈ ℤ ∧ 𝐴 ∈ ℤ) → (((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝑝) = ((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴) ↔ 𝑁 ∥ (𝑝 − 𝐴))) |
18 | 3, 11, 16, 17 | syl3anc 1351 | . . . 4 ⊢ (((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) ∧ 𝑝 ∈ ℙ) → (((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝑝) = ((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴) ↔ 𝑁 ∥ (𝑝 − 𝐴))) |
19 | 14, 18 | bitrd 271 | . . 3 ⊢ (((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) ∧ 𝑝 ∈ ℙ) → (𝑝 ∈ (◡(ℤRHom‘(ℤ/nℤ‘𝑁)) “ {((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)}) ↔ 𝑁 ∥ (𝑝 − 𝐴))) |
20 | 19 | rabbi2dva 4076 | . 2 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → (ℙ ∩ (◡(ℤRHom‘(ℤ/nℤ‘𝑁)) “ {((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)})) = {𝑝 ∈ ℙ ∣ 𝑁 ∥ (𝑝 − 𝐴)}) |
21 | eqid 2772 | . . 3 ⊢ (Unit‘(ℤ/nℤ‘𝑁)) = (Unit‘(ℤ/nℤ‘𝑁)) | |
22 | simp3 1118 | . . . 4 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → (𝐴 gcd 𝑁) = 1) | |
23 | 4, 21, 6 | znunit 20402 | . . . . 5 ⊢ ((𝑁 ∈ ℕ0 ∧ 𝐴 ∈ ℤ) → (((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴) ∈ (Unit‘(ℤ/nℤ‘𝑁)) ↔ (𝐴 gcd 𝑁) = 1)) |
24 | 2, 15, 23 | syl2anc 576 | . . . 4 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → (((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴) ∈ (Unit‘(ℤ/nℤ‘𝑁)) ↔ (𝐴 gcd 𝑁) = 1)) |
25 | 22, 24 | mpbird 249 | . . 3 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → ((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴) ∈ (Unit‘(ℤ/nℤ‘𝑁))) |
26 | eqid 2772 | . . 3 ⊢ (◡(ℤRHom‘(ℤ/nℤ‘𝑁)) “ {((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)}) = (◡(ℤRHom‘(ℤ/nℤ‘𝑁)) “ {((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)}) | |
27 | 4, 6, 1, 21, 25, 26 | dirith2 25796 | . 2 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → (ℙ ∩ (◡(ℤRHom‘(ℤ/nℤ‘𝑁)) “ {((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)})) ≈ ℕ) |
28 | 20, 27 | eqbrtrrd 4947 | 1 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → {𝑝 ∈ ℙ ∣ 𝑁 ∥ (𝑝 − 𝐴)} ≈ ℕ) |
Colors of variables: wff setvar class |
Syntax hints: → wi 4 ↔ wb 198 ∧ wa 387 ∧ w3a 1068 = wceq 1507 ∈ wcel 2048 {crab 3086 ∩ cin 3824 {csn 4435 class class class wbr 4923 ◡ccnv 5399 “ cima 5403 Fn wfn 6177 –onto→wfo 6180 ‘cfv 6182 (class class class)co 6970 ≈ cen 8295 1c1 10328 − cmin 10662 ℕcn 11431 ℕ0cn0 11700 ℤcz 11786 ∥ cdvds 15457 gcd cgcd 15693 ℙcprime 15861 Basecbs 16329 Unitcui 19102 ℤRHomczrh 20339 ℤ/nℤczn 20342 |
This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1758 ax-4 1772 ax-5 1869 ax-6 1928 ax-7 1964 ax-8 2050 ax-9 2057 ax-10 2077 ax-11 2091 ax-12 2104 ax-13 2299 ax-ext 2745 ax-rep 5043 ax-sep 5054 ax-nul 5061 ax-pow 5113 ax-pr 5180 ax-un 7273 ax-inf2 8890 ax-cnex 10383 ax-resscn 10384 ax-1cn 10385 ax-icn 10386 ax-addcl 10387 ax-addrcl 10388 ax-mulcl 10389 ax-mulrcl 10390 ax-mulcom 10391 ax-addass 10392 ax-mulass 10393 ax-distr 10394 ax-i2m1 10395 ax-1ne0 10396 ax-1rid 10397 ax-rnegex 10398 ax-rrecex 10399 ax-cnre 10400 ax-pre-lttri 10401 ax-pre-lttrn 10402 ax-pre-ltadd 10403 ax-pre-mulgt0 10404 ax-pre-sup 10405 ax-addf 10406 ax-mulf 10407 |
This theorem depends on definitions: df-bi 199 df-an 388 df-or 834 df-3or 1069 df-3an 1070 df-tru 1510 df-fal 1520 df-ex 1743 df-nf 1747 df-sb 2014 df-mo 2544 df-eu 2580 df-clab 2754 df-cleq 2765 df-clel 2840 df-nfc 2912 df-ne 2962 df-nel 3068 df-ral 3087 df-rex 3088 df-reu 3089 df-rmo 3090 df-rab 3091 df-v 3411 df-sbc 3678 df-csb 3783 df-dif 3828 df-un 3830 df-in 3832 df-ss 3839 df-pss 3841 df-nul 4174 df-if 4345 df-pw 4418 df-sn 4436 df-pr 4438 df-tp 4440 df-op 4442 df-uni 4707 df-int 4744 df-iun 4788 df-iin 4789 df-disj 4892 df-br 4924 df-opab 4986 df-mpt 5003 df-tr 5025 df-id 5305 df-eprel 5310 df-po 5319 df-so 5320 df-fr 5359 df-se 5360 df-we 5361 df-xp 5406 df-rel 5407 df-cnv 5408 df-co 5409 df-dm 5410 df-rn 5411 df-res 5412 df-ima 5413 df-pred 5980 df-ord 6026 df-on 6027 df-lim 6028 df-suc 6029 df-iota 6146 df-fun 6184 df-fn 6185 df-f 6186 df-f1 6187 df-fo 6188 df-f1o 6189 df-fv 6190 df-isom 6191 df-riota 6931 df-ov 6973 df-oprab 6974 df-mpo 6975 df-of 7221 df-rpss 7261 df-om 7391 df-1st 7494 df-2nd 7495 df-supp 7627 df-tpos 7688 df-wrecs 7743 df-recs 7805 df-rdg 7843 df-1o 7897 df-2o 7898 df-oadd 7901 df-omul 7902 df-er 8081 df-ec 8083 df-qs 8087 df-map 8200 df-pm 8201 df-ixp 8252 df-en 8299 df-dom 8300 df-sdom 8301 df-fin 8302 df-fsupp 8621 df-fi 8662 df-sup 8693 df-inf 8694 df-oi 8761 df-dju 9116 df-card 9154 df-acn 9157 df-cda 9380 df-pnf 10468 df-mnf 10469 df-xr 10470 df-ltxr 10471 df-le 10472 df-sub 10664 df-neg 10665 df-div 11091 df-nn 11432 df-2 11496 df-3 11497 df-4 11498 df-5 11499 df-6 11500 df-7 11501 df-8 11502 df-9 11503 df-n0 11701 df-xnn0 11773 df-z 11787 df-dec 11905 df-uz 12052 df-q 12156 df-rp 12198 df-xneg 12317 df-xadd 12318 df-xmul 12319 df-ioo 12551 df-ioc 12552 df-ico 12553 df-icc 12554 df-fz 12702 df-fzo 12843 df-fl 12970 df-mod 13046 df-seq 13178 df-exp 13238 df-fac 13442 df-bc 13471 df-hash 13499 df-word 13663 df-concat 13724 df-s1 13749 df-shft 14277 df-cj 14309 df-re 14310 df-im 14311 df-sqrt 14445 df-abs 14446 df-limsup 14679 df-clim 14696 df-rlim 14697 df-o1 14698 df-lo1 14699 df-sum 14894 df-ef 15271 df-e 15272 df-sin 15273 df-cos 15274 df-tan 15275 df-pi 15276 df-dvds 15458 df-gcd 15694 df-prm 15862 df-numer 15921 df-denom 15922 df-phi 15949 df-pc 16020 df-struct 16331 df-ndx 16332 df-slot 16333 df-base 16335 df-sets 16336 df-ress 16337 df-plusg 16424 df-mulr 16425 df-starv 16426 df-sca 16427 df-vsca 16428 df-ip 16429 df-tset 16430 df-ple 16431 df-ds 16433 df-unif 16434 df-hom 16435 df-cco 16436 df-rest 16542 df-topn 16543 df-0g 16561 df-gsum 16562 df-topgen 16563 df-pt 16564 df-prds 16567 df-xrs 16621 df-qtop 16626 df-imas 16627 df-qus 16628 df-xps 16629 df-mre 16705 df-mrc 16706 df-acs 16708 df-mgm 17700 df-sgrp 17742 df-mnd 17753 df-mhm 17793 df-submnd 17794 df-grp 17884 df-minusg 17885 df-sbg 17886 df-mulg 18002 df-subg 18050 df-nsg 18051 df-eqg 18052 df-ghm 18117 df-gim 18160 df-ga 18181 df-cntz 18208 df-oppg 18235 df-od 18408 df-gex 18409 df-pgp 18410 df-lsm 18512 df-pj1 18513 df-cmn 18658 df-abl 18659 df-cyg 18743 df-dprd 18857 df-dpj 18858 df-mgp 18953 df-ur 18965 df-ring 19012 df-cring 19013 df-oppr 19086 df-dvdsr 19104 df-unit 19105 df-invr 19135 df-dvr 19146 df-rnghom 19180 df-drng 19217 df-subrg 19246 df-lmod 19348 df-lss 19416 df-lsp 19456 df-sra 19656 df-rgmod 19657 df-lidl 19658 df-rsp 19659 df-2idl 19716 df-psmet 20229 df-xmet 20230 df-met 20231 df-bl 20232 df-mopn 20233 df-fbas 20234 df-fg 20235 df-cnfld 20238 df-zring 20310 df-zrh 20343 df-zn 20346 df-top 21196 df-topon 21213 df-topsp 21235 df-bases 21248 df-cld 21321 df-ntr 21322 df-cls 21323 df-nei 21400 df-lp 21438 df-perf 21439 df-cn 21529 df-cnp 21530 df-haus 21617 df-cmp 21689 df-tx 21864 df-hmeo 22057 df-fil 22148 df-fm 22240 df-flim 22241 df-flf 22242 df-xms 22623 df-ms 22624 df-tms 22625 df-cncf 23179 df-0p 23964 df-limc 24157 df-dv 24158 df-ply 24471 df-idp 24472 df-coe 24473 df-dgr 24474 df-quot 24573 df-ulm 24658 df-log 24831 df-cxp 24832 df-atan 25136 df-em 25262 df-cht 25366 df-vma 25367 df-chp 25368 df-ppi 25369 df-mu 25370 df-dchr 25501 |
This theorem is referenced by: (None) |
Copyright terms: Public domain | W3C validator |