perfectlem1 - Intuitionistic Logic Explorer

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

Theorem perfectlem1 16311

Description: Lemma for perfect 16313. (Contributed by Mario Carneiro, 7-Jun-2016.)

**Hypotheses**
Ref	Expression
perfectlem.1	⊢ (𝜑 → 𝐴 ∈ ℕ)
perfectlem.2	⊢ (𝜑 → 𝐵 ∈ ℕ)
perfectlem.3	⊢ (𝜑 → ¬ 2 ∥ 𝐵)
perfectlem.4	⊢ (𝜑 → (1 σ ((2↑𝐴) · 𝐵)) = (2 · ((2↑𝐴) · 𝐵)))

**Assertion**
Ref	Expression
perfectlem1	⊢ (𝜑 → ((2↑(𝐴 + 1)) ∈ ℕ ∧ ((2↑(𝐴 + 1)) − 1) ∈ ℕ ∧ (𝐵 / ((2↑(𝐴 + 1)) − 1)) ∈ ℕ))

**Proof of Theorem perfectlem1**
Step	Hyp	Ref	Expression
1		2nn 9478	. . 3 ⊢ 2 ∈ ℕ
2		perfectlem.1	. . . . 5 ⊢ (𝜑 → 𝐴 ∈ ℕ)
3	2	nnnn0d 9632	. . . 4 ⊢ (𝜑 → 𝐴 ∈ ℕ₀)
4		peano2nn0 9615	. . . 4 ⊢ (𝐴 ∈ ℕ₀ → (𝐴 + 1) ∈ ℕ₀)
5	3, 4	syl 14	. . 3 ⊢ (𝜑 → (𝐴 + 1) ∈ ℕ₀)
6		nnexpcl 11011	. . 3 ⊢ ((2 ∈ ℕ ∧ (𝐴 + 1) ∈ ℕ₀) → (2↑(𝐴 + 1)) ∈ ℕ)
7	1, 5, 6	sylancr 418	. 2 ⊢ (𝜑 → (2↑(𝐴 + 1)) ∈ ℕ)
8		2re 9384	. . . 4 ⊢ 2 ∈ ℝ
9	2	peano2nnd 9329	. . . 4 ⊢ (𝜑 → (𝐴 + 1) ∈ ℕ)
10		1lt2 9486	. . . . 5 ⊢ 1 < 2
11	10	a1i 9	. . . 4 ⊢ (𝜑 → 1 < 2)
12		expgt1 11036	. . . 4 ⊢ ((2 ∈ ℝ ∧ (𝐴 + 1) ∈ ℕ ∧ 1 < 2) → 1 < (2↑(𝐴 + 1)))
13	8, 9, 11, 12	mp3an2i 1383	. . 3 ⊢ (𝜑 → 1 < (2↑(𝐴 + 1)))
14		1nn 9325	. . . 4 ⊢ 1 ∈ ℕ
15		nnsub 9353	. . . 4 ⊢ ((1 ∈ ℕ ∧ (2↑(𝐴 + 1)) ∈ ℕ) → (1 < (2↑(𝐴 + 1)) ↔ ((2↑(𝐴 + 1)) − 1) ∈ ℕ))
16	14, 7, 15	sylancr 418	. . 3 ⊢ (𝜑 → (1 < (2↑(𝐴 + 1)) ↔ ((2↑(𝐴 + 1)) − 1) ∈ ℕ))
17	13, 16	mpbid 147	. 2 ⊢ (𝜑 → ((2↑(𝐴 + 1)) − 1) ∈ ℕ)
18	7	nnzd 9779	. . . . . . 7 ⊢ (𝜑 → (2↑(𝐴 + 1)) ∈ ℤ)
19		peano2zm 9694	. . . . . . 7 ⊢ ((2↑(𝐴 + 1)) ∈ ℤ → ((2↑(𝐴 + 1)) − 1) ∈ ℤ)
20	18, 19	syl 14	. . . . . 6 ⊢ (𝜑 → ((2↑(𝐴 + 1)) − 1) ∈ ℤ)
21		1nn0 9591	. . . . . . . 8 ⊢ 1 ∈ ℕ₀
22		perfectlem.2	. . . . . . . 8 ⊢ (𝜑 → 𝐵 ∈ ℕ)
23		sgmnncl 16269	. . . . . . . 8 ⊢ ((1 ∈ ℕ₀ ∧ 𝐵 ∈ ℕ) → (1 σ 𝐵) ∈ ℕ)
24	21, 22, 23	sylancr 418	. . . . . . 7 ⊢ (𝜑 → (1 σ 𝐵) ∈ ℕ)
25	24	nnzd 9779	. . . . . 6 ⊢ (𝜑 → (1 σ 𝐵) ∈ ℤ)
26		dvdsmul1 12606	. . . . . 6 ⊢ ((((2↑(𝐴 + 1)) − 1) ∈ ℤ ∧ (1 σ 𝐵) ∈ ℤ) → ((2↑(𝐴 + 1)) − 1) ∥ (((2↑(𝐴 + 1)) − 1) · (1 σ 𝐵)))
27	20, 25, 26	syl2anc 415	. . . . 5 ⊢ (𝜑 → ((2↑(𝐴 + 1)) − 1) ∥ (((2↑(𝐴 + 1)) − 1) · (1 σ 𝐵)))
28		2cn 9385	. . . . . . . . 9 ⊢ 2 ∈ ℂ
29		expp1 11005	. . . . . . . . 9 ⊢ ((2 ∈ ℂ ∧ 𝐴 ∈ ℕ₀) → (2↑(𝐴 + 1)) = ((2↑𝐴) · 2))
30	28, 3, 29	sylancr 418	. . . . . . . 8 ⊢ (𝜑 → (2↑(𝐴 + 1)) = ((2↑𝐴) · 2))
31		nnexpcl 11011	. . . . . . . . . . 11 ⊢ ((2 ∈ ℕ ∧ 𝐴 ∈ ℕ₀) → (2↑𝐴) ∈ ℕ)
32	1, 3, 31	sylancr 418	. . . . . . . . . 10 ⊢ (𝜑 → (2↑𝐴) ∈ ℕ)
33	32	nncnd 9328	. . . . . . . . 9 ⊢ (𝜑 → (2↑𝐴) ∈ ℂ)
34		mulcom 8315	. . . . . . . . 9 ⊢ (((2↑𝐴) ∈ ℂ ∧ 2 ∈ ℂ) → ((2↑𝐴) · 2) = (2 · (2↑𝐴)))
35	33, 28, 34	sylancl 417	. . . . . . . 8 ⊢ (𝜑 → ((2↑𝐴) · 2) = (2 · (2↑𝐴)))
36	30, 35	eqtrd 2271	. . . . . . 7 ⊢ (𝜑 → (2↑(𝐴 + 1)) = (2 · (2↑𝐴)))
37	36	oveq1d 6103	. . . . . 6 ⊢ (𝜑 → ((2↑(𝐴 + 1)) · 𝐵) = ((2 · (2↑𝐴)) · 𝐵))
38	28	a1i 9	. . . . . . 7 ⊢ (𝜑 → 2 ∈ ℂ)
39	22	nncnd 9328	. . . . . . 7 ⊢ (𝜑 → 𝐵 ∈ ℂ)
40	38, 33, 39	mulassd 8356	. . . . . 6 ⊢ (𝜑 → ((2 · (2↑𝐴)) · 𝐵) = (2 · ((2↑𝐴) · 𝐵)))
41		ax-1cn 8279	. . . . . . . . 9 ⊢ 1 ∈ ℂ
42	41	a1i 9	. . . . . . . 8 ⊢ (𝜑 → 1 ∈ ℂ)
43		perfectlem.3	. . . . . . . . . 10 ⊢ (𝜑 → ¬ 2 ∥ 𝐵)
44		2prm 12931	. . . . . . . . . . 11 ⊢ 2 ∈ ℙ
45	22	nnzd 9779	. . . . . . . . . . 11 ⊢ (𝜑 → 𝐵 ∈ ℤ)
46		coprm 12949	. . . . . . . . . . 11 ⊢ ((2 ∈ ℙ ∧ 𝐵 ∈ ℤ) → (¬ 2 ∥ 𝐵 ↔ (2 gcd 𝐵) = 1))
47	44, 45, 46	sylancr 418	. . . . . . . . . 10 ⊢ (𝜑 → (¬ 2 ∥ 𝐵 ↔ (2 gcd 𝐵) = 1))
48	43, 47	mpbid 147	. . . . . . . . 9 ⊢ (𝜑 → (2 gcd 𝐵) = 1)
49		2z 9684	. . . . . . . . . 10 ⊢ 2 ∈ ℤ
50		rpexp1i 12959	. . . . . . . . . 10 ⊢ ((2 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐴 ∈ ℕ₀) → ((2 gcd 𝐵) = 1 → ((2↑𝐴) gcd 𝐵) = 1))
51	49, 45, 3, 50	mp3an2i 1383	. . . . . . . . 9 ⊢ (𝜑 → ((2 gcd 𝐵) = 1 → ((2↑𝐴) gcd 𝐵) = 1))
52	48, 51	mpd 13	. . . . . . . 8 ⊢ (𝜑 → ((2↑𝐴) gcd 𝐵) = 1)
53		sgmmul 16302	. . . . . . . 8 ⊢ ((1 ∈ ℂ ∧ ((2↑𝐴) ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ ((2↑𝐴) gcd 𝐵) = 1)) → (1 σ ((2↑𝐴) · 𝐵)) = ((1 σ (2↑𝐴)) · (1 σ 𝐵)))
54	42, 32, 22, 52, 53	syl13anc 1280	. . . . . . 7 ⊢ (𝜑 → (1 σ ((2↑𝐴) · 𝐵)) = ((1 σ (2↑𝐴)) · (1 σ 𝐵)))
55		perfectlem.4	. . . . . . 7 ⊢ (𝜑 → (1 σ ((2↑𝐴) · 𝐵)) = (2 · ((2↑𝐴) · 𝐵)))
56	2	nncnd 9328	. . . . . . . . . . . 12 ⊢ (𝜑 → 𝐴 ∈ ℂ)
57		pncan 8540	. . . . . . . . . . . 12 ⊢ ((𝐴 ∈ ℂ ∧ 1 ∈ ℂ) → ((𝐴 + 1) − 1) = 𝐴)
58	56, 41, 57	sylancl 417	. . . . . . . . . . 11 ⊢ (𝜑 → ((𝐴 + 1) − 1) = 𝐴)
59	58	oveq2d 6104	. . . . . . . . . 10 ⊢ (𝜑 → (2↑((𝐴 + 1) − 1)) = (2↑𝐴))
60	59	oveq2d 6104	. . . . . . . . 9 ⊢ (𝜑 → (1 σ (2↑((𝐴 + 1) − 1))) = (1 σ (2↑𝐴)))
61		1sgm2ppw 16301	. . . . . . . . . 10 ⊢ ((𝐴 + 1) ∈ ℕ → (1 σ (2↑((𝐴 + 1) − 1))) = ((2↑(𝐴 + 1)) − 1))
62	9, 61	syl 14	. . . . . . . . 9 ⊢ (𝜑 → (1 σ (2↑((𝐴 + 1) − 1))) = ((2↑(𝐴 + 1)) − 1))
63	60, 62	eqtr3d 2273	. . . . . . . 8 ⊢ (𝜑 → (1 σ (2↑𝐴)) = ((2↑(𝐴 + 1)) − 1))
64	63	oveq1d 6103	. . . . . . 7 ⊢ (𝜑 → ((1 σ (2↑𝐴)) · (1 σ 𝐵)) = (((2↑(𝐴 + 1)) − 1) · (1 σ 𝐵)))
65	54, 55, 64	3eqtr3d 2279	. . . . . 6 ⊢ (𝜑 → (2 · ((2↑𝐴) · 𝐵)) = (((2↑(𝐴 + 1)) − 1) · (1 σ 𝐵)))
66	37, 40, 65	3eqtrd 2275	. . . . 5 ⊢ (𝜑 → ((2↑(𝐴 + 1)) · 𝐵) = (((2↑(𝐴 + 1)) − 1) · (1 σ 𝐵)))
67	27, 66	breqtrrd 4159	. . . 4 ⊢ (𝜑 → ((2↑(𝐴 + 1)) − 1) ∥ ((2↑(𝐴 + 1)) · 𝐵))
68	20, 18	gcdcomd 12777	. . . . 5 ⊢ (𝜑 → (((2↑(𝐴 + 1)) − 1) gcd (2↑(𝐴 + 1))) = ((2↑(𝐴 + 1)) gcd ((2↑(𝐴 + 1)) − 1)))
69		iddvdsexp 12608	. . . . . . . . 9 ⊢ ((2 ∈ ℤ ∧ (𝐴 + 1) ∈ ℕ) → 2 ∥ (2↑(𝐴 + 1)))
70	49, 9, 69	sylancr 418	. . . . . . . 8 ⊢ (𝜑 → 2 ∥ (2↑(𝐴 + 1)))
71		n2dvds1 12705	. . . . . . . . . 10 ⊢ ¬ 2 ∥ 1
72	49	a1i 9	. . . . . . . . . . . 12 ⊢ (𝜑 → 2 ∈ ℤ)
73		1zzd 9683	. . . . . . . . . . . 12 ⊢ (𝜑 → 1 ∈ ℤ)
74	72, 18, 73	3jca 1208	. . . . . . . . . . 11 ⊢ (𝜑 → (2 ∈ ℤ ∧ (2↑(𝐴 + 1)) ∈ ℤ ∧ 1 ∈ ℤ))
75		dvdssub2 12628	. . . . . . . . . . 11 ⊢ (((2 ∈ ℤ ∧ (2↑(𝐴 + 1)) ∈ ℤ ∧ 1 ∈ ℤ) ∧ 2 ∥ ((2↑(𝐴 + 1)) − 1)) → (2 ∥ (2↑(𝐴 + 1)) ↔ 2 ∥ 1))
76	74, 75	sylan 283	. . . . . . . . . 10 ⊢ ((𝜑 ∧ 2 ∥ ((2↑(𝐴 + 1)) − 1)) → (2 ∥ (2↑(𝐴 + 1)) ↔ 2 ∥ 1))
77	71, 76	mtbiri 686	. . . . . . . . 9 ⊢ ((𝜑 ∧ 2 ∥ ((2↑(𝐴 + 1)) − 1)) → ¬ 2 ∥ (2↑(𝐴 + 1)))
78	77	ex 115	. . . . . . . 8 ⊢ (𝜑 → (2 ∥ ((2↑(𝐴 + 1)) − 1) → ¬ 2 ∥ (2↑(𝐴 + 1))))
79	70, 78	mt2d 634	. . . . . . 7 ⊢ (𝜑 → ¬ 2 ∥ ((2↑(𝐴 + 1)) − 1))
80		coprm 12949	. . . . . . . 8 ⊢ ((2 ∈ ℙ ∧ ((2↑(𝐴 + 1)) − 1) ∈ ℤ) → (¬ 2 ∥ ((2↑(𝐴 + 1)) − 1) ↔ (2 gcd ((2↑(𝐴 + 1)) − 1)) = 1))
81	44, 20, 80	sylancr 418	. . . . . . 7 ⊢ (𝜑 → (¬ 2 ∥ ((2↑(𝐴 + 1)) − 1) ↔ (2 gcd ((2↑(𝐴 + 1)) − 1)) = 1))
82	79, 81	mpbid 147	. . . . . 6 ⊢ (𝜑 → (2 gcd ((2↑(𝐴 + 1)) − 1)) = 1)
83		rpexp1i 12959	. . . . . . 7 ⊢ ((2 ∈ ℤ ∧ ((2↑(𝐴 + 1)) − 1) ∈ ℤ ∧ (𝐴 + 1) ∈ ℕ₀) → ((2 gcd ((2↑(𝐴 + 1)) − 1)) = 1 → ((2↑(𝐴 + 1)) gcd ((2↑(𝐴 + 1)) − 1)) = 1))
84	49, 20, 5, 83	mp3an2i 1383	. . . . . 6 ⊢ (𝜑 → ((2 gcd ((2↑(𝐴 + 1)) − 1)) = 1 → ((2↑(𝐴 + 1)) gcd ((2↑(𝐴 + 1)) − 1)) = 1))
85	82, 84	mpd 13	. . . . 5 ⊢ (𝜑 → ((2↑(𝐴 + 1)) gcd ((2↑(𝐴 + 1)) − 1)) = 1)
86	68, 85	eqtrd 2271	. . . 4 ⊢ (𝜑 → (((2↑(𝐴 + 1)) − 1) gcd (2↑(𝐴 + 1))) = 1)
87		coprmdvds 12896	. . . . 5 ⊢ ((((2↑(𝐴 + 1)) − 1) ∈ ℤ ∧ (2↑(𝐴 + 1)) ∈ ℤ ∧ 𝐵 ∈ ℤ) → ((((2↑(𝐴 + 1)) − 1) ∥ ((2↑(𝐴 + 1)) · 𝐵) ∧ (((2↑(𝐴 + 1)) − 1) gcd (2↑(𝐴 + 1))) = 1) → ((2↑(𝐴 + 1)) − 1) ∥ 𝐵))
88	20, 18, 45, 87	syl3anc 1278	. . . 4 ⊢ (𝜑 → ((((2↑(𝐴 + 1)) − 1) ∥ ((2↑(𝐴 + 1)) · 𝐵) ∧ (((2↑(𝐴 + 1)) − 1) gcd (2↑(𝐴 + 1))) = 1) → ((2↑(𝐴 + 1)) − 1) ∥ 𝐵))
89	67, 86, 88	mp2and 437	. . 3 ⊢ (𝜑 → ((2↑(𝐴 + 1)) − 1) ∥ 𝐵)
90		nndivdvds 12589	. . . 4 ⊢ ((𝐵 ∈ ℕ ∧ ((2↑(𝐴 + 1)) − 1) ∈ ℕ) → (((2↑(𝐴 + 1)) − 1) ∥ 𝐵 ↔ (𝐵 / ((2↑(𝐴 + 1)) − 1)) ∈ ℕ))
91	22, 17, 90	syl2anc 415	. . 3 ⊢ (𝜑 → (((2↑(𝐴 + 1)) − 1) ∥ 𝐵 ↔ (𝐵 / ((2↑(𝐴 + 1)) − 1)) ∈ ℕ))
92	89, 91	mpbid 147	. 2 ⊢ (𝜑 → (𝐵 / ((2↑(𝐴 + 1)) − 1)) ∈ ℕ)
93	7, 17, 92	3jca 1208	1 ⊢ (𝜑 → ((2↑(𝐴 + 1)) ∈ ℕ ∧ ((2↑(𝐴 + 1)) − 1) ∈ ℕ ∧ (𝐵 / ((2↑(𝐴 + 1)) − 1)) ∈ ℕ))

Colors of variables: wff set class

This proof depends on syntax axioms: ¬ wn 3 → wi 4 ∧ wa 104 ↔ wb 105 ∧ w3a 1009 = wceq 1402 ∈ wcel 2209 class class class wbr 4131 (class class class)co 6088 ℂcc 8184 ℝcr 8185 1c1 8187 + caddc 8189 · cmul 8191 < clt 8367 − cmin 8505 / cdiv 9011 ℕcn 9314 2c2 9365 ℕ₀cn0 9575 ℤcz 9656 ↑cexp 10997 ∥ cdvds 12580 gcd cgcd 12756 ℙcprime 12911 σ csgm 16247

This proof depends on axioms: ax-mp 5 ax-1 6 ax-2 7 ax-ia1 106 ax-ia2 107 ax-ia3 108 ax-in1 623 ax-in2 624 ax-io 721 ax-5 1500 ax-7 1501 ax-gen 1502 ax-ie1 1546 ax-ie2 1547 ax-8 1557 ax-10 1558 ax-11 1559 ax-i12 1560 ax-bndl 1562 ax-4 1563 ax-17 1579 ax-i9 1583 ax-ial 1587 ax-i5r 1588 ax-14 2212 ax-ext 2220 ax-coll 4248 ax-sep 4251 ax-nul 4261 ax-pow 4313 ax-pr 4348 ax-un 4580 ax-setind 4686 ax-iinf 4737 ax-cnex 8277 ax-resscn 8278 ax-1cn 8279 ax-1re 8280 ax-icn 8281 ax-addcl 8282 ax-addrcl 8283 ax-mulcl 8284 ax-mulrcl 8285 ax-addcom 8286 ax-mulcom 8287 ax-addass 8288 ax-mulass 8289 ax-distr 8290 ax-i2m1 8291 ax-0lt1 8292 ax-1rid 8293 ax-0id 8294 ax-rnegex 8295 ax-precex 8296 ax-cnre 8297 ax-pre-ltirr 8298 ax-pre-ltwlin 8299 ax-pre-lttrn 8300 ax-pre-apti 8301 ax-pre-ltadd 8302 ax-pre-mulgt0 8303 ax-pre-mulext 8304 ax-arch 8305 ax-caucvg 8306 ax-pre-suploc 8307 ax-addf 8308 ax-mulf 8309

This proof depends on definitions: df-bi 117 df-stab 843 df-dc 847 df-3or 1010 df-3an 1011 df-tru 1405 df-fal 1408 df-nf 1514 df-sb 1816 df-eu 2089 df-mo 2090 df-clab 2225 df-cleq 2231 df-clel 2234 df-nfc 2381 df-ne 2421 df-nel 2516 df-ral 2533 df-rex 2534 df-reu 2535 df-rmo 2536 df-rab 2537 df-v 2823 df-sbc 3052 df-csb 3148 df-dif 3222 df-un 3224 df-in 3226 df-ss 3233 df-nul 3521 df-if 3639 df-pw 3690 df-sn 3715 df-pr 3716 df-op 3718 df-uni 3936 df-int 3971 df-iun 4014 df-disj 4107 df-br 4132 df-opab 4194 df-mpt 4195 df-tr 4232 df-id 4440 df-po 4443 df-iso 4444 df-iord 4513 df-on 4515 df-ilim 4516 df-suc 4518 df-iom 4740 df-xp 4782 df-rel 4783 df-cnv 4784 df-co 4785 df-dm 4786 df-rn 4787 df-res 4788 df-ima 4789 df-iota 5340 df-fun 5382 df-fn 5383 df-f 5384 df-f1 5385 df-fo 5386 df-f1o 5387 df-fv 5388 df-isom 5389 df-riota 6041 df-ov 6091 df-oprab 6092 df-mpo 6093 df-of 6305 df-1st 6378 df-2nd 6379 df-recs 6580 df-irdg 6645 df-frec 6666 df-1o 6691 df-2o 6692 df-oadd 6695 df-er 6811 df-map 6928 df-pm 6929 df-en 7028 df-dom 7029 df-fin 7030 df-sup 7331 df-inf 7332 df-pnf 8369 df-mnf 8370 df-xr 8371 df-ltxr 8372 df-le 8373 df-sub 8507 df-neg 8508 df-reap 8912 df-ap 8919 df-div 9012 df-inn 9315 df-2 9373 df-3 9374 df-4 9375 df-n0 9576 df-xnn0 9643 df-z 9657 df-uz 9939 df-q 10037 df-rp 10073 df-xneg 10192 df-xadd 10193 df-ioo 10312 df-ico 10314 df-icc 10315 df-fz 10430 df-fzo 10568 df-fl 10723 df-mod 10782 df-seqfrec 10907 df-exp 10998 df-fac 11187 df-bc 11209 df-ihash 11238 df-shft 11603 df-cj 11630 df-re 11631 df-im 11632 df-rsqrt 11787 df-abs 11788 df-clim 12071 df-sumdc 12146 df-ef 12441 df-e 12442 df-dvds 12581 df-gcd 12757 df-prm 12912 df-pc 13094 df-rest 13655 df-topgen 13674 df-psmet 14990 df-xmet 14991 df-met 14992 df-bl 14993 df-mopn 14994 df-top 15236 df-topon 15249 df-bases 15281 df-ntr 15334 df-cn 15426 df-cnp 15427 df-tx 15491 df-cncf 15809 df-limced 15894 df-dvap 15895 df-relog 16099 df-rpcxp 16100 df-sgm 16250

This theorem is used by: perfectlem2 16312

W3C validator