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 27861

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 1154	. . . . . . . 8 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → 𝑁 ∈ ℕ)
2	1	nnnn0d 12670	. . . . . . 7 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → 𝑁 ∈ ℕ₀)
3	2	adantr 486	. . . . . 6 ⊢ (((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) ∧ 𝑝 ∈ ℙ) → 𝑁 ∈ ℕ₀)
4		eqid 2760	. . . . . . 7 ⊢ (ℤ/nℤ‘𝑁) = (ℤ/nℤ‘𝑁)
5		eqid 2760	. . . . . . 7 ⊢ (Base‘(ℤ/nℤ‘𝑁)) = (Base‘(ℤ/nℤ‘𝑁))
6		eqid 2760	. . . . . . 7 ⊢ (ℤRHom‘(ℤ/nℤ‘𝑁)) = (ℤRHom‘(ℤ/nℤ‘𝑁))
7	4, 5, 6	znzrhfo 21858	. . . . . 6 ⊢ (𝑁 ∈ ℕ₀ → (ℤRHom‘(ℤ/nℤ‘𝑁)):ℤ–onto→(Base‘(ℤ/nℤ‘𝑁)))
8		fofn 6798	. . . . . 6 ⊢ ((ℤRHom‘(ℤ/nℤ‘𝑁)):ℤ–onto→(Base‘(ℤ/nℤ‘𝑁)) → (ℤRHom‘(ℤ/nℤ‘𝑁)) Fn ℤ)
9	3, 7, 8	3syl 19	. . . . 5 ⊢ (((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) ∧ 𝑝 ∈ ℙ) → (ℤRHom‘(ℤ/nℤ‘𝑁)) Fn ℤ)
10		prmz 16855	. . . . . 6 ⊢ (𝑝 ∈ ℙ → 𝑝 ∈ ℤ)
11	10	adantl 487	. . . . 5 ⊢ (((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) ∧ 𝑝 ∈ ℙ) → 𝑝 ∈ ℤ)
12		fniniseg 7059	. . . . . 6 ⊢ ((ℤRHom‘(ℤ/nℤ‘𝑁)) Fn ℤ → (𝑝 ∈ (^◡(ℤRHom‘(ℤ/nℤ‘𝑁)) “ {((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)}) ↔ (𝑝 ∈ ℤ ∧ ((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝑝) = ((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴))))
13	12	baibd 549	. . . . 5 ⊢ (((ℤRHom‘(ℤ/nℤ‘𝑁)) Fn ℤ ∧ 𝑝 ∈ ℤ) → (𝑝 ∈ (^◡(ℤRHom‘(ℤ/nℤ‘𝑁)) “ {((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)}) ↔ ((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝑝) = ((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)))
14	9, 11, 13	syl2anc 596	. . . 4 ⊢ (((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) ∧ 𝑝 ∈ ℙ) → (𝑝 ∈ (^◡(ℤRHom‘(ℤ/nℤ‘𝑁)) “ {((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)}) ↔ ((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝑝) = ((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)))
15		simp2 1155	. . . . . 6 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → 𝐴 ∈ ℤ)
16	15	adantr 486	. . . . 5 ⊢ (((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) ∧ 𝑝 ∈ ℙ) → 𝐴 ∈ ℤ)
17	4, 6	zndvds 21860	. . . . 5 ⊢ ((𝑁 ∈ ℕ₀ ∧ 𝑝 ∈ ℤ ∧ 𝐴 ∈ ℤ) → (((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝑝) = ((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴) ↔ 𝑁 ∥ (𝑝 − 𝐴)))
18	3, 11, 16, 17	syl3anc 1398	. . . 4 ⊢ (((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) ∧ 𝑝 ∈ ℙ) → (((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝑝) = ((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴) ↔ 𝑁 ∥ (𝑝 − 𝐴)))
19	14, 18	bitrd 282	. . 3 ⊢ (((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) ∧ 𝑝 ∈ ℙ) → (𝑝 ∈ (^◡(ℤRHom‘(ℤ/nℤ‘𝑁)) “ {((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)}) ↔ 𝑁 ∥ (𝑝 − 𝐴)))
20	19	rabbi2dva 4122	. 2 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → (ℙ ∩ (^◡(ℤRHom‘(ℤ/nℤ‘𝑁)) “ {((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)})) = {𝑝 ∈ ℙ ∣ 𝑁 ∥ (𝑝 − 𝐴)})
21		eqid 2760	. . 3 ⊢ (Unit‘(ℤ/nℤ‘𝑁)) = (Unit‘(ℤ/nℤ‘𝑁))
22		simp3 1156	. . . 4 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → (𝐴 gcd 𝑁) = 1)
23	4, 21, 6	znunit 21874	. . . . 5 ⊢ ((𝑁 ∈ ℕ₀ ∧ 𝐴 ∈ ℤ) → (((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴) ∈ (Unit‘(ℤ/nℤ‘𝑁)) ↔ (𝐴 gcd 𝑁) = 1))
24	2, 15, 23	syl2anc 596	. . . 4 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → (((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴) ∈ (Unit‘(ℤ/nℤ‘𝑁)) ↔ (𝐴 gcd 𝑁) = 1))
25	22, 24	mpbird 260	. . 3 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → ((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴) ∈ (Unit‘(ℤ/nℤ‘𝑁)))
26		eqid 2760	. . 3 ⊢ (^◡(ℤRHom‘(ℤ/nℤ‘𝑁)) “ {((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)}) = (^◡(ℤRHom‘(ℤ/nℤ‘𝑁)) “ {((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)})
27	4, 6, 1, 21, 25, 26	dirith2 27860	. 2 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → (ℙ ∩ (^◡(ℤRHom‘(ℤ/nℤ‘𝑁)) “ {((ℤRHom‘(ℤ/nℤ‘𝑁))‘𝐴)})) ≈ ℕ)
28	20, 27	eqbrtrrd 5128	1 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ (𝐴 gcd 𝑁) = 1) → {𝑝 ∈ ℙ ∣ 𝑁 ∥ (𝑝 − 𝐴)} ≈ ℕ)

Colors of variables: wff setvar class

This proof depends on syntax axioms: → wi 4 ↔ wb 209 ∧ wa 401 ∧ w3a 1103 = wceq 1569 ∈ wcel 2144 {crab 3412 ∩ cin 4089 {csn 4584 class class class wbr 5102 ^◡ccnv 5649 “ cima 5653 Fn wfn 6533 –onto→wfo 6536 ‘cfv 6538 (class class class)co 7420 ≈ cen 8973 1c1 11204 − cmin 11544 ℕcn 12338 ℕ₀cn0 12609 ℤcz 12696 ∥ cdvds 16427 gcd cgcd 16669 ℙcprime 16851 Basecbs 17392 Unitcui 20590 ℤRHomczrh 21810 ℤ/nℤczn 21813

This proof depends on axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1827 ax-4 1841 ax-5 1942 ax-6 1999 ax-7 2040 ax-8 2146 ax-9 2154 ax-10 2177 ax-11 2193 ax-12 2212 ax-ext 2732 ax-rep 5231 ax-sep 5248 ax-nul 5259 ax-pow 5326 ax-pr 5390 ax-un 7751 ax-inf2 9645 ax-cnex 11259 ax-resscn 11260 ax-1cn 11261 ax-icn 11262 ax-addcl 11263 ax-addrcl 11264 ax-mulcl 11265 ax-mulrcl 11266 ax-mulcom 11267 ax-addass 11268 ax-mulass 11269 ax-distr 11270 ax-i2m1 11271 ax-1ne0 11272 ax-1rid 11273 ax-rnegex 11274 ax-rrecex 11275 ax-cnre 11276 ax-pre-lttri 11277 ax-pre-lttrn 11278 ax-pre-ltadd 11279 ax-pre-mulgt0 11280 ax-pre-sup 11281 ax-addf 11282 ax-mulf 11283

This proof depends on definitions: df-bi 210 df-an 402 df-or 862 df-3or 1104 df-3an 1105 df-tru 1572 df-fal 1582 df-ex 1812 df-nf 1816 df-sb 2099 df-mo 2564 df-eu 2594 df-clab 2739 df-cleq 2752 df-clel 2835 df-nfc 2909 df-ne 2956 df-nel 3062 df-ral 3077 df-rex 3087 df-rmo 3365 df-reu 3366 df-rab 3413 df-v 3452 df-sbc 3739 df-csb 3847 df-ss 3896 df-pss 4014 df-dif 4047 df-in 4091 df-un 4151 df-nul 4279 df-if 4482 df-pw 4558 df-sn 4585 df-pr 4587 df-tp 4589 df-op 4835 df-uni 4867 df-int 4907 df-iun 4952 df-iin 4953 df-disj 5070 df-br 5103 df-opab 5167 df-mpt 5186 df-tr 5212 df-id 5545 df-eprel 5550 df-po 5558 df-so 5559 df-fr 5603 df-se 5604 df-we 5605 df-xp 5656 df-rel 5657 df-cnv 5658 df-co 5659 df-dm 5660 df-rn 5661 df-res 5662 df-ima 5663 df-pred 6304 df-ord 6365 df-on 6366 df-lim 6367 df-suc 6368 df-iota 6494 df-fun 6540 df-fn 6541 df-f 6542 df-f1 6543 df-fo 6544 df-f1o 6545 df-fv 6546 df-isom 6547 df-riota 7377 df-ov 7423 df-oprab 7424 df-mpo 7425 df-of 7693 df-rpss 7739 df-om 7878 df-1st 8001 df-2nd 8002 df-supp 8180 df-tpos 8246 df-frecs 8302 df-wrecs 8333 df-recs 8382 df-rdg 8421 df-1o 8479 df-2o 8480 df-oadd 8483 df-omul 8484 df-er 8720 df-ec 8722 df-qs 8726 df-map 8852 df-pm 8853 df-ixp 8929 df-en 8977 df-dom 8978 df-sdom 8979 df-fin 8980 df-fsupp 9357 df-fi 9406 df-sup 9437 df-inf 9438 df-oi 9507 df-dju 9985 df-card 10023 df-acn 10026 df-pnf 11348 df-mnf 11349 df-xr 11350 df-ltxr 11351 df-le 11352 df-sub 11546 df-neg 11547 df-div 11977 df-nn 12339 df-2 12408 df-3 12409 df-4 12410 df-5 12411 df-6 12412 df-7 12413 df-8 12414 df-9 12415 df-n0 12610 df-xnn0 12683 df-z 12697 df-dec 12818 df-uz 12969 df-q 13079 df-rp 13124 df-xneg 13244 df-xadd 13245 df-xmul 13246 df-ioo 13483 df-ioc 13484 df-ico 13485 df-icc 13486 df-fz 13643 df-fzo 13792 df-fl 13935 df-mod 14013 df-seq 14148 df-exp 14208 df-fac 14421 df-bc 14450 df-hash 14478 df-word 14662 df-concat 14719 df-s1 14746 df-shft 15225 df-cj 15271 df-re 15272 df-im 15273 df-sqrt 15407 df-abs 15408 df-limsup 15643 df-clim 15660 df-rlim 15661 df-o1 15662 df-lo1 15663 df-sum 15859 df-ef 16238 df-e 16239 df-sin 16240 df-cos 16241 df-tan 16242 df-pi 16243 df-dvds 16428 df-gcd 16670 df-prm 16852 df-numer 16916 df-denom 16917 df-phi 16948 df-pc 17020 df-struct 17330 df-sets 17347 df-slot 17365 df-ndx 17377 df-base 17393 df-ress 17414 df-plusg 17446 df-mulr 17447 df-starv 17448 df-sca 17449 df-vsca 17450 df-ip 17451 df-tset 17452 df-ple 17453 df-ds 17455 df-unif 17456 df-hom 17457 df-cco 17458 df-rest 17598 df-topn 17599 df-0g 17617 df-gsum 17618 df-topgen 17619 df-pt 17620 df-prds 17623 df-xrs 17679 df-qtop 17684 df-imas 17685 df-qus 17686 df-xps 17687 df-mre 17761 df-mrc 17762 df-acs 17764 df-mgm 18821 df-sgrp 18913 df-mnd 18929 df-mhm 18983 df-submnd 18984 df-grp 19152 df-minusg 19153 df-sbg 19154 df-mulg 19283 df-subg 19338 df-nsg 19339 df-eqg 19340 df-ghm 19433 df-gim 19478 df-ga 19509 df-cntz 19536 df-oppg 19565 df-od 19747 df-gex 19748 df-pgp 19749 df-lsm 19855 df-pj1 19856 df-cmn 20001 df-abl 20002 df-cyg 20097 df-dprd 20216 df-dpj 20217 df-mgp 20366 df-rng 20380 df-ur 20413 df-ring 20466 df-cring 20467 df-oppr 20572 df-dvdsr 20592 df-unit 20593 df-invr 20623 df-dvr 20636 df-rhm 20707 df-subrng 20803 df-subrg 20827 df-drng 20987 df-lmod 21142 df-lss 21212 df-lsp 21252 df-sra 21453 df-rgmod 21454 df-lidl 21491 df-rsp 21492 df-2idl 21548 df-psmet 21675 df-xmet 21676 df-met 21677 df-bl 21678 df-mopn 21679 df-fbas 21680 df-fg 21681 df-cnfld 21684 df-zring 21758 df-zrh 21814 df-zn 21817 df-top 23217 df-topon 23234 df-topsp 23256 df-bases 23269 df-cld 23342 df-ntr 23343 df-cls 23344 df-nei 23421 df-lp 23459 df-perf 23460 df-cn 23550 df-cnp 23551 df-haus 23638 df-cmp 23710 df-tx 23886 df-hmeo 24079 df-fil 24170 df-fm 24262 df-flim 24263 df-flf 24264 df-xms 24644 df-ms 24645 df-tms 24646 df-cncf 25204 df-0p 25996 df-limc 26191 df-dv 26192 df-ply 26511 df-idp 26512 df-coe 26513 df-dgr 26514 df-quot 26617 df-ulm 26709 df-log 26889 df-cxp 26890 df-atan 27200 df-em 27325 df-cht 27429 df-vma 27430 df-chp 27431 df-ppi 27432 df-mu 27433 df-dchr 27565

This theorem is used by: (None)

W3C validator