perfectlem1 - Intuitionistic Logic Explorer

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

Theorem perfectlem1 15515

Description: Lemma for perfect 15517. (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 9205	. . 3 ⊢ 2 ∈ ℕ
2		perfectlem.1	. . . . 5 ⊢ (𝜑 → 𝐴 ∈ ℕ)
3	2	nnnn0d 9355	. . . 4 ⊢ (𝜑 → 𝐴 ∈ ℕ₀)
4		peano2nn0 9342	. . . 4 ⊢ (𝐴 ∈ ℕ₀ → (𝐴 + 1) ∈ ℕ₀)
5	3, 4	syl 14	. . 3 ⊢ (𝜑 → (𝐴 + 1) ∈ ℕ₀)
6		nnexpcl 10704	. . 3 ⊢ ((2 ∈ ℕ ∧ (𝐴 + 1) ∈ ℕ₀) → (2↑(𝐴 + 1)) ∈ ℕ)
7	1, 5, 6	sylancr 414	. 2 ⊢ (𝜑 → (2↑(𝐴 + 1)) ∈ ℕ)
8		2re 9113	. . . 4 ⊢ 2 ∈ ℝ
9	2	peano2nnd 9058	. . . 4 ⊢ (𝜑 → (𝐴 + 1) ∈ ℕ)
10		1lt2 9213	. . . . 5 ⊢ 1 < 2
11	10	a1i 9	. . . 4 ⊢ (𝜑 → 1 < 2)
12		expgt1 10729	. . . 4 ⊢ ((2 ∈ ℝ ∧ (𝐴 + 1) ∈ ℕ ∧ 1 < 2) → 1 < (2↑(𝐴 + 1)))
13	8, 9, 11, 12	mp3an2i 1355	. . 3 ⊢ (𝜑 → 1 < (2↑(𝐴 + 1)))
14		1nn 9054	. . . 4 ⊢ 1 ∈ ℕ
15		nnsub 9082	. . . 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 9501	. . . . . . 7 ⊢ (𝜑 → (2↑(𝐴 + 1)) ∈ ℤ)
19		peano2zm 9417	. . . . . . 7 ⊢ ((2↑(𝐴 + 1)) ∈ ℤ → ((2↑(𝐴 + 1)) − 1) ∈ ℤ)
20	18, 19	syl 14	. . . . . 6 ⊢ (𝜑 → ((2↑(𝐴 + 1)) − 1) ∈ ℤ)
21		1nn0 9318	. . . . . . . 8 ⊢ 1 ∈ ℕ₀
22		perfectlem.2	. . . . . . . 8 ⊢ (𝜑 → 𝐵 ∈ ℕ)
23		sgmnncl 15504	. . . . . . . 8 ⊢ ((1 ∈ ℕ₀ ∧ 𝐵 ∈ ℕ) → (1 σ 𝐵) ∈ ℕ)
24	21, 22, 23	sylancr 414	. . . . . . 7 ⊢ (𝜑 → (1 σ 𝐵) ∈ ℕ)
25	24	nnzd 9501	. . . . . 6 ⊢ (𝜑 → (1 σ 𝐵) ∈ ℤ)
26		dvdsmul1 12168	. . . . . 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 9114	. . . . . . . . 9 ⊢ 2 ∈ ℂ
29		expp1 10698	. . . . . . . . 9 ⊢ ((2 ∈ ℂ ∧ 𝐴 ∈ ℕ₀) → (2↑(𝐴 + 1)) = ((2↑𝐴) · 2))
30	28, 3, 29	sylancr 414	. . . . . . . 8 ⊢ (𝜑 → (2↑(𝐴 + 1)) = ((2↑𝐴) · 2))
31		nnexpcl 10704	. . . . . . . . . . 11 ⊢ ((2 ∈ ℕ ∧ 𝐴 ∈ ℕ₀) → (2↑𝐴) ∈ ℕ)
32	1, 3, 31	sylancr 414	. . . . . . . . . 10 ⊢ (𝜑 → (2↑𝐴) ∈ ℕ)
33	32	nncnd 9057	. . . . . . . . 9 ⊢ (𝜑 → (2↑𝐴) ∈ ℂ)
34		mulcom 8061	. . . . . . . . 9 ⊢ (((2↑𝐴) ∈ ℂ ∧ 2 ∈ ℂ) → ((2↑𝐴) · 2) = (2 · (2↑𝐴)))
35	33, 28, 34	sylancl 413	. . . . . . . 8 ⊢ (𝜑 → ((2↑𝐴) · 2) = (2 · (2↑𝐴)))
36	30, 35	eqtrd 2239	. . . . . . 7 ⊢ (𝜑 → (2↑(𝐴 + 1)) = (2 · (2↑𝐴)))
37	36	oveq1d 5966	. . . . . 6 ⊢ (𝜑 → ((2↑(𝐴 + 1)) · 𝐵) = ((2 · (2↑𝐴)) · 𝐵))
38	28	a1i 9	. . . . . . 7 ⊢ (𝜑 → 2 ∈ ℂ)
39	22	nncnd 9057	. . . . . . 7 ⊢ (𝜑 → 𝐵 ∈ ℂ)
40	38, 33, 39	mulassd 8103	. . . . . 6 ⊢ (𝜑 → ((2 · (2↑𝐴)) · 𝐵) = (2 · ((2↑𝐴) · 𝐵)))
41		ax-1cn 8025	. . . . . . . . 9 ⊢ 1 ∈ ℂ
42	41	a1i 9	. . . . . . . 8 ⊢ (𝜑 → 1 ∈ ℂ)
43		perfectlem.3	. . . . . . . . . 10 ⊢ (𝜑 → ¬ 2 ∥ 𝐵)
44		2prm 12493	. . . . . . . . . . 11 ⊢ 2 ∈ ℙ
45	22	nnzd 9501	. . . . . . . . . . 11 ⊢ (𝜑 → 𝐵 ∈ ℤ)
46		coprm 12510	. . . . . . . . . . 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 9407	. . . . . . . . . 10 ⊢ 2 ∈ ℤ
50		rpexp1i 12520	. . . . . . . . . 10 ⊢ ((2 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐴 ∈ ℕ₀) → ((2 gcd 𝐵) = 1 → ((2↑𝐴) gcd 𝐵) = 1))
51	49, 45, 3, 50	mp3an2i 1355	. . . . . . . . 9 ⊢ (𝜑 → ((2 gcd 𝐵) = 1 → ((2↑𝐴) gcd 𝐵) = 1))
52	48, 51	mpd 13	. . . . . . . 8 ⊢ (𝜑 → ((2↑𝐴) gcd 𝐵) = 1)
53		sgmmul 15512	. . . . . . . 8 ⊢ ((1 ∈ ℂ ∧ ((2↑𝐴) ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ ((2↑𝐴) gcd 𝐵) = 1)) → (1 σ ((2↑𝐴) · 𝐵)) = ((1 σ (2↑𝐴)) · (1 σ 𝐵)))
54	42, 32, 22, 52, 53	syl13anc 1252	. . . . . . 7 ⊢ (𝜑 → (1 σ ((2↑𝐴) · 𝐵)) = ((1 σ (2↑𝐴)) · (1 σ 𝐵)))
55		perfectlem.4	. . . . . . 7 ⊢ (𝜑 → (1 σ ((2↑𝐴) · 𝐵)) = (2 · ((2↑𝐴) · 𝐵)))
56	2	nncnd 9057	. . . . . . . . . . . 12 ⊢ (𝜑 → 𝐴 ∈ ℂ)
57		pncan 8285	. . . . . . . . . . . 12 ⊢ ((𝐴 ∈ ℂ ∧ 1 ∈ ℂ) → ((𝐴 + 1) − 1) = 𝐴)
58	56, 41, 57	sylancl 413	. . . . . . . . . . 11 ⊢ (𝜑 → ((𝐴 + 1) − 1) = 𝐴)
59	58	oveq2d 5967	. . . . . . . . . 10 ⊢ (𝜑 → (2↑((𝐴 + 1) − 1)) = (2↑𝐴))
60	59	oveq2d 5967	. . . . . . . . 9 ⊢ (𝜑 → (1 σ (2↑((𝐴 + 1) − 1))) = (1 σ (2↑𝐴)))
61		1sgm2ppw 15511	. . . . . . . . . 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 2241	. . . . . . . 8 ⊢ (𝜑 → (1 σ (2↑𝐴)) = ((2↑(𝐴 + 1)) − 1))
64	63	oveq1d 5966	. . . . . . 7 ⊢ (𝜑 → ((1 σ (2↑𝐴)) · (1 σ 𝐵)) = (((2↑(𝐴 + 1)) − 1) · (1 σ 𝐵)))
65	54, 55, 64	3eqtr3d 2247	. . . . . 6 ⊢ (𝜑 → (2 · ((2↑𝐴) · 𝐵)) = (((2↑(𝐴 + 1)) − 1) · (1 σ 𝐵)))
66	37, 40, 65	3eqtrd 2243	. . . . 5 ⊢ (𝜑 → ((2↑(𝐴 + 1)) · 𝐵) = (((2↑(𝐴 + 1)) − 1) · (1 σ 𝐵)))
67	27, 66	breqtrrd 4075	. . . 4 ⊢ (𝜑 → ((2↑(𝐴 + 1)) − 1) ∥ ((2↑(𝐴 + 1)) · 𝐵))
68	20, 18	gcdcomd 12339	. . . . 5 ⊢ (𝜑 → (((2↑(𝐴 + 1)) − 1) gcd (2↑(𝐴 + 1))) = ((2↑(𝐴 + 1)) gcd ((2↑(𝐴 + 1)) − 1)))
69		iddvdsexp 12170	. . . . . . . . 9 ⊢ ((2 ∈ ℤ ∧ (𝐴 + 1) ∈ ℕ) → 2 ∥ (2↑(𝐴 + 1)))
70	49, 9, 69	sylancr 414	. . . . . . . 8 ⊢ (𝜑 → 2 ∥ (2↑(𝐴 + 1)))
71		n2dvds1 12267	. . . . . . . . . 10 ⊢ ¬ 2 ∥ 1
72	49	a1i 9	. . . . . . . . . . . 12 ⊢ (𝜑 → 2 ∈ ℤ)
73		1zzd 9406	. . . . . . . . . . . 12 ⊢ (𝜑 → 1 ∈ ℤ)
74	72, 18, 73	3jca 1180	. . . . . . . . . . 11 ⊢ (𝜑 → (2 ∈ ℤ ∧ (2↑(𝐴 + 1)) ∈ ℤ ∧ 1 ∈ ℤ))
75		dvdssub2 12190	. . . . . . . . . . 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 677	. . . . . . . . 9 ⊢ ((𝜑 ∧ 2 ∥ ((2↑(𝐴 + 1)) − 1)) → ¬ 2 ∥ (2↑(𝐴 + 1)))
78	77	ex 115	. . . . . . . 8 ⊢ (𝜑 → (2 ∥ ((2↑(𝐴 + 1)) − 1) → ¬ 2 ∥ (2↑(𝐴 + 1))))
79	70, 78	mt2d 626	. . . . . . 7 ⊢ (𝜑 → ¬ 2 ∥ ((2↑(𝐴 + 1)) − 1))
80		coprm 12510	. . . . . . . 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 12520	. . . . . . 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 1355	. . . . . 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 2239	. . . 4 ⊢ (𝜑 → (((2↑(𝐴 + 1)) − 1) gcd (2↑(𝐴 + 1))) = 1)
87		coprmdvds 12458	. . . . 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 1250	. . . 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 12151	. . . 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 1180	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 981 = wceq 1373 ∈ wcel 2177 class class class wbr 4047 (class class class)co 5951 ℂcc 7930 ℝcr 7931 1c1 7933 + caddc 7935 · cmul 7937 < clt 8114 − cmin 8250 / cdiv 8752 ℕcn 9043 2c2 9094 ℕ₀cn0 9302 ℤcz 9379 ↑cexp 10690 ∥ cdvds 12142 gcd cgcd 12318 ℙcprime 12473 σ csgm 15497

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 615 ax-in2 616 ax-io 711 ax-5 1471 ax-7 1472 ax-gen 1473 ax-ie1 1517 ax-ie2 1518 ax-8 1528 ax-10 1529 ax-11 1530 ax-i12 1531 ax-bndl 1533 ax-4 1534 ax-17 1550 ax-i9 1554 ax-ial 1558 ax-i5r 1559 ax-13 2179 ax-14 2180 ax-ext 2188 ax-coll 4163 ax-sep 4166 ax-nul 4174 ax-pow 4222 ax-pr 4257 ax-un 4484 ax-setind 4589 ax-iinf 4640 ax-cnex 8023 ax-resscn 8024 ax-1cn 8025 ax-1re 8026 ax-icn 8027 ax-addcl 8028 ax-addrcl 8029 ax-mulcl 8030 ax-mulrcl 8031 ax-addcom 8032 ax-mulcom 8033 ax-addass 8034 ax-mulass 8035 ax-distr 8036 ax-i2m1 8037 ax-0lt1 8038 ax-1rid 8039 ax-0id 8040 ax-rnegex 8041 ax-precex 8042 ax-cnre 8043 ax-pre-ltirr 8044 ax-pre-ltwlin 8045 ax-pre-lttrn 8046 ax-pre-apti 8047 ax-pre-ltadd 8048 ax-pre-mulgt0 8049 ax-pre-mulext 8050 ax-arch 8051 ax-caucvg 8052 ax-pre-suploc 8053 ax-addf 8054 ax-mulf 8055

This theorem depends on definitions: df-bi 117 df-stab 833 df-dc 837 df-3or 982 df-3an 983 df-tru 1376 df-fal 1379 df-nf 1485 df-sb 1787 df-eu 2058 df-mo 2059 df-clab 2193 df-cleq 2199 df-clel 2202 df-nfc 2338 df-ne 2378 df-nel 2473 df-ral 2490 df-rex 2491 df-reu 2492 df-rmo 2493 df-rab 2494 df-v 2775 df-sbc 3000 df-csb 3095 df-dif 3169 df-un 3171 df-in 3173 df-ss 3180 df-nul 3462 df-if 3573 df-pw 3619 df-sn 3640 df-pr 3641 df-op 3643 df-uni 3853 df-int 3888 df-iun 3931 df-disj 4024 df-br 4048 df-opab 4110 df-mpt 4111 df-tr 4147 df-id 4344 df-po 4347 df-iso 4348 df-iord 4417 df-on 4419 df-ilim 4420 df-suc 4422 df-iom 4643 df-xp 4685 df-rel 4686 df-cnv 4687 df-co 4688 df-dm 4689 df-rn 4690 df-res 4691 df-ima 4692 df-iota 5237 df-fun 5278 df-fn 5279 df-f 5280 df-f1 5281 df-fo 5282 df-f1o 5283 df-fv 5284 df-isom 5285 df-riota 5906 df-ov 5954 df-oprab 5955 df-mpo 5956 df-of 6165 df-1st 6233 df-2nd 6234 df-recs 6398 df-irdg 6463 df-frec 6484 df-1o 6509 df-2o 6510 df-oadd 6513 df-er 6627 df-map 6744 df-pm 6745 df-en 6835 df-dom 6836 df-fin 6837 df-sup 7093 df-inf 7094 df-pnf 8116 df-mnf 8117 df-xr 8118 df-ltxr 8119 df-le 8120 df-sub 8252 df-neg 8253 df-reap 8655 df-ap 8662 df-div 8753 df-inn 9044 df-2 9102 df-3 9103 df-4 9104 df-n0 9303 df-xnn0 9366 df-z 9380 df-uz 9656 df-q 9748 df-rp 9783 df-xneg 9901 df-xadd 9902 df-ioo 10021 df-ico 10023 df-icc 10024 df-fz 10138 df-fzo 10272 df-fl 10420 df-mod 10475 df-seqfrec 10600 df-exp 10691 df-fac 10878 df-bc 10900 df-ihash 10928 df-shft 11170 df-cj 11197 df-re 11198 df-im 11199 df-rsqrt 11353 df-abs 11354 df-clim 11634 df-sumdc 11709 df-ef 12003 df-e 12004 df-dvds 12143 df-gcd 12319 df-prm 12474 df-pc 12652 df-rest 13117 df-topgen 13136 df-psmet 14349 df-xmet 14350 df-met 14351 df-bl 14352 df-mopn 14353 df-top 14514 df-topon 14527 df-bases 14559 df-ntr 14612 df-cn 14704 df-cnp 14705 df-tx 14769 df-cncf 15087 df-limced 15172 df-dvap 15173 df-relog 15374 df-rpcxp 15375 df-sgm 15498

This theorem is referenced by: perfectlem2 15516

W3C validator