perfectlem1 - Intuitionistic Logic Explorer

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

Theorem perfectlem1 15694

Description: Lemma for perfect 15696. (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 9288	. . 3 ⊢ 2 ∈ ℕ
2		perfectlem.1	. . . . 5 ⊢ (𝜑 → 𝐴 ∈ ℕ)
3	2	nnnn0d 9438	. . . 4 ⊢ (𝜑 → 𝐴 ∈ ℕ₀)
4		peano2nn0 9425	. . . 4 ⊢ (𝐴 ∈ ℕ₀ → (𝐴 + 1) ∈ ℕ₀)
5	3, 4	syl 14	. . 3 ⊢ (𝜑 → (𝐴 + 1) ∈ ℕ₀)
6		nnexpcl 10791	. . 3 ⊢ ((2 ∈ ℕ ∧ (𝐴 + 1) ∈ ℕ₀) → (2↑(𝐴 + 1)) ∈ ℕ)
7	1, 5, 6	sylancr 414	. 2 ⊢ (𝜑 → (2↑(𝐴 + 1)) ∈ ℕ)
8		2re 9196	. . . 4 ⊢ 2 ∈ ℝ
9	2	peano2nnd 9141	. . . 4 ⊢ (𝜑 → (𝐴 + 1) ∈ ℕ)
10		1lt2 9296	. . . . 5 ⊢ 1 < 2
11	10	a1i 9	. . . 4 ⊢ (𝜑 → 1 < 2)
12		expgt1 10816	. . . 4 ⊢ ((2 ∈ ℝ ∧ (𝐴 + 1) ∈ ℕ ∧ 1 < 2) → 1 < (2↑(𝐴 + 1)))
13	8, 9, 11, 12	mp3an2i 1376	. . 3 ⊢ (𝜑 → 1 < (2↑(𝐴 + 1)))
14		1nn 9137	. . . 4 ⊢ 1 ∈ ℕ
15		nnsub 9165	. . . 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 9584	. . . . . . 7 ⊢ (𝜑 → (2↑(𝐴 + 1)) ∈ ℤ)
19		peano2zm 9500	. . . . . . 7 ⊢ ((2↑(𝐴 + 1)) ∈ ℤ → ((2↑(𝐴 + 1)) − 1) ∈ ℤ)
20	18, 19	syl 14	. . . . . 6 ⊢ (𝜑 → ((2↑(𝐴 + 1)) − 1) ∈ ℤ)
21		1nn0 9401	. . . . . . . 8 ⊢ 1 ∈ ℕ₀
22		perfectlem.2	. . . . . . . 8 ⊢ (𝜑 → 𝐵 ∈ ℕ)
23		sgmnncl 15683	. . . . . . . 8 ⊢ ((1 ∈ ℕ₀ ∧ 𝐵 ∈ ℕ) → (1 σ 𝐵) ∈ ℕ)
24	21, 22, 23	sylancr 414	. . . . . . 7 ⊢ (𝜑 → (1 σ 𝐵) ∈ ℕ)
25	24	nnzd 9584	. . . . . 6 ⊢ (𝜑 → (1 σ 𝐵) ∈ ℤ)
26		dvdsmul1 12345	. . . . . 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 9197	. . . . . . . . 9 ⊢ 2 ∈ ℂ
29		expp1 10785	. . . . . . . . 9 ⊢ ((2 ∈ ℂ ∧ 𝐴 ∈ ℕ₀) → (2↑(𝐴 + 1)) = ((2↑𝐴) · 2))
30	28, 3, 29	sylancr 414	. . . . . . . 8 ⊢ (𝜑 → (2↑(𝐴 + 1)) = ((2↑𝐴) · 2))
31		nnexpcl 10791	. . . . . . . . . . 11 ⊢ ((2 ∈ ℕ ∧ 𝐴 ∈ ℕ₀) → (2↑𝐴) ∈ ℕ)
32	1, 3, 31	sylancr 414	. . . . . . . . . 10 ⊢ (𝜑 → (2↑𝐴) ∈ ℕ)
33	32	nncnd 9140	. . . . . . . . 9 ⊢ (𝜑 → (2↑𝐴) ∈ ℂ)
34		mulcom 8144	. . . . . . . . 9 ⊢ (((2↑𝐴) ∈ ℂ ∧ 2 ∈ ℂ) → ((2↑𝐴) · 2) = (2 · (2↑𝐴)))
35	33, 28, 34	sylancl 413	. . . . . . . 8 ⊢ (𝜑 → ((2↑𝐴) · 2) = (2 · (2↑𝐴)))
36	30, 35	eqtrd 2262	. . . . . . 7 ⊢ (𝜑 → (2↑(𝐴 + 1)) = (2 · (2↑𝐴)))
37	36	oveq1d 6025	. . . . . 6 ⊢ (𝜑 → ((2↑(𝐴 + 1)) · 𝐵) = ((2 · (2↑𝐴)) · 𝐵))
38	28	a1i 9	. . . . . . 7 ⊢ (𝜑 → 2 ∈ ℂ)
39	22	nncnd 9140	. . . . . . 7 ⊢ (𝜑 → 𝐵 ∈ ℂ)
40	38, 33, 39	mulassd 8186	. . . . . 6 ⊢ (𝜑 → ((2 · (2↑𝐴)) · 𝐵) = (2 · ((2↑𝐴) · 𝐵)))
41		ax-1cn 8108	. . . . . . . . 9 ⊢ 1 ∈ ℂ
42	41	a1i 9	. . . . . . . 8 ⊢ (𝜑 → 1 ∈ ℂ)
43		perfectlem.3	. . . . . . . . . 10 ⊢ (𝜑 → ¬ 2 ∥ 𝐵)
44		2prm 12670	. . . . . . . . . . 11 ⊢ 2 ∈ ℙ
45	22	nnzd 9584	. . . . . . . . . . 11 ⊢ (𝜑 → 𝐵 ∈ ℤ)
46		coprm 12687	. . . . . . . . . . 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 9490	. . . . . . . . . 10 ⊢ 2 ∈ ℤ
50		rpexp1i 12697	. . . . . . . . . 10 ⊢ ((2 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐴 ∈ ℕ₀) → ((2 gcd 𝐵) = 1 → ((2↑𝐴) gcd 𝐵) = 1))
51	49, 45, 3, 50	mp3an2i 1376	. . . . . . . . 9 ⊢ (𝜑 → ((2 gcd 𝐵) = 1 → ((2↑𝐴) gcd 𝐵) = 1))
52	48, 51	mpd 13	. . . . . . . 8 ⊢ (𝜑 → ((2↑𝐴) gcd 𝐵) = 1)
53		sgmmul 15691	. . . . . . . 8 ⊢ ((1 ∈ ℂ ∧ ((2↑𝐴) ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ ((2↑𝐴) gcd 𝐵) = 1)) → (1 σ ((2↑𝐴) · 𝐵)) = ((1 σ (2↑𝐴)) · (1 σ 𝐵)))
54	42, 32, 22, 52, 53	syl13anc 1273	. . . . . . 7 ⊢ (𝜑 → (1 σ ((2↑𝐴) · 𝐵)) = ((1 σ (2↑𝐴)) · (1 σ 𝐵)))
55		perfectlem.4	. . . . . . 7 ⊢ (𝜑 → (1 σ ((2↑𝐴) · 𝐵)) = (2 · ((2↑𝐴) · 𝐵)))
56	2	nncnd 9140	. . . . . . . . . . . 12 ⊢ (𝜑 → 𝐴 ∈ ℂ)
57		pncan 8368	. . . . . . . . . . . 12 ⊢ ((𝐴 ∈ ℂ ∧ 1 ∈ ℂ) → ((𝐴 + 1) − 1) = 𝐴)
58	56, 41, 57	sylancl 413	. . . . . . . . . . 11 ⊢ (𝜑 → ((𝐴 + 1) − 1) = 𝐴)
59	58	oveq2d 6026	. . . . . . . . . 10 ⊢ (𝜑 → (2↑((𝐴 + 1) − 1)) = (2↑𝐴))
60	59	oveq2d 6026	. . . . . . . . 9 ⊢ (𝜑 → (1 σ (2↑((𝐴 + 1) − 1))) = (1 σ (2↑𝐴)))
61		1sgm2ppw 15690	. . . . . . . . . 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 2264	. . . . . . . 8 ⊢ (𝜑 → (1 σ (2↑𝐴)) = ((2↑(𝐴 + 1)) − 1))
64	63	oveq1d 6025	. . . . . . 7 ⊢ (𝜑 → ((1 σ (2↑𝐴)) · (1 σ 𝐵)) = (((2↑(𝐴 + 1)) − 1) · (1 σ 𝐵)))
65	54, 55, 64	3eqtr3d 2270	. . . . . 6 ⊢ (𝜑 → (2 · ((2↑𝐴) · 𝐵)) = (((2↑(𝐴 + 1)) − 1) · (1 σ 𝐵)))
66	37, 40, 65	3eqtrd 2266	. . . . 5 ⊢ (𝜑 → ((2↑(𝐴 + 1)) · 𝐵) = (((2↑(𝐴 + 1)) − 1) · (1 σ 𝐵)))
67	27, 66	breqtrrd 4111	. . . 4 ⊢ (𝜑 → ((2↑(𝐴 + 1)) − 1) ∥ ((2↑(𝐴 + 1)) · 𝐵))
68	20, 18	gcdcomd 12516	. . . . 5 ⊢ (𝜑 → (((2↑(𝐴 + 1)) − 1) gcd (2↑(𝐴 + 1))) = ((2↑(𝐴 + 1)) gcd ((2↑(𝐴 + 1)) − 1)))
69		iddvdsexp 12347	. . . . . . . . 9 ⊢ ((2 ∈ ℤ ∧ (𝐴 + 1) ∈ ℕ) → 2 ∥ (2↑(𝐴 + 1)))
70	49, 9, 69	sylancr 414	. . . . . . . 8 ⊢ (𝜑 → 2 ∥ (2↑(𝐴 + 1)))
71		n2dvds1 12444	. . . . . . . . . 10 ⊢ ¬ 2 ∥ 1
72	49	a1i 9	. . . . . . . . . . . 12 ⊢ (𝜑 → 2 ∈ ℤ)
73		1zzd 9489	. . . . . . . . . . . 12 ⊢ (𝜑 → 1 ∈ ℤ)
74	72, 18, 73	3jca 1201	. . . . . . . . . . 11 ⊢ (𝜑 → (2 ∈ ℤ ∧ (2↑(𝐴 + 1)) ∈ ℤ ∧ 1 ∈ ℤ))
75		dvdssub2 12367	. . . . . . . . . . 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 679	. . . . . . . . 9 ⊢ ((𝜑 ∧ 2 ∥ ((2↑(𝐴 + 1)) − 1)) → ¬ 2 ∥ (2↑(𝐴 + 1)))
78	77	ex 115	. . . . . . . 8 ⊢ (𝜑 → (2 ∥ ((2↑(𝐴 + 1)) − 1) → ¬ 2 ∥ (2↑(𝐴 + 1))))
79	70, 78	mt2d 628	. . . . . . 7 ⊢ (𝜑 → ¬ 2 ∥ ((2↑(𝐴 + 1)) − 1))
80		coprm 12687	. . . . . . . 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 12697	. . . . . . 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 1376	. . . . . 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 2262	. . . 4 ⊢ (𝜑 → (((2↑(𝐴 + 1)) − 1) gcd (2↑(𝐴 + 1))) = 1)
87		coprmdvds 12635	. . . . 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 1271	. . . 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 12328	. . . 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 1201	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 1002 = wceq 1395 ∈ wcel 2200 class class class wbr 4083 (class class class)co 6010 ℂcc 8013 ℝcr 8014 1c1 8016 + caddc 8018 · cmul 8020 < clt 8197 − cmin 8333 / cdiv 8835 ℕcn 9126 2c2 9177 ℕ₀cn0 9385 ℤcz 9462 ↑cexp 10777 ∥ cdvds 12319 gcd cgcd 12495 ℙcprime 12650 σ csgm 15676

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 4259 ax-pr 4294 ax-un 4525 ax-setind 4630 ax-iinf 4681 ax-cnex 8106 ax-resscn 8107 ax-1cn 8108 ax-1re 8109 ax-icn 8110 ax-addcl 8111 ax-addrcl 8112 ax-mulcl 8113 ax-mulrcl 8114 ax-addcom 8115 ax-mulcom 8116 ax-addass 8117 ax-mulass 8118 ax-distr 8119 ax-i2m1 8120 ax-0lt1 8121 ax-1rid 8122 ax-0id 8123 ax-rnegex 8124 ax-precex 8125 ax-cnre 8126 ax-pre-ltirr 8127 ax-pre-ltwlin 8128 ax-pre-lttrn 8129 ax-pre-apti 8130 ax-pre-ltadd 8131 ax-pre-mulgt0 8132 ax-pre-mulext 8133 ax-arch 8134 ax-caucvg 8135 ax-pre-suploc 8136 ax-addf 8137 ax-mulf 8138

This theorem depends on definitions: df-bi 117 df-stab 836 df-dc 840 df-3or 1003 df-3an 1004 df-tru 1398 df-fal 1401 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-disj 4060 df-br 4084 df-opab 4146 df-mpt 4147 df-tr 4183 df-id 4385 df-po 4388 df-iso 4389 df-iord 4458 df-on 4460 df-ilim 4461 df-suc 4463 df-iom 4684 df-xp 4726 df-rel 4727 df-cnv 4728 df-co 4729 df-dm 4730 df-rn 4731 df-res 4732 df-ima 4733 df-iota 5281 df-fun 5323 df-fn 5324 df-f 5325 df-f1 5326 df-fo 5327 df-f1o 5328 df-fv 5329 df-isom 5330 df-riota 5963 df-ov 6013 df-oprab 6014 df-mpo 6015 df-of 6227 df-1st 6295 df-2nd 6296 df-recs 6462 df-irdg 6527 df-frec 6548 df-1o 6573 df-2o 6574 df-oadd 6577 df-er 6693 df-map 6810 df-pm 6811 df-en 6901 df-dom 6902 df-fin 6903 df-sup 7167 df-inf 7168 df-pnf 8199 df-mnf 8200 df-xr 8201 df-ltxr 8202 df-le 8203 df-sub 8335 df-neg 8336 df-reap 8738 df-ap 8745 df-div 8836 df-inn 9127 df-2 9185 df-3 9186 df-4 9187 df-n0 9386 df-xnn0 9449 df-z 9463 df-uz 9739 df-q 9832 df-rp 9867 df-xneg 9985 df-xadd 9986 df-ioo 10105 df-ico 10107 df-icc 10108 df-fz 10222 df-fzo 10356 df-fl 10507 df-mod 10562 df-seqfrec 10687 df-exp 10778 df-fac 10965 df-bc 10987 df-ihash 11015 df-shft 11347 df-cj 11374 df-re 11375 df-im 11376 df-rsqrt 11530 df-abs 11531 df-clim 11811 df-sumdc 11886 df-ef 12180 df-e 12181 df-dvds 12320 df-gcd 12496 df-prm 12651 df-pc 12829 df-rest 13295 df-topgen 13314 df-psmet 14528 df-xmet 14529 df-met 14530 df-bl 14531 df-mopn 14532 df-top 14693 df-topon 14706 df-bases 14738 df-ntr 14791 df-cn 14883 df-cnp 14884 df-tx 14948 df-cncf 15266 df-limced 15351 df-dvap 15352 df-relog 15553 df-rpcxp 15554 df-sgm 15677

This theorem is referenced by: perfectlem2 15695

W3C validator