perfectlem1 - Intuitionistic Logic Explorer

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

Theorem perfectlem1 15916

Description: Lemma for perfect 15918. (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 9404	. . 3 ⊢ 2 ∈ ℕ
2		perfectlem.1	. . . . 5 ⊢ (𝜑 → 𝐴 ∈ ℕ)
3	2	nnnn0d 9558	. . . 4 ⊢ (𝜑 → 𝐴 ∈ ℕ₀)
4		peano2nn0 9541	. . . 4 ⊢ (𝐴 ∈ ℕ₀ → (𝐴 + 1) ∈ ℕ₀)
5	3, 4	syl 14	. . 3 ⊢ (𝜑 → (𝐴 + 1) ∈ ℕ₀)
6		nnexpcl 10921	. . 3 ⊢ ((2 ∈ ℕ ∧ (𝐴 + 1) ∈ ℕ₀) → (2↑(𝐴 + 1)) ∈ ℕ)
7	1, 5, 6	sylancr 414	. 2 ⊢ (𝜑 → (2↑(𝐴 + 1)) ∈ ℕ)
8		2re 9312	. . . 4 ⊢ 2 ∈ ℝ
9	2	peano2nnd 9257	. . . 4 ⊢ (𝜑 → (𝐴 + 1) ∈ ℕ)
10		1lt2 9412	. . . . 5 ⊢ 1 < 2
11	10	a1i 9	. . . 4 ⊢ (𝜑 → 1 < 2)
12		expgt1 10946	. . . 4 ⊢ ((2 ∈ ℝ ∧ (𝐴 + 1) ∈ ℕ ∧ 1 < 2) → 1 < (2↑(𝐴 + 1)))
13	8, 9, 11, 12	mp3an2i 1379	. . 3 ⊢ (𝜑 → 1 < (2↑(𝐴 + 1)))
14		1nn 9253	. . . 4 ⊢ 1 ∈ ℕ
15		nnsub 9281	. . . 4 ⊢ ((1 ∈ ℕ ∧ (2↑(𝐴 + 1)) ∈ ℕ) → (1 < (2↑(𝐴 + 1)) ↔ ((2↑(𝐴 + 1)) − 1) ∈ ℕ))
16	14, 7, 15	sylancr 414	. . 3 ⊢ (𝜑 → (1 < (2↑(𝐴 + 1)) ↔ ((2↑(𝐴 + 1)) − 1) ∈ ℕ))
17	13, 16	mpbid 147	. 2 ⊢ (𝜑 → ((2↑(𝐴 + 1)) − 1) ∈ ℕ)
18	7	nnzd 9705	. . . . . . 7 ⊢ (𝜑 → (2↑(𝐴 + 1)) ∈ ℤ)
19		peano2zm 9620	. . . . . . 7 ⊢ ((2↑(𝐴 + 1)) ∈ ℤ → ((2↑(𝐴 + 1)) − 1) ∈ ℤ)
20	18, 19	syl 14	. . . . . 6 ⊢ (𝜑 → ((2↑(𝐴 + 1)) − 1) ∈ ℤ)
21		1nn0 9517	. . . . . . . 8 ⊢ 1 ∈ ℕ₀
22		perfectlem.2	. . . . . . . 8 ⊢ (𝜑 → 𝐵 ∈ ℕ)
23		sgmnncl 15905	. . . . . . . 8 ⊢ ((1 ∈ ℕ₀ ∧ 𝐵 ∈ ℕ) → (1 σ 𝐵) ∈ ℕ)
24	21, 22, 23	sylancr 414	. . . . . . 7 ⊢ (𝜑 → (1 σ 𝐵) ∈ ℕ)
25	24	nnzd 9705	. . . . . 6 ⊢ (𝜑 → (1 σ 𝐵) ∈ ℤ)
26		dvdsmul1 12507	. . . . . 6 ⊢ ((((2↑(𝐴 + 1)) − 1) ∈ ℤ ∧ (1 σ 𝐵) ∈ ℤ) → ((2↑(𝐴 + 1)) − 1) ∥ (((2↑(𝐴 + 1)) − 1) · (1 σ 𝐵)))
27	20, 25, 26	syl2anc 411	. . . . 5 ⊢ (𝜑 → ((2↑(𝐴 + 1)) − 1) ∥ (((2↑(𝐴 + 1)) − 1) · (1 σ 𝐵)))
28		2cn 9313	. . . . . . . . 9 ⊢ 2 ∈ ℂ
29		expp1 10915	. . . . . . . . 9 ⊢ ((2 ∈ ℂ ∧ 𝐴 ∈ ℕ₀) → (2↑(𝐴 + 1)) = ((2↑𝐴) · 2))
30	28, 3, 29	sylancr 414	. . . . . . . 8 ⊢ (𝜑 → (2↑(𝐴 + 1)) = ((2↑𝐴) · 2))
31		nnexpcl 10921	. . . . . . . . . . 11 ⊢ ((2 ∈ ℕ ∧ 𝐴 ∈ ℕ₀) → (2↑𝐴) ∈ ℕ)
32	1, 3, 31	sylancr 414	. . . . . . . . . 10 ⊢ (𝜑 → (2↑𝐴) ∈ ℕ)
33	32	nncnd 9256	. . . . . . . . 9 ⊢ (𝜑 → (2↑𝐴) ∈ ℂ)
34		mulcom 8261	. . . . . . . . 9 ⊢ (((2↑𝐴) ∈ ℂ ∧ 2 ∈ ℂ) → ((2↑𝐴) · 2) = (2 · (2↑𝐴)))
35	33, 28, 34	sylancl 413	. . . . . . . 8 ⊢ (𝜑 → ((2↑𝐴) · 2) = (2 · (2↑𝐴)))
36	30, 35	eqtrd 2267	. . . . . . 7 ⊢ (𝜑 → (2↑(𝐴 + 1)) = (2 · (2↑𝐴)))
37	36	oveq1d 6067	. . . . . 6 ⊢ (𝜑 → ((2↑(𝐴 + 1)) · 𝐵) = ((2 · (2↑𝐴)) · 𝐵))
38	28	a1i 9	. . . . . . 7 ⊢ (𝜑 → 2 ∈ ℂ)
39	22	nncnd 9256	. . . . . . 7 ⊢ (𝜑 → 𝐵 ∈ ℂ)
40	38, 33, 39	mulassd 8302	. . . . . 6 ⊢ (𝜑 → ((2 · (2↑𝐴)) · 𝐵) = (2 · ((2↑𝐴) · 𝐵)))
41		ax-1cn 8225	. . . . . . . . 9 ⊢ 1 ∈ ℂ
42	41	a1i 9	. . . . . . . 8 ⊢ (𝜑 → 1 ∈ ℂ)
43		perfectlem.3	. . . . . . . . . 10 ⊢ (𝜑 → ¬ 2 ∥ 𝐵)
44		2prm 12832	. . . . . . . . . . 11 ⊢ 2 ∈ ℙ
45	22	nnzd 9705	. . . . . . . . . . 11 ⊢ (𝜑 → 𝐵 ∈ ℤ)
46		coprm 12849	. . . . . . . . . . 11 ⊢ ((2 ∈ ℙ ∧ 𝐵 ∈ ℤ) → (¬ 2 ∥ 𝐵 ↔ (2 gcd 𝐵) = 1))
47	44, 45, 46	sylancr 414	. . . . . . . . . 10 ⊢ (𝜑 → (¬ 2 ∥ 𝐵 ↔ (2 gcd 𝐵) = 1))
48	43, 47	mpbid 147	. . . . . . . . 9 ⊢ (𝜑 → (2 gcd 𝐵) = 1)
49		2z 9610	. . . . . . . . . 10 ⊢ 2 ∈ ℤ
50		rpexp1i 12859	. . . . . . . . . 10 ⊢ ((2 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐴 ∈ ℕ₀) → ((2 gcd 𝐵) = 1 → ((2↑𝐴) gcd 𝐵) = 1))
51	49, 45, 3, 50	mp3an2i 1379	. . . . . . . . 9 ⊢ (𝜑 → ((2 gcd 𝐵) = 1 → ((2↑𝐴) gcd 𝐵) = 1))
52	48, 51	mpd 13	. . . . . . . 8 ⊢ (𝜑 → ((2↑𝐴) gcd 𝐵) = 1)
53		sgmmul 15913	. . . . . . . 8 ⊢ ((1 ∈ ℂ ∧ ((2↑𝐴) ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ ((2↑𝐴) gcd 𝐵) = 1)) → (1 σ ((2↑𝐴) · 𝐵)) = ((1 σ (2↑𝐴)) · (1 σ 𝐵)))
54	42, 32, 22, 52, 53	syl13anc 1276	. . . . . . 7 ⊢ (𝜑 → (1 σ ((2↑𝐴) · 𝐵)) = ((1 σ (2↑𝐴)) · (1 σ 𝐵)))
55		perfectlem.4	. . . . . . 7 ⊢ (𝜑 → (1 σ ((2↑𝐴) · 𝐵)) = (2 · ((2↑𝐴) · 𝐵)))
56	2	nncnd 9256	. . . . . . . . . . . 12 ⊢ (𝜑 → 𝐴 ∈ ℂ)
57		pncan 8484	. . . . . . . . . . . 12 ⊢ ((𝐴 ∈ ℂ ∧ 1 ∈ ℂ) → ((𝐴 + 1) − 1) = 𝐴)
58	56, 41, 57	sylancl 413	. . . . . . . . . . 11 ⊢ (𝜑 → ((𝐴 + 1) − 1) = 𝐴)
59	58	oveq2d 6068	. . . . . . . . . 10 ⊢ (𝜑 → (2↑((𝐴 + 1) − 1)) = (2↑𝐴))
60	59	oveq2d 6068	. . . . . . . . 9 ⊢ (𝜑 → (1 σ (2↑((𝐴 + 1) − 1))) = (1 σ (2↑𝐴)))
61		1sgm2ppw 15912	. . . . . . . . . 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 2269	. . . . . . . 8 ⊢ (𝜑 → (1 σ (2↑𝐴)) = ((2↑(𝐴 + 1)) − 1))
64	63	oveq1d 6067	. . . . . . 7 ⊢ (𝜑 → ((1 σ (2↑𝐴)) · (1 σ 𝐵)) = (((2↑(𝐴 + 1)) − 1) · (1 σ 𝐵)))
65	54, 55, 64	3eqtr3d 2275	. . . . . 6 ⊢ (𝜑 → (2 · ((2↑𝐴) · 𝐵)) = (((2↑(𝐴 + 1)) − 1) · (1 σ 𝐵)))
66	37, 40, 65	3eqtrd 2271	. . . . 5 ⊢ (𝜑 → ((2↑(𝐴 + 1)) · 𝐵) = (((2↑(𝐴 + 1)) − 1) · (1 σ 𝐵)))
67	27, 66	breqtrrd 4139	. . . 4 ⊢ (𝜑 → ((2↑(𝐴 + 1)) − 1) ∥ ((2↑(𝐴 + 1)) · 𝐵))
68	20, 18	gcdcomd 12678	. . . . 5 ⊢ (𝜑 → (((2↑(𝐴 + 1)) − 1) gcd (2↑(𝐴 + 1))) = ((2↑(𝐴 + 1)) gcd ((2↑(𝐴 + 1)) − 1)))
69		iddvdsexp 12509	. . . . . . . . 9 ⊢ ((2 ∈ ℤ ∧ (𝐴 + 1) ∈ ℕ) → 2 ∥ (2↑(𝐴 + 1)))
70	49, 9, 69	sylancr 414	. . . . . . . 8 ⊢ (𝜑 → 2 ∥ (2↑(𝐴 + 1)))
71		n2dvds1 12606	. . . . . . . . . 10 ⊢ ¬ 2 ∥ 1
72	49	a1i 9	. . . . . . . . . . . 12 ⊢ (𝜑 → 2 ∈ ℤ)
73		1zzd 9609	. . . . . . . . . . . 12 ⊢ (𝜑 → 1 ∈ ℤ)
74	72, 18, 73	3jca 1204	. . . . . . . . . . 11 ⊢ (𝜑 → (2 ∈ ℤ ∧ (2↑(𝐴 + 1)) ∈ ℤ ∧ 1 ∈ ℤ))
75		dvdssub2 12529	. . . . . . . . . . 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 682	. . . . . . . . 9 ⊢ ((𝜑 ∧ 2 ∥ ((2↑(𝐴 + 1)) − 1)) → ¬ 2 ∥ (2↑(𝐴 + 1)))
78	77	ex 115	. . . . . . . 8 ⊢ (𝜑 → (2 ∥ ((2↑(𝐴 + 1)) − 1) → ¬ 2 ∥ (2↑(𝐴 + 1))))
79	70, 78	mt2d 630	. . . . . . 7 ⊢ (𝜑 → ¬ 2 ∥ ((2↑(𝐴 + 1)) − 1))
80		coprm 12849	. . . . . . . 8 ⊢ ((2 ∈ ℙ ∧ ((2↑(𝐴 + 1)) − 1) ∈ ℤ) → (¬ 2 ∥ ((2↑(𝐴 + 1)) − 1) ↔ (2 gcd ((2↑(𝐴 + 1)) − 1)) = 1))
81	44, 20, 80	sylancr 414	. . . . . . 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 12859	. . . . . . 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 1379	. . . . . 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 2267	. . . 4 ⊢ (𝜑 → (((2↑(𝐴 + 1)) − 1) gcd (2↑(𝐴 + 1))) = 1)
87		coprmdvds 12797	. . . . 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 1274	. . . 4 ⊢ (𝜑 → ((((2↑(𝐴 + 1)) − 1) ∥ ((2↑(𝐴 + 1)) · 𝐵) ∧ (((2↑(𝐴 + 1)) − 1) gcd (2↑(𝐴 + 1))) = 1) → ((2↑(𝐴 + 1)) − 1) ∥ 𝐵))
89	67, 86, 88	mp2and 433	. . 3 ⊢ (𝜑 → ((2↑(𝐴 + 1)) − 1) ∥ 𝐵)
90		nndivdvds 12490	. . . 4 ⊢ ((𝐵 ∈ ℕ ∧ ((2↑(𝐴 + 1)) − 1) ∈ ℕ) → (((2↑(𝐴 + 1)) − 1) ∥ 𝐵 ↔ (𝐵 / ((2↑(𝐴 + 1)) − 1)) ∈ ℕ))
91	22, 17, 90	syl2anc 411	. . 3 ⊢ (𝜑 → (((2↑(𝐴 + 1)) − 1) ∥ 𝐵 ↔ (𝐵 / ((2↑(𝐴 + 1)) − 1)) ∈ ℕ))
92	89, 91	mpbid 147	. 2 ⊢ (𝜑 → (𝐵 / ((2↑(𝐴 + 1)) − 1)) ∈ ℕ)
93	7, 17, 92	3jca 1204	1 ⊢ (𝜑 → ((2↑(𝐴 + 1)) ∈ ℕ ∧ ((2↑(𝐴 + 1)) − 1) ∈ ℕ ∧ (𝐵 / ((2↑(𝐴 + 1)) − 1)) ∈ ℕ))

Colors of variables: wff set class

Syntax hints: ¬ wn 3 → wi 4 ∧ wa 104 ↔ wb 105 ∧ w3a 1005 = wceq 1398 ∈ wcel 2205 class class class wbr 4111 (class class class)co 6052 ℂcc 8130 ℝcr 8131 1c1 8133 + caddc 8135 · cmul 8137 < clt 8313 − cmin 8449 / cdiv 8951 ℕcn 9242 2c2 9293 ℕ₀cn0 9501 ℤcz 9582 ↑cexp 10907 ∥ cdvds 12481 gcd cgcd 12657 ℙcprime 12812 σ csgm 15898

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 619 ax-in2 620 ax-io 717 ax-5 1496 ax-7 1497 ax-gen 1498 ax-ie1 1542 ax-ie2 1543 ax-8 1553 ax-10 1554 ax-11 1555 ax-i12 1556 ax-bndl 1558 ax-4 1559 ax-17 1575 ax-i9 1579 ax-ial 1583 ax-i5r 1584 ax-13 2207 ax-14 2208 ax-ext 2216 ax-coll 4227 ax-sep 4230 ax-nul 4238 ax-pow 4289 ax-pr 4324 ax-un 4556 ax-setind 4661 ax-iinf 4712 ax-cnex 8223 ax-resscn 8224 ax-1cn 8225 ax-1re 8226 ax-icn 8227 ax-addcl 8228 ax-addrcl 8229 ax-mulcl 8230 ax-mulrcl 8231 ax-addcom 8232 ax-mulcom 8233 ax-addass 8234 ax-mulass 8235 ax-distr 8236 ax-i2m1 8237 ax-0lt1 8238 ax-1rid 8239 ax-0id 8240 ax-rnegex 8241 ax-precex 8242 ax-cnre 8243 ax-pre-ltirr 8244 ax-pre-ltwlin 8245 ax-pre-lttrn 8246 ax-pre-apti 8247 ax-pre-ltadd 8248 ax-pre-mulgt0 8249 ax-pre-mulext 8250 ax-arch 8251 ax-caucvg 8252 ax-pre-suploc 8253 ax-addf 8254 ax-mulf 8255

This theorem depends on definitions: df-bi 117 df-stab 839 df-dc 843 df-3or 1006 df-3an 1007 df-tru 1401 df-fal 1404 df-nf 1510 df-sb 1812 df-eu 2085 df-mo 2086 df-clab 2221 df-cleq 2227 df-clel 2230 df-nfc 2375 df-ne 2415 df-nel 2510 df-ral 2527 df-rex 2528 df-reu 2529 df-rmo 2530 df-rab 2531 df-v 2817 df-sbc 3045 df-csb 3141 df-dif 3215 df-un 3217 df-in 3219 df-ss 3226 df-nul 3511 df-if 3623 df-pw 3673 df-sn 3697 df-pr 3698 df-op 3700 df-uni 3917 df-int 3952 df-iun 3995 df-disj 4088 df-br 4112 df-opab 4174 df-mpt 4175 df-tr 4211 df-id 4416 df-po 4419 df-iso 4420 df-iord 4489 df-on 4491 df-ilim 4492 df-suc 4494 df-iom 4715 df-xp 4757 df-rel 4758 df-cnv 4759 df-co 4760 df-dm 4761 df-rn 4762 df-res 4763 df-ima 4764 df-iota 5314 df-fun 5356 df-fn 5357 df-f 5358 df-f1 5359 df-fo 5360 df-f1o 5361 df-fv 5362 df-isom 5363 df-riota 6005 df-ov 6055 df-oprab 6056 df-mpo 6057 df-of 6268 df-1st 6336 df-2nd 6337 df-recs 6538 df-irdg 6603 df-frec 6624 df-1o 6649 df-2o 6650 df-oadd 6653 df-er 6769 df-map 6886 df-pm 6887 df-en 6978 df-dom 6979 df-fin 6980 df-sup 7277 df-inf 7278 df-pnf 8315 df-mnf 8316 df-xr 8317 df-ltxr 8318 df-le 8319 df-sub 8451 df-neg 8452 df-reap 8854 df-ap 8861 df-div 8952 df-inn 9243 df-2 9301 df-3 9302 df-4 9303 df-n0 9502 df-xnn0 9569 df-z 9583 df-uz 9860 df-q 9958 df-rp 9993 df-xneg 10111 df-xadd 10112 df-ioo 10231 df-ico 10233 df-icc 10234 df-fz 10349 df-fzo 10484 df-fl 10637 df-mod 10692 df-seqfrec 10817 df-exp 10908 df-fac 11096 df-bc 11118 df-ihash 11147 df-shft 11508 df-cj 11535 df-re 11536 df-im 11537 df-rsqrt 11691 df-abs 11692 df-clim 11972 df-sumdc 12047 df-ef 12342 df-e 12343 df-dvds 12482 df-gcd 12658 df-prm 12813 df-pc 12991 df-rest 13475 df-topgen 13494 df-psmet 14740 df-xmet 14741 df-met 14742 df-bl 14743 df-mopn 14744 df-top 14912 df-topon 14925 df-bases 14957 df-ntr 15010 df-cn 15102 df-cnp 15103 df-tx 15167 df-cncf 15485 df-limced 15570 df-dvap 15571 df-relog 15772 df-rpcxp 15773 df-sgm 15899

This theorem is referenced by: perfectlem2 15917

W3C validator