2lgslem1 - Intuitionistic Logic Explorer

	Intuitionistic Logic Explorer		< Previous Next > Nearby theorems
Mirrors > Home > ILE Home > Th. List > 2lgslem1		GIF version

Theorem 2lgslem1 15778

Description: Lemma 1 for 2lgs 15791. (Contributed by AV, 19-Jun-2021.)

**Assertion**
Ref	Expression
2lgslem1	⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → (♯‘{𝑥 ∈ ℤ ∣ ∃𝑖 ∈ (1...((𝑃 − 1) / 2))(𝑥 = (𝑖 · 2) ∧ (𝑃 / 2) < (𝑥 mod 𝑃))}) = (((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4))))

Distinct variable group: 𝑃,𝑖,𝑥

Proof of Theorem 2lgslem1 Dummy variables 𝑓 𝑦 are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		2lgslem1a 15775	. . 3 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → {𝑥 ∈ ℤ ∣ ∃𝑖 ∈ (1...((𝑃 − 1) / 2))(𝑥 = (𝑖 · 2) ∧ (𝑃 / 2) < (𝑥 mod 𝑃))} = {𝑥 ∈ ℤ ∣ ∃𝑖 ∈ (((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))𝑥 = (𝑖 · 2)})
2	1	fveq2d 5633	. 2 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → (♯‘{𝑥 ∈ ℤ ∣ ∃𝑖 ∈ (1...((𝑃 − 1) / 2))(𝑥 = (𝑖 · 2) ∧ (𝑃 / 2) < (𝑥 mod 𝑃))}) = (♯‘{𝑥 ∈ ℤ ∣ ∃𝑖 ∈ (((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))𝑥 = (𝑖 · 2)}))
3		prmz 12641	. . . . . . . 8 ⊢ (𝑃 ∈ ℙ → 𝑃 ∈ ℤ)
4		4nn 9282	. . . . . . . 8 ⊢ 4 ∈ ℕ
5		znq 9827	. . . . . . . 8 ⊢ ((𝑃 ∈ ℤ ∧ 4 ∈ ℕ) → (𝑃 / 4) ∈ ℚ)
6	3, 4, 5	sylancl 413	. . . . . . 7 ⊢ (𝑃 ∈ ℙ → (𝑃 / 4) ∈ ℚ)
7	6	adantr 276	. . . . . 6 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → (𝑃 / 4) ∈ ℚ)
8	7	flqcld 10505	. . . . 5 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → (⌊‘(𝑃 / 4)) ∈ ℤ)
9	8	peano2zd 9580	. . . 4 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → ((⌊‘(𝑃 / 4)) + 1) ∈ ℤ)
10		nnoddn2prmb 12793	. . . . . 6 ⊢ (𝑃 ∈ (ℙ ∖ {2}) ↔ (𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃))
11		oddprm 12790	. . . . . 6 ⊢ (𝑃 ∈ (ℙ ∖ {2}) → ((𝑃 − 1) / 2) ∈ ℕ)
12	10, 11	sylbir 135	. . . . 5 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → ((𝑃 − 1) / 2) ∈ ℕ)
13	12	nnzd 9576	. . . 4 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → ((𝑃 − 1) / 2) ∈ ℤ)
14	9, 13	fzfigd 10661	. . 3 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → (((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2)) ∈ Fin)
15	14	mptexd 5870	. . . 4 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → (𝑦 ∈ (((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2)) ↦ (𝑦 · 2)) ∈ V)
16		eqid 2229	. . . . 5 ⊢ (((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2)) = (((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))
17		eqid 2229	. . . . 5 ⊢ (𝑦 ∈ (((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2)) ↦ (𝑦 · 2)) = (𝑦 ∈ (((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2)) ↦ (𝑦 · 2))
18	16, 17	2lgslem1b 15776	. . . 4 ⊢ (𝑦 ∈ (((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2)) ↦ (𝑦 · 2)):(((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))–1-1-onto→{𝑥 ∈ ℤ ∣ ∃𝑖 ∈ (((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))𝑥 = (𝑖 · 2)}
19		f1oeq1 5562	. . . . 5 ⊢ (𝑓 = (𝑦 ∈ (((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2)) ↦ (𝑦 · 2)) → (𝑓:(((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))–1-1-onto→{𝑥 ∈ ℤ ∣ ∃𝑖 ∈ (((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))𝑥 = (𝑖 · 2)} ↔ (𝑦 ∈ (((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2)) ↦ (𝑦 · 2)):(((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))–1-1-onto→{𝑥 ∈ ℤ ∣ ∃𝑖 ∈ (((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))𝑥 = (𝑖 · 2)}))
20	19	spcegv 2891	. . . 4 ⊢ ((𝑦 ∈ (((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2)) ↦ (𝑦 · 2)) ∈ V → ((𝑦 ∈ (((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2)) ↦ (𝑦 · 2)):(((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))–1-1-onto→{𝑥 ∈ ℤ ∣ ∃𝑖 ∈ (((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))𝑥 = (𝑖 · 2)} → ∃𝑓 𝑓:(((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))–1-1-onto→{𝑥 ∈ ℤ ∣ ∃𝑖 ∈ (((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))𝑥 = (𝑖 · 2)}))
21	15, 18, 20	mpisyl 1489	. . 3 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → ∃𝑓 𝑓:(((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))–1-1-onto→{𝑥 ∈ ℤ ∣ ∃𝑖 ∈ (((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))𝑥 = (𝑖 · 2)})
22		fihasheqf1oi 11017	. . . . 5 ⊢ (((((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2)) ∈ Fin ∧ 𝑓:(((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))–1-1-onto→{𝑥 ∈ ℤ ∣ ∃𝑖 ∈ (((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))𝑥 = (𝑖 · 2)}) → (♯‘(((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))) = (♯‘{𝑥 ∈ ℤ ∣ ∃𝑖 ∈ (((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))𝑥 = (𝑖 · 2)}))
23	22	ex 115	. . . 4 ⊢ ((((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2)) ∈ Fin → (𝑓:(((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))–1-1-onto→{𝑥 ∈ ℤ ∣ ∃𝑖 ∈ (((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))𝑥 = (𝑖 · 2)} → (♯‘(((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))) = (♯‘{𝑥 ∈ ℤ ∣ ∃𝑖 ∈ (((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))𝑥 = (𝑖 · 2)})))
24	23	exlimdv 1865	. . 3 ⊢ ((((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2)) ∈ Fin → (∃𝑓 𝑓:(((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))–1-1-onto→{𝑥 ∈ ℤ ∣ ∃𝑖 ∈ (((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))𝑥 = (𝑖 · 2)} → (♯‘(((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))) = (♯‘{𝑥 ∈ ℤ ∣ ∃𝑖 ∈ (((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))𝑥 = (𝑖 · 2)})))
25	14, 21, 24	sylc 62	. 2 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → (♯‘(((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))) = (♯‘{𝑥 ∈ ℤ ∣ ∃𝑖 ∈ (((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))𝑥 = (𝑖 · 2)}))
26	6	flqcld 10505	. . . . 5 ⊢ (𝑃 ∈ ℙ → (⌊‘(𝑃 / 4)) ∈ ℤ)
27	26	adantr 276	. . . 4 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → (⌊‘(𝑃 / 4)) ∈ ℤ)
28		oddm1d2 12411	. . . . . 6 ⊢ (𝑃 ∈ ℤ → (¬ 2 ∥ 𝑃 ↔ ((𝑃 − 1) / 2) ∈ ℤ))
29	3, 28	syl 14	. . . . 5 ⊢ (𝑃 ∈ ℙ → (¬ 2 ∥ 𝑃 ↔ ((𝑃 − 1) / 2) ∈ ℤ))
30	29	biimpa 296	. . . 4 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → ((𝑃 − 1) / 2) ∈ ℤ)
31		2lgslem1c 15777	. . . 4 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → (⌊‘(𝑃 / 4)) ≤ ((𝑃 − 1) / 2))
32		eluz2 9736	. . . 4 ⊢ (((𝑃 − 1) / 2) ∈ (ℤ_≥‘(⌊‘(𝑃 / 4))) ↔ ((⌊‘(𝑃 / 4)) ∈ ℤ ∧ ((𝑃 − 1) / 2) ∈ ℤ ∧ (⌊‘(𝑃 / 4)) ≤ ((𝑃 − 1) / 2)))
33	27, 30, 31, 32	syl3anbrc 1205	. . 3 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → ((𝑃 − 1) / 2) ∈ (ℤ_≥‘(⌊‘(𝑃 / 4))))
34		hashfzp1 11054	. . 3 ⊢ (((𝑃 − 1) / 2) ∈ (ℤ_≥‘(⌊‘(𝑃 / 4))) → (♯‘(((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))) = (((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4))))
35	33, 34	syl 14	. 2 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → (♯‘(((⌊‘(𝑃 / 4)) + 1)...((𝑃 − 1) / 2))) = (((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4))))
36	2, 25, 35	3eqtr2d 2268	1 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → (♯‘{𝑥 ∈ ℤ ∣ ∃𝑖 ∈ (1...((𝑃 − 1) / 2))(𝑥 = (𝑖 · 2) ∧ (𝑃 / 2) < (𝑥 mod 𝑃))}) = (((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4))))

Colors of variables: wff set class

Syntax hints: ¬ wn 3 → wi 4 ∧ wa 104 ↔ wb 105 = wceq 1395 ∃wex 1538 ∈ wcel 2200 ∃wrex 2509 {crab 2512 Vcvv 2799 ∖ cdif 3194 {csn 3666 class class class wbr 4083 ↦ cmpt 4145 –1-1-onto→wf1o 5317 ‘cfv 5318 (class class class)co 6007 Fincfn 6895 1c1 8008 + caddc 8010 · cmul 8012 < clt 8189 ≤ cle 8190 − cmin 8325 / cdiv 8827 ℕcn 9118 2c2 9169 4c4 9171 ℤcz 9454 ℤ_≥cuz 9730 ℚcq 9822 ...cfz 10212 ⌊cfl 10496 mod cmo 10552 ♯chash 11005 ∥ cdvds 12306 ℙcprime 12637

This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-ia1 106 ax-ia2 107 ax-ia3 108 ax-in1 617 ax-in2 618 ax-io 714 ax-5 1493 ax-7 1494 ax-gen 1495 ax-ie1 1539 ax-ie2 1540 ax-8 1550 ax-10 1551 ax-11 1552 ax-i12 1553 ax-bndl 1555 ax-4 1556 ax-17 1572 ax-i9 1576 ax-ial 1580 ax-i5r 1581 ax-13 2202 ax-14 2203 ax-ext 2211 ax-coll 4199 ax-sep 4202 ax-nul 4210 ax-pow 4258 ax-pr 4293 ax-un 4524 ax-setind 4629 ax-iinf 4680 ax-cnex 8098 ax-resscn 8099 ax-1cn 8100 ax-1re 8101 ax-icn 8102 ax-addcl 8103 ax-addrcl 8104 ax-mulcl 8105 ax-mulrcl 8106 ax-addcom 8107 ax-mulcom 8108 ax-addass 8109 ax-mulass 8110 ax-distr 8111 ax-i2m1 8112 ax-0lt1 8113 ax-1rid 8114 ax-0id 8115 ax-rnegex 8116 ax-precex 8117 ax-cnre 8118 ax-pre-ltirr 8119 ax-pre-ltwlin 8120 ax-pre-lttrn 8121 ax-pre-apti 8122 ax-pre-ltadd 8123 ax-pre-mulgt0 8124 ax-pre-mulext 8125 ax-arch 8126 ax-caucvg 8127

This theorem depends on definitions: df-bi 117 df-dc 840 df-3or 1003 df-3an 1004 df-tru 1398 df-fal 1401 df-xor 1418 df-nf 1507 df-sb 1809 df-eu 2080 df-mo 2081 df-clab 2216 df-cleq 2222 df-clel 2225 df-nfc 2361 df-ne 2401 df-nel 2496 df-ral 2513 df-rex 2514 df-reu 2515 df-rmo 2516 df-rab 2517 df-v 2801 df-sbc 3029 df-csb 3125 df-dif 3199 df-un 3201 df-in 3203 df-ss 3210 df-nul 3492 df-if 3603 df-pw 3651 df-sn 3672 df-pr 3673 df-op 3675 df-uni 3889 df-int 3924 df-iun 3967 df-br 4084 df-opab 4146 df-mpt 4147 df-tr 4183 df-id 4384 df-po 4387 df-iso 4388 df-iord 4457 df-on 4459 df-ilim 4460 df-suc 4462 df-iom 4683 df-xp 4725 df-rel 4726 df-cnv 4727 df-co 4728 df-dm 4729 df-rn 4730 df-res 4731 df-ima 4732 df-iota 5278 df-fun 5320 df-fn 5321 df-f 5322 df-f1 5323 df-fo 5324 df-f1o 5325 df-fv 5326 df-riota 5960 df-ov 6010 df-oprab 6011 df-mpo 6012 df-1st 6292 df-2nd 6293 df-recs 6457 df-frec 6543 df-1o 6568 df-2o 6569 df-er 6688 df-en 6896 df-dom 6897 df-fin 6898 df-pnf 8191 df-mnf 8192 df-xr 8193 df-ltxr 8194 df-le 8195 df-sub 8327 df-neg 8328 df-reap 8730 df-ap 8737 df-div 8828 df-inn 9119 df-2 9177 df-3 9178 df-4 9179 df-n0 9378 df-z 9455 df-uz 9731 df-q 9823 df-rp 9858 df-fz 10213 df-fl 10498 df-mod 10553 df-seqfrec 10678 df-exp 10769 df-ihash 11006 df-cj 11361 df-re 11362 df-im 11363 df-rsqrt 11517 df-abs 11518 df-dvds 12307 df-prm 12638

This theorem is referenced by: 2lgs 15791

W3C validator