dirith - Metamath Proof Explorer

	Metamath Proof Explorer		< Previous Next > Nearby theorems
Mirrors > Home > MPE Home > Th. List > dirith		Structured version Visualization version GIF version

Theorem dirith 26748

Description: Dirichlet's theorem: there are infinitely many primes in any arithmetic progression coprime to 𝑁. Theorem 9.4.1 of [Shapiro], p. 375. See https://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.)

**Assertion**
Ref	Expression
dirith	⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → {𝑝 ∈ ℙ ∣ 𝑁 ∥ (𝑝 − 𝐴)} ≈ ℕ)

Distinct variable groups: 𝐴,𝑝 𝑁,𝑝

**Proof of Theorem dirith**
Step	Hyp	Ref	Expression
1		simp1 1135	. . . . . . . 8 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → 𝑁 ∈ ℕ)
2	1	nnnn0d 12363	. . . . . . 7 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → 𝑁 ∈ ℕ₀)
3	2	adantr 481	. . . . . 6 ⊢ (((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) ∧ 𝑝 ∈ ℙ) → 𝑁 ∈ ℕ₀)
4		eqid 2737	. . . . . . 7 ⊢ (ℤ/nℤ‘𝑁) = (ℤ/nℤ‘𝑁)
5		eqid 2737	. . . . . . 7 ⊢ (Base‘(ℤ/nℤ‘𝑁)) = (Base‘(ℤ/nℤ‘𝑁))
6		eqid 2737	. . . . . . 7 ⊢ (ℤRHom‘(ℤ/nℤ‘𝑁)) = (ℤRHom‘(ℤ/nℤ‘𝑁))
7	4, 5, 6	znzrhfo 20826	. . . . . 6 ⊢ (𝑁 ∈ ℕ₀ → (ℤRHom‘(ℤ/nℤ‘𝑁)):ℤ–onto→(Base‘(ℤ/nℤ‘𝑁)))
8		fofn 6725	. . . . . 6 ⊢ ((ℤRHom‘(ℤ/nℤ‘𝑁)):ℤ–onto→(Base‘(ℤ/nℤ‘𝑁)) → (ℤRHom‘(ℤ/nℤ‘𝑁)) Fn ℤ)
9	3, 7, 8	3syl 18	. . . . 5 ⊢ (((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) ∧ 𝑝 ∈ ℙ) → (ℤRHom‘(ℤ/nℤ‘𝑁)) Fn ℤ)
10		prmz 16447	. . . . . 6 ⊢ (𝑝 ∈ ℙ → 𝑝 ∈ ℤ)
11	10	adantl 482	. . . . 5 ⊢ (((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) ∧ 𝑝 ∈ ℙ) → 𝑝 ∈ ℤ)
12		fniniseg 6974	. . . . . 6 ⊢ ((ℤRHom‘(ℤ/nℤ‘𝑁)) Fn ℤ → (𝑝 ∈ (^◡(ℤRHom‘(ℤ/nℤ‘𝑁)) “ {((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)}) ↔ (𝑝 ∈ ℤ ∧ ((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝑝) = ((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴))))
13	12	baibd 540	. . . . 5 ⊢ (((ℤRHom‘(ℤ/nℤ‘𝑁)) Fn ℤ ∧ 𝑝 ∈ ℤ) → (𝑝 ∈ (^◡(ℤRHom‘(ℤ/nℤ‘𝑁)) “ {((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)}) ↔ ((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝑝) = ((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)))
14	9, 11, 13	syl2anc 584	. . . 4 ⊢ (((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) ∧ 𝑝 ∈ ℙ) → (𝑝 ∈ (^◡(ℤRHom‘(ℤ/nℤ‘𝑁)) “ {((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)}) ↔ ((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝑝) = ((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)))
15		simp2 1136	. . . . . 6 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → 𝐴 ∈ ℤ)
16	15	adantr 481	. . . . 5 ⊢ (((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) ∧ 𝑝 ∈ ℙ) → 𝐴 ∈ ℤ)
17	4, 6	zndvds 20828	. . . . 5 ⊢ ((𝑁 ∈ ℕ₀ ∧ 𝑝 ∈ ℤ ∧ 𝐴 ∈ ℤ) → (((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝑝) = ((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴) ↔ 𝑁 ∥ (𝑝 − 𝐴)))
18	3, 11, 16, 17	syl3anc 1370	. . . 4 ⊢ (((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) ∧ 𝑝 ∈ ℙ) → (((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝑝) = ((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴) ↔ 𝑁 ∥ (𝑝 − 𝐴)))
19	14, 18	bitrd 278	. . 3 ⊢ (((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) ∧ 𝑝 ∈ ℙ) → (𝑝 ∈ (^◡(ℤRHom‘(ℤ/nℤ‘𝑁)) “ {((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)}) ↔ 𝑁 ∥ (𝑝 − 𝐴)))
20	19	rabbi2dva 4161	. 2 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → (ℙ ∩ (^◡(ℤRHom‘(ℤ/nℤ‘𝑁)) “ {((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)})) = {𝑝 ∈ ℙ ∣ 𝑁 ∥ (𝑝 − 𝐴)})
21		eqid 2737	. . 3 ⊢ (Unit‘(ℤ/nℤ‘𝑁)) = (Unit‘(ℤ/nℤ‘𝑁))
22		simp3 1137	. . . 4 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → (𝐴 gcd 𝑁) = 1)
23	4, 21, 6	znunit 20842	. . . . 5 ⊢ ((𝑁 ∈ ℕ₀ ∧ 𝐴 ∈ ℤ) → (((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴) ∈ (Unit‘(ℤ/nℤ‘𝑁)) ↔ (𝐴 gcd 𝑁) = 1))
24	2, 15, 23	syl2anc 584	. . . 4 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → (((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴) ∈ (Unit‘(ℤ/nℤ‘𝑁)) ↔ (𝐴 gcd 𝑁) = 1))
25	22, 24	mpbird 256	. . 3 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → ((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴) ∈ (Unit‘(ℤ/nℤ‘𝑁)))
26		eqid 2737	. . 3 ⊢ (^◡(ℤRHom‘(ℤ/nℤ‘𝑁)) “ {((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)}) = (^◡(ℤRHom‘(ℤ/nℤ‘𝑁)) “ {((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)})
27	4, 6, 1, 21, 25, 26	dirith2 26747	. 2 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → (ℙ ∩ (^◡(ℤRHom‘(ℤ/nℤ‘𝑁)) “ {((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)})) ≈ ℕ)
28	20, 27	eqbrtrrd 5109	1 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → {𝑝 ∈ ℙ ∣ 𝑁 ∥ (𝑝 − 𝐴)} ≈ ℕ)

Colors of variables: wff setvar class

Syntax hints: → wi 4 ↔ wb 205 ∧ wa 396 ∧ w3a 1086 = wceq 1540 ∈ wcel 2105 {crab 3404 ∩ cin 3895 {csn 4569 class class class wbr 5085 ^◡ccnv 5604 “ cima 5608 Fn wfn 6458 –onto→wfo 6461 ‘cfv 6463 (class class class)co 7313 ≈ cen 8776 1c1 10942 − cmin 11275 ℕcn 12043 ℕ₀cn0 12303 ℤcz 12389 ∥ cdvds 16032 gcd cgcd 16270 ℙcprime 16443 Basecbs 16979 Unitcui 19948 ℤRHomczrh 20772 ℤ/nℤczn 20775

This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1796 ax-4 1810 ax-5 1912 ax-6 1970 ax-7 2010 ax-8 2107 ax-9 2115 ax-10 2136 ax-11 2153 ax-12 2170 ax-ext 2708 ax-rep 5222 ax-sep 5236 ax-nul 5243 ax-pow 5301 ax-pr 5365 ax-un 7626 ax-inf2 9467 ax-cnex 10997 ax-resscn 10998 ax-1cn 10999 ax-icn 11000 ax-addcl 11001 ax-addrcl 11002 ax-mulcl 11003 ax-mulrcl 11004 ax-mulcom 11005 ax-addass 11006 ax-mulass 11007 ax-distr 11008 ax-i2m1 11009 ax-1ne0 11010 ax-1rid 11011 ax-rnegex 11012 ax-rrecex 11013 ax-cnre 11014 ax-pre-lttri 11015 ax-pre-lttrn 11016 ax-pre-ltadd 11017 ax-pre-mulgt0 11018 ax-pre-sup 11019 ax-addf 11020 ax-mulf 11021

This theorem depends on definitions: df-bi 206 df-an 397 df-or 845 df-3or 1087 df-3an 1088 df-tru 1543 df-fal 1553 df-ex 1781 df-nf 1785 df-sb 2067 df-mo 2539 df-eu 2568 df-clab 2715 df-cleq 2729 df-clel 2815 df-nfc 2887 df-ne 2942 df-nel 3048 df-ral 3063 df-rex 3072 df-rmo 3350 df-reu 3351 df-rab 3405 df-v 3443 df-sbc 3726 df-csb 3842 df-dif 3899 df-un 3901 df-in 3903 df-ss 3913 df-pss 3915 df-nul 4267 df-if 4470 df-pw 4545 df-sn 4570 df-pr 4572 df-tp 4574 df-op 4576 df-uni 4849 df-int 4891 df-iun 4937 df-iin 4938 df-disj 5051 df-br 5086 df-opab 5148 df-mpt 5169 df-tr 5203 df-id 5505 df-eprel 5511 df-po 5519 df-so 5520 df-fr 5560 df-se 5561 df-we 5562 df-xp 5611 df-rel 5612 df-cnv 5613 df-co 5614 df-dm 5615 df-rn 5616 df-res 5617 df-ima 5618 df-pred 6222 df-ord 6289 df-on 6290 df-lim 6291 df-suc 6292 df-iota 6415 df-fun 6465 df-fn 6466 df-f 6467 df-f1 6468 df-fo 6469 df-f1o 6470 df-fv 6471 df-isom 6472 df-riota 7270 df-ov 7316 df-oprab 7317 df-mpo 7318 df-of 7571 df-rpss 7614 df-om 7756 df-1st 7874 df-2nd 7875 df-supp 8023 df-tpos 8087 df-frecs 8142 df-wrecs 8173 df-recs 8247 df-rdg 8286 df-1o 8342 df-2o 8343 df-oadd 8346 df-omul 8347 df-er 8544 df-ec 8546 df-qs 8550 df-map 8663 df-pm 8664 df-ixp 8732 df-en 8780 df-dom 8781 df-sdom 8782 df-fin 8783 df-fsupp 9197 df-fi 9238 df-sup 9269 df-inf 9270 df-oi 9337 df-dju 9727 df-card 9765 df-acn 9768 df-pnf 11081 df-mnf 11082 df-xr 11083 df-ltxr 11084 df-le 11085 df-sub 11277 df-neg 11278 df-div 11703 df-nn 12044 df-2 12106 df-3 12107 df-4 12108 df-5 12109 df-6 12110 df-7 12111 df-8 12112 df-9 12113 df-n0 12304 df-xnn0 12376 df-z 12390 df-dec 12508 df-uz 12653 df-q 12759 df-rp 12801 df-xneg 12918 df-xadd 12919 df-xmul 12920 df-ioo 13153 df-ioc 13154 df-ico 13155 df-icc 13156 df-fz 13310 df-fzo 13453 df-fl 13582 df-mod 13660 df-seq 13792 df-exp 13853 df-fac 14058 df-bc 14087 df-hash 14115 df-word 14287 df-concat 14343 df-s1 14370 df-shft 14847 df-cj 14879 df-re 14880 df-im 14881 df-sqrt 15015 df-abs 15016 df-limsup 15249 df-clim 15266 df-rlim 15267 df-o1 15268 df-lo1 15269 df-sum 15467 df-ef 15846 df-e 15847 df-sin 15848 df-cos 15849 df-tan 15850 df-pi 15851 df-dvds 16033 df-gcd 16271 df-prm 16444 df-numer 16506 df-denom 16507 df-phi 16534 df-pc 16605 df-struct 16915 df-sets 16932 df-slot 16950 df-ndx 16962 df-base 16980 df-ress 17009 df-plusg 17042 df-mulr 17043 df-starv 17044 df-sca 17045 df-vsca 17046 df-ip 17047 df-tset 17048 df-ple 17049 df-ds 17051 df-unif 17052 df-hom 17053 df-cco 17054 df-rest 17200 df-topn 17201 df-0g 17219 df-gsum 17220 df-topgen 17221 df-pt 17222 df-prds 17225 df-xrs 17280 df-qtop 17285 df-imas 17286 df-qus 17287 df-xps 17288 df-mre 17362 df-mrc 17363 df-acs 17365 df-mgm 18393 df-sgrp 18442 df-mnd 18453 df-mhm 18497 df-submnd 18498 df-grp 18647 df-minusg 18648 df-sbg 18649 df-mulg 18768 df-subg 18819 df-nsg 18820 df-eqg 18821 df-ghm 18899 df-gim 18942 df-ga 18963 df-cntz 18990 df-oppg 19017 df-od 19203 df-gex 19204 df-pgp 19205 df-lsm 19308 df-pj1 19309 df-cmn 19455 df-abl 19456 df-cyg 19545 df-dprd 19665 df-dpj 19666 df-mgp 19788 df-ur 19805 df-ring 19852 df-cring 19853 df-oppr 19929 df-dvdsr 19950 df-unit 19951 df-invr 19981 df-dvr 19992 df-rnghom 20026 df-drng 20064 df-subrg 20093 df-lmod 20196 df-lss 20265 df-lsp 20305 df-sra 20505 df-rgmod 20506 df-lidl 20507 df-rsp 20508 df-2idl 20574 df-psmet 20660 df-xmet 20661 df-met 20662 df-bl 20663 df-mopn 20664 df-fbas 20665 df-fg 20666 df-cnfld 20669 df-zring 20742 df-zrh 20776 df-zn 20779 df-top 22114 df-topon 22131 df-topsp 22153 df-bases 22167 df-cld 22241 df-ntr 22242 df-cls 22243 df-nei 22320 df-lp 22358 df-perf 22359 df-cn 22449 df-cnp 22450 df-haus 22537 df-cmp 22609 df-tx 22784 df-hmeo 22977 df-fil 23068 df-fm 23160 df-flim 23161 df-flf 23162 df-xms 23544 df-ms 23545 df-tms 23546 df-cncf 24112 df-0p 24905 df-limc 25101 df-dv 25102 df-ply 25420 df-idp 25421 df-coe 25422 df-dgr 25423 df-quot 25522 df-ulm 25607 df-log 25783 df-cxp 25784 df-atan 26088 df-em 26213 df-cht 26317 df-vma 26318 df-chp 26319 df-ppi 26320 df-mu 26321 df-dchr 26452

This theorem is referenced by: (None)

W3C validator