perfectlem1 - Intuitionistic Logic Explorer

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

Theorem perfectlem1 15796

Description: Lemma for perfect 15798. (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 9347	. . 3 ⊢ 2 ∈ ℕ
2		perfectlem.1	. . . . 5 ⊢ (𝜑 → 𝐴 ∈ ℕ)
3	2	nnnn0d 9499	. . . 4 ⊢ (𝜑 → 𝐴 ∈ ℕ₀)
4		peano2nn0 9484	. . . 4 ⊢ (𝐴 ∈ ℕ₀ → (𝐴 + 1) ∈ ℕ₀)
5	3, 4	syl 14	. . 3 ⊢ (𝜑 → (𝐴 + 1) ∈ ℕ₀)
6		nnexpcl 10860	. . 3 ⊢ ((2 ∈ ℕ ∧ (𝐴 + 1) ∈ ℕ₀) → (2↑(𝐴 + 1)) ∈ ℕ)
7	1, 5, 6	sylancr 414	. 2 ⊢ (𝜑 → (2↑(𝐴 + 1)) ∈ ℕ)
8		2re 9255	. . . 4 ⊢ 2 ∈ ℝ
9	2	peano2nnd 9200	. . . 4 ⊢ (𝜑 → (𝐴 + 1) ∈ ℕ)
10		1lt2 9355	. . . . 5 ⊢ 1 < 2
11	10	a1i 9	. . . 4 ⊢ (𝜑 → 1 < 2)
12		expgt1 10885	. . . 4 ⊢ ((2 ∈ ℝ ∧ (𝐴 + 1) ∈ ℕ ∧ 1 < 2) → 1 < (2↑(𝐴 + 1)))
13	8, 9, 11, 12	mp3an2i 1379	. . 3 ⊢ (𝜑 → 1 < (2↑(𝐴 + 1)))
14		1nn 9196	. . . 4 ⊢ 1 ∈ ℕ
15		nnsub 9224	. . . 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 9645	. . . . . . 7 ⊢ (𝜑 → (2↑(𝐴 + 1)) ∈ ℤ)
19		peano2zm 9561	. . . . . . 7 ⊢ ((2↑(𝐴 + 1)) ∈ ℤ → ((2↑(𝐴 + 1)) − 1) ∈ ℤ)
20	18, 19	syl 14	. . . . . 6 ⊢ (𝜑 → ((2↑(𝐴 + 1)) − 1) ∈ ℤ)
21		1nn0 9460	. . . . . . . 8 ⊢ 1 ∈ ℕ₀
22		perfectlem.2	. . . . . . . 8 ⊢ (𝜑 → 𝐵 ∈ ℕ)
23		sgmnncl 15785	. . . . . . . 8 ⊢ ((1 ∈ ℕ₀ ∧ 𝐵 ∈ ℕ) → (1 σ 𝐵) ∈ ℕ)
24	21, 22, 23	sylancr 414	. . . . . . 7 ⊢ (𝜑 → (1 σ 𝐵) ∈ ℕ)
25	24	nnzd 9645	. . . . . 6 ⊢ (𝜑 → (1 σ 𝐵) ∈ ℤ)
26		dvdsmul1 12437	. . . . . 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 9256	. . . . . . . . 9 ⊢ 2 ∈ ℂ
29		expp1 10854	. . . . . . . . 9 ⊢ ((2 ∈ ℂ ∧ 𝐴 ∈ ℕ₀) → (2↑(𝐴 + 1)) = ((2↑𝐴) · 2))
30	28, 3, 29	sylancr 414	. . . . . . . 8 ⊢ (𝜑 → (2↑(𝐴 + 1)) = ((2↑𝐴) · 2))
31		nnexpcl 10860	. . . . . . . . . . 11 ⊢ ((2 ∈ ℕ ∧ 𝐴 ∈ ℕ₀) → (2↑𝐴) ∈ ℕ)
32	1, 3, 31	sylancr 414	. . . . . . . . . 10 ⊢ (𝜑 → (2↑𝐴) ∈ ℕ)
33	32	nncnd 9199	. . . . . . . . 9 ⊢ (𝜑 → (2↑𝐴) ∈ ℂ)
34		mulcom 8204	. . . . . . . . 9 ⊢ (((2↑𝐴) ∈ ℂ ∧ 2 ∈ ℂ) → ((2↑𝐴) · 2) = (2 · (2↑𝐴)))
35	33, 28, 34	sylancl 413	. . . . . . . 8 ⊢ (𝜑 → ((2↑𝐴) · 2) = (2 · (2↑𝐴)))
36	30, 35	eqtrd 2264	. . . . . . 7 ⊢ (𝜑 → (2↑(𝐴 + 1)) = (2 · (2↑𝐴)))
37	36	oveq1d 6043	. . . . . 6 ⊢ (𝜑 → ((2↑(𝐴 + 1)) · 𝐵) = ((2 · (2↑𝐴)) · 𝐵))
38	28	a1i 9	. . . . . . 7 ⊢ (𝜑 → 2 ∈ ℂ)
39	22	nncnd 9199	. . . . . . 7 ⊢ (𝜑 → 𝐵 ∈ ℂ)
40	38, 33, 39	mulassd 8245	. . . . . 6 ⊢ (𝜑 → ((2 · (2↑𝐴)) · 𝐵) = (2 · ((2↑𝐴) · 𝐵)))
41		ax-1cn 8168	. . . . . . . . 9 ⊢ 1 ∈ ℂ
42	41	a1i 9	. . . . . . . 8 ⊢ (𝜑 → 1 ∈ ℂ)
43		perfectlem.3	. . . . . . . . . 10 ⊢ (𝜑 → ¬ 2 ∥ 𝐵)
44		2prm 12762	. . . . . . . . . . 11 ⊢ 2 ∈ ℙ
45	22	nnzd 9645	. . . . . . . . . . 11 ⊢ (𝜑 → 𝐵 ∈ ℤ)
46		coprm 12779	. . . . . . . . . . 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 9551	. . . . . . . . . 10 ⊢ 2 ∈ ℤ
50		rpexp1i 12789	. . . . . . . . . 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 15793	. . . . . . . 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 9199	. . . . . . . . . . . 12 ⊢ (𝜑 → 𝐴 ∈ ℂ)
57		pncan 8427	. . . . . . . . . . . 12 ⊢ ((𝐴 ∈ ℂ ∧ 1 ∈ ℂ) → ((𝐴 + 1) − 1) = 𝐴)
58	56, 41, 57	sylancl 413	. . . . . . . . . . 11 ⊢ (𝜑 → ((𝐴 + 1) − 1) = 𝐴)
59	58	oveq2d 6044	. . . . . . . . . 10 ⊢ (𝜑 → (2↑((𝐴 + 1) − 1)) = (2↑𝐴))
60	59	oveq2d 6044	. . . . . . . . 9 ⊢ (𝜑 → (1 σ (2↑((𝐴 + 1) − 1))) = (1 σ (2↑𝐴)))
61		1sgm2ppw 15792	. . . . . . . . . 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 2266	. . . . . . . 8 ⊢ (𝜑 → (1 σ (2↑𝐴)) = ((2↑(𝐴 + 1)) − 1))
64	63	oveq1d 6043	. . . . . . 7 ⊢ (𝜑 → ((1 σ (2↑𝐴)) · (1 σ 𝐵)) = (((2↑(𝐴 + 1)) − 1) · (1 σ 𝐵)))
65	54, 55, 64	3eqtr3d 2272	. . . . . 6 ⊢ (𝜑 → (2 · ((2↑𝐴) · 𝐵)) = (((2↑(𝐴 + 1)) − 1) · (1 σ 𝐵)))
66	37, 40, 65	3eqtrd 2268	. . . . 5 ⊢ (𝜑 → ((2↑(𝐴 + 1)) · 𝐵) = (((2↑(𝐴 + 1)) − 1) · (1 σ 𝐵)))
67	27, 66	breqtrrd 4121	. . . 4 ⊢ (𝜑 → ((2↑(𝐴 + 1)) − 1) ∥ ((2↑(𝐴 + 1)) · 𝐵))
68	20, 18	gcdcomd 12608	. . . . 5 ⊢ (𝜑 → (((2↑(𝐴 + 1)) − 1) gcd (2↑(𝐴 + 1))) = ((2↑(𝐴 + 1)) gcd ((2↑(𝐴 + 1)) − 1)))
69		iddvdsexp 12439	. . . . . . . . 9 ⊢ ((2 ∈ ℤ ∧ (𝐴 + 1) ∈ ℕ) → 2 ∥ (2↑(𝐴 + 1)))
70	49, 9, 69	sylancr 414	. . . . . . . 8 ⊢ (𝜑 → 2 ∥ (2↑(𝐴 + 1)))
71		n2dvds1 12536	. . . . . . . . . 10 ⊢ ¬ 2 ∥ 1
72	49	a1i 9	. . . . . . . . . . . 12 ⊢ (𝜑 → 2 ∈ ℤ)
73		1zzd 9550	. . . . . . . . . . . 12 ⊢ (𝜑 → 1 ∈ ℤ)
74	72, 18, 73	3jca 1204	. . . . . . . . . . 11 ⊢ (𝜑 → (2 ∈ ℤ ∧ (2↑(𝐴 + 1)) ∈ ℤ ∧ 1 ∈ ℤ))
75		dvdssub2 12459	. . . . . . . . . . 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 12779	. . . . . . . 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 12789	. . . . . . 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 2264	. . . 4 ⊢ (𝜑 → (((2↑(𝐴 + 1)) − 1) gcd (2↑(𝐴 + 1))) = 1)
87		coprmdvds 12727	. . . . 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 12420	. . . 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 2202 class class class wbr 4093 (class class class)co 6028 ℂcc 8073 ℝcr 8074 1c1 8076 + caddc 8078 · cmul 8080 < clt 8256 − cmin 8392 / cdiv 8894 ℕcn 9185 2c2 9236 ℕ₀cn0 9444 ℤcz 9523 ↑cexp 10846 ∥ cdvds 12411 gcd cgcd 12587 ℙcprime 12742 σ csgm 15778

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 2204 ax-14 2205 ax-ext 2213 ax-coll 4209 ax-sep 4212 ax-nul 4220 ax-pow 4270 ax-pr 4305 ax-un 4536 ax-setind 4641 ax-iinf 4692 ax-cnex 8166 ax-resscn 8167 ax-1cn 8168 ax-1re 8169 ax-icn 8170 ax-addcl 8171 ax-addrcl 8172 ax-mulcl 8173 ax-mulrcl 8174 ax-addcom 8175 ax-mulcom 8176 ax-addass 8177 ax-mulass 8178 ax-distr 8179 ax-i2m1 8180 ax-0lt1 8181 ax-1rid 8182 ax-0id 8183 ax-rnegex 8184 ax-precex 8185 ax-cnre 8186 ax-pre-ltirr 8187 ax-pre-ltwlin 8188 ax-pre-lttrn 8189 ax-pre-apti 8190 ax-pre-ltadd 8191 ax-pre-mulgt0 8192 ax-pre-mulext 8193 ax-arch 8194 ax-caucvg 8195 ax-pre-suploc 8196 ax-addf 8197 ax-mulf 8198

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 1811 df-eu 2082 df-mo 2083 df-clab 2218 df-cleq 2224 df-clel 2227 df-nfc 2364 df-ne 2404 df-nel 2499 df-ral 2516 df-rex 2517 df-reu 2518 df-rmo 2519 df-rab 2520 df-v 2805 df-sbc 3033 df-csb 3129 df-dif 3203 df-un 3205 df-in 3207 df-ss 3214 df-nul 3497 df-if 3608 df-pw 3658 df-sn 3679 df-pr 3680 df-op 3682 df-uni 3899 df-int 3934 df-iun 3977 df-disj 4070 df-br 4094 df-opab 4156 df-mpt 4157 df-tr 4193 df-id 4396 df-po 4399 df-iso 4400 df-iord 4469 df-on 4471 df-ilim 4472 df-suc 4474 df-iom 4695 df-xp 4737 df-rel 4738 df-cnv 4739 df-co 4740 df-dm 4741 df-rn 4742 df-res 4743 df-ima 4744 df-iota 5293 df-fun 5335 df-fn 5336 df-f 5337 df-f1 5338 df-fo 5339 df-f1o 5340 df-fv 5341 df-isom 5342 df-riota 5981 df-ov 6031 df-oprab 6032 df-mpo 6033 df-of 6244 df-1st 6312 df-2nd 6313 df-recs 6514 df-irdg 6579 df-frec 6600 df-1o 6625 df-2o 6626 df-oadd 6629 df-er 6745 df-map 6862 df-pm 6863 df-en 6953 df-dom 6954 df-fin 6955 df-sup 7226 df-inf 7227 df-pnf 8258 df-mnf 8259 df-xr 8260 df-ltxr 8261 df-le 8262 df-sub 8394 df-neg 8395 df-reap 8797 df-ap 8804 df-div 8895 df-inn 9186 df-2 9244 df-3 9245 df-4 9246 df-n0 9445 df-xnn0 9510 df-z 9524 df-uz 9800 df-q 9898 df-rp 9933 df-xneg 10051 df-xadd 10052 df-ioo 10171 df-ico 10173 df-icc 10174 df-fz 10289 df-fzo 10423 df-fl 10576 df-mod 10631 df-seqfrec 10756 df-exp 10847 df-fac 11034 df-bc 11056 df-ihash 11084 df-shft 11438 df-cj 11465 df-re 11466 df-im 11467 df-rsqrt 11621 df-abs 11622 df-clim 11902 df-sumdc 11977 df-ef 12272 df-e 12273 df-dvds 12412 df-gcd 12588 df-prm 12743 df-pc 12921 df-rest 13387 df-topgen 13406 df-psmet 14622 df-xmet 14623 df-met 14624 df-bl 14625 df-mopn 14626 df-top 14792 df-topon 14805 df-bases 14837 df-ntr 14890 df-cn 14982 df-cnp 14983 df-tx 15047 df-cncf 15365 df-limced 15450 df-dvap 15451 df-relog 15652 df-rpcxp 15653 df-sgm 15779

This theorem is referenced by: perfectlem2 15797

W3C validator