Step | Hyp | Ref
| Expression |
1 | | nprmdvds1 15256 |
. . . . . . 7
⊢ (𝑝 ∈ ℙ → ¬
𝑝 ∥
1) |
2 | 1 | adantl 481 |
. . . . . 6
⊢ ((𝜑 ∧ 𝑝 ∈ ℙ) → ¬ 𝑝 ∥ 1) |
3 | | ablfacrp.1 |
. . . . . . . 8
⊢ (𝜑 → (𝑀 gcd 𝑁) = 1) |
4 | 3 | adantr 480 |
. . . . . . 7
⊢ ((𝜑 ∧ 𝑝 ∈ ℙ) → (𝑀 gcd 𝑁) = 1) |
5 | 4 | breq2d 4595 |
. . . . . 6
⊢ ((𝜑 ∧ 𝑝 ∈ ℙ) → (𝑝 ∥ (𝑀 gcd 𝑁) ↔ 𝑝 ∥ 1)) |
6 | 2, 5 | mtbird 314 |
. . . . 5
⊢ ((𝜑 ∧ 𝑝 ∈ ℙ) → ¬ 𝑝 ∥ (𝑀 gcd 𝑁)) |
7 | | ablfacrp.k |
. . . . . . . . . . . . . 14
⊢ 𝐾 = {𝑥 ∈ 𝐵 ∣ (𝑂‘𝑥) ∥ 𝑀} |
8 | | ablfacrp.g |
. . . . . . . . . . . . . . 15
⊢ (𝜑 → 𝐺 ∈ Abel) |
9 | | ablfacrp.m |
. . . . . . . . . . . . . . . 16
⊢ (𝜑 → 𝑀 ∈ ℕ) |
10 | 9 | nnzd 11357 |
. . . . . . . . . . . . . . 15
⊢ (𝜑 → 𝑀 ∈ ℤ) |
11 | | ablfacrp.o |
. . . . . . . . . . . . . . . 16
⊢ 𝑂 = (od‘𝐺) |
12 | | ablfacrp.b |
. . . . . . . . . . . . . . . 16
⊢ 𝐵 = (Base‘𝐺) |
13 | 11, 12 | oddvdssubg 18081 |
. . . . . . . . . . . . . . 15
⊢ ((𝐺 ∈ Abel ∧ 𝑀 ∈ ℤ) → {𝑥 ∈ 𝐵 ∣ (𝑂‘𝑥) ∥ 𝑀} ∈ (SubGrp‘𝐺)) |
14 | 8, 10, 13 | syl2anc 691 |
. . . . . . . . . . . . . 14
⊢ (𝜑 → {𝑥 ∈ 𝐵 ∣ (𝑂‘𝑥) ∥ 𝑀} ∈ (SubGrp‘𝐺)) |
15 | 7, 14 | syl5eqel 2692 |
. . . . . . . . . . . . 13
⊢ (𝜑 → 𝐾 ∈ (SubGrp‘𝐺)) |
16 | 15 | ad2antrr 758 |
. . . . . . . . . . . 12
⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ (#‘𝐾)) → 𝐾 ∈ (SubGrp‘𝐺)) |
17 | | eqid 2610 |
. . . . . . . . . . . . 13
⊢ (𝐺 ↾s 𝐾) = (𝐺 ↾s 𝐾) |
18 | 17 | subggrp 17420 |
. . . . . . . . . . . 12
⊢ (𝐾 ∈ (SubGrp‘𝐺) → (𝐺 ↾s 𝐾) ∈ Grp) |
19 | 16, 18 | syl 17 |
. . . . . . . . . . 11
⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ (#‘𝐾)) → (𝐺 ↾s 𝐾) ∈ Grp) |
20 | 17 | subgbas 17421 |
. . . . . . . . . . . . 13
⊢ (𝐾 ∈ (SubGrp‘𝐺) → 𝐾 = (Base‘(𝐺 ↾s 𝐾))) |
21 | 16, 20 | syl 17 |
. . . . . . . . . . . 12
⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ (#‘𝐾)) → 𝐾 = (Base‘(𝐺 ↾s 𝐾))) |
22 | | ablfacrp.2 |
. . . . . . . . . . . . . . . 16
⊢ (𝜑 → (#‘𝐵) = (𝑀 · 𝑁)) |
23 | 9 | nnnn0d 11228 |
. . . . . . . . . . . . . . . . 17
⊢ (𝜑 → 𝑀 ∈
ℕ0) |
24 | | ablfacrp.n |
. . . . . . . . . . . . . . . . . 18
⊢ (𝜑 → 𝑁 ∈ ℕ) |
25 | 24 | nnnn0d 11228 |
. . . . . . . . . . . . . . . . 17
⊢ (𝜑 → 𝑁 ∈
ℕ0) |
26 | 23, 25 | nn0mulcld 11233 |
. . . . . . . . . . . . . . . 16
⊢ (𝜑 → (𝑀 · 𝑁) ∈
ℕ0) |
27 | 22, 26 | eqeltrd 2688 |
. . . . . . . . . . . . . . 15
⊢ (𝜑 → (#‘𝐵) ∈
ℕ0) |
28 | | fvex 6113 |
. . . . . . . . . . . . . . . . 17
⊢
(Base‘𝐺)
∈ V |
29 | 12, 28 | eqeltri 2684 |
. . . . . . . . . . . . . . . 16
⊢ 𝐵 ∈ V |
30 | | hashclb 13011 |
. . . . . . . . . . . . . . . 16
⊢ (𝐵 ∈ V → (𝐵 ∈ Fin ↔
(#‘𝐵) ∈
ℕ0)) |
31 | 29, 30 | ax-mp 5 |
. . . . . . . . . . . . . . 15
⊢ (𝐵 ∈ Fin ↔
(#‘𝐵) ∈
ℕ0) |
32 | 27, 31 | sylibr 223 |
. . . . . . . . . . . . . 14
⊢ (𝜑 → 𝐵 ∈ Fin) |
33 | | ssrab2 3650 |
. . . . . . . . . . . . . . 15
⊢ {𝑥 ∈ 𝐵 ∣ (𝑂‘𝑥) ∥ 𝑀} ⊆ 𝐵 |
34 | 7, 33 | eqsstri 3598 |
. . . . . . . . . . . . . 14
⊢ 𝐾 ⊆ 𝐵 |
35 | | ssfi 8065 |
. . . . . . . . . . . . . 14
⊢ ((𝐵 ∈ Fin ∧ 𝐾 ⊆ 𝐵) → 𝐾 ∈ Fin) |
36 | 32, 34, 35 | sylancl 693 |
. . . . . . . . . . . . 13
⊢ (𝜑 → 𝐾 ∈ Fin) |
37 | 36 | ad2antrr 758 |
. . . . . . . . . . . 12
⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ (#‘𝐾)) → 𝐾 ∈ Fin) |
38 | 21, 37 | eqeltrrd 2689 |
. . . . . . . . . . 11
⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ (#‘𝐾)) → (Base‘(𝐺 ↾s 𝐾)) ∈ Fin) |
39 | | simplr 788 |
. . . . . . . . . . 11
⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ (#‘𝐾)) → 𝑝 ∈ ℙ) |
40 | | simpr 476 |
. . . . . . . . . . . 12
⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ (#‘𝐾)) → 𝑝 ∥ (#‘𝐾)) |
41 | 21 | fveq2d 6107 |
. . . . . . . . . . . 12
⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ (#‘𝐾)) → (#‘𝐾) = (#‘(Base‘(𝐺 ↾s 𝐾)))) |
42 | 40, 41 | breqtrd 4609 |
. . . . . . . . . . 11
⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ (#‘𝐾)) → 𝑝 ∥ (#‘(Base‘(𝐺 ↾s 𝐾)))) |
43 | | eqid 2610 |
. . . . . . . . . . . 12
⊢
(Base‘(𝐺
↾s 𝐾)) =
(Base‘(𝐺
↾s 𝐾)) |
44 | | eqid 2610 |
. . . . . . . . . . . 12
⊢
(od‘(𝐺
↾s 𝐾)) =
(od‘(𝐺
↾s 𝐾)) |
45 | 43, 44 | odcau 17842 |
. . . . . . . . . . 11
⊢ ((((𝐺 ↾s 𝐾) ∈ Grp ∧
(Base‘(𝐺
↾s 𝐾))
∈ Fin ∧ 𝑝 ∈
ℙ) ∧ 𝑝 ∥
(#‘(Base‘(𝐺
↾s 𝐾))))
→ ∃𝑔 ∈
(Base‘(𝐺
↾s 𝐾))((od‘(𝐺 ↾s 𝐾))‘𝑔) = 𝑝) |
46 | 19, 38, 39, 42, 45 | syl31anc 1321 |
. . . . . . . . . 10
⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ (#‘𝐾)) → ∃𝑔 ∈ (Base‘(𝐺 ↾s 𝐾))((od‘(𝐺 ↾s 𝐾))‘𝑔) = 𝑝) |
47 | 21 | rexeqdv 3122 |
. . . . . . . . . 10
⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ (#‘𝐾)) → (∃𝑔 ∈ 𝐾 ((od‘(𝐺 ↾s 𝐾))‘𝑔) = 𝑝 ↔ ∃𝑔 ∈ (Base‘(𝐺 ↾s 𝐾))((od‘(𝐺 ↾s 𝐾))‘𝑔) = 𝑝)) |
48 | 46, 47 | mpbird 246 |
. . . . . . . . 9
⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ (#‘𝐾)) → ∃𝑔 ∈ 𝐾 ((od‘(𝐺 ↾s 𝐾))‘𝑔) = 𝑝) |
49 | 17, 11, 44 | subgod 17808 |
. . . . . . . . . . . . 13
⊢ ((𝐾 ∈ (SubGrp‘𝐺) ∧ 𝑔 ∈ 𝐾) → (𝑂‘𝑔) = ((od‘(𝐺 ↾s 𝐾))‘𝑔)) |
50 | 16, 49 | sylan 487 |
. . . . . . . . . . . 12
⊢ ((((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ (#‘𝐾)) ∧ 𝑔 ∈ 𝐾) → (𝑂‘𝑔) = ((od‘(𝐺 ↾s 𝐾))‘𝑔)) |
51 | | fveq2 6103 |
. . . . . . . . . . . . . . . 16
⊢ (𝑥 = 𝑔 → (𝑂‘𝑥) = (𝑂‘𝑔)) |
52 | 51 | breq1d 4593 |
. . . . . . . . . . . . . . 15
⊢ (𝑥 = 𝑔 → ((𝑂‘𝑥) ∥ 𝑀 ↔ (𝑂‘𝑔) ∥ 𝑀)) |
53 | 52, 7 | elrab2 3333 |
. . . . . . . . . . . . . 14
⊢ (𝑔 ∈ 𝐾 ↔ (𝑔 ∈ 𝐵 ∧ (𝑂‘𝑔) ∥ 𝑀)) |
54 | 53 | simprbi 479 |
. . . . . . . . . . . . 13
⊢ (𝑔 ∈ 𝐾 → (𝑂‘𝑔) ∥ 𝑀) |
55 | 54 | adantl 481 |
. . . . . . . . . . . 12
⊢ ((((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ (#‘𝐾)) ∧ 𝑔 ∈ 𝐾) → (𝑂‘𝑔) ∥ 𝑀) |
56 | 50, 55 | eqbrtrrd 4607 |
. . . . . . . . . . 11
⊢ ((((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ (#‘𝐾)) ∧ 𝑔 ∈ 𝐾) → ((od‘(𝐺 ↾s 𝐾))‘𝑔) ∥ 𝑀) |
57 | | breq1 4586 |
. . . . . . . . . . 11
⊢
(((od‘(𝐺
↾s 𝐾))‘𝑔) = 𝑝 → (((od‘(𝐺 ↾s 𝐾))‘𝑔) ∥ 𝑀 ↔ 𝑝 ∥ 𝑀)) |
58 | 56, 57 | syl5ibcom 234 |
. . . . . . . . . 10
⊢ ((((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ (#‘𝐾)) ∧ 𝑔 ∈ 𝐾) → (((od‘(𝐺 ↾s 𝐾))‘𝑔) = 𝑝 → 𝑝 ∥ 𝑀)) |
59 | 58 | rexlimdva 3013 |
. . . . . . . . 9
⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ (#‘𝐾)) → (∃𝑔 ∈ 𝐾 ((od‘(𝐺 ↾s 𝐾))‘𝑔) = 𝑝 → 𝑝 ∥ 𝑀)) |
60 | 48, 59 | mpd 15 |
. . . . . . . 8
⊢ (((𝜑 ∧ 𝑝 ∈ ℙ) ∧ 𝑝 ∥ (#‘𝐾)) → 𝑝 ∥ 𝑀) |
61 | 60 | ex 449 |
. . . . . . 7
⊢ ((𝜑 ∧ 𝑝 ∈ ℙ) → (𝑝 ∥ (#‘𝐾) → 𝑝 ∥ 𝑀)) |
62 | 61 | anim1d 586 |
. . . . . 6
⊢ ((𝜑 ∧ 𝑝 ∈ ℙ) → ((𝑝 ∥ (#‘𝐾) ∧ 𝑝 ∥ 𝑁) → (𝑝 ∥ 𝑀 ∧ 𝑝 ∥ 𝑁))) |
63 | | prmz 15227 |
. . . . . . . 8
⊢ (𝑝 ∈ ℙ → 𝑝 ∈
ℤ) |
64 | 63 | adantl 481 |
. . . . . . 7
⊢ ((𝜑 ∧ 𝑝 ∈ ℙ) → 𝑝 ∈ ℤ) |
65 | | hashcl 13009 |
. . . . . . . . . 10
⊢ (𝐾 ∈ Fin →
(#‘𝐾) ∈
ℕ0) |
66 | 36, 65 | syl 17 |
. . . . . . . . 9
⊢ (𝜑 → (#‘𝐾) ∈
ℕ0) |
67 | 66 | nn0zd 11356 |
. . . . . . . 8
⊢ (𝜑 → (#‘𝐾) ∈ ℤ) |
68 | 67 | adantr 480 |
. . . . . . 7
⊢ ((𝜑 ∧ 𝑝 ∈ ℙ) → (#‘𝐾) ∈
ℤ) |
69 | 24 | nnzd 11357 |
. . . . . . . 8
⊢ (𝜑 → 𝑁 ∈ ℤ) |
70 | 69 | adantr 480 |
. . . . . . 7
⊢ ((𝜑 ∧ 𝑝 ∈ ℙ) → 𝑁 ∈ ℤ) |
71 | | dvdsgcdb 15100 |
. . . . . . 7
⊢ ((𝑝 ∈ ℤ ∧
(#‘𝐾) ∈ ℤ
∧ 𝑁 ∈ ℤ)
→ ((𝑝 ∥
(#‘𝐾) ∧ 𝑝 ∥ 𝑁) ↔ 𝑝 ∥ ((#‘𝐾) gcd 𝑁))) |
72 | 64, 68, 70, 71 | syl3anc 1318 |
. . . . . 6
⊢ ((𝜑 ∧ 𝑝 ∈ ℙ) → ((𝑝 ∥ (#‘𝐾) ∧ 𝑝 ∥ 𝑁) ↔ 𝑝 ∥ ((#‘𝐾) gcd 𝑁))) |
73 | 10 | adantr 480 |
. . . . . . 7
⊢ ((𝜑 ∧ 𝑝 ∈ ℙ) → 𝑀 ∈ ℤ) |
74 | | dvdsgcdb 15100 |
. . . . . . 7
⊢ ((𝑝 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → ((𝑝 ∥ 𝑀 ∧ 𝑝 ∥ 𝑁) ↔ 𝑝 ∥ (𝑀 gcd 𝑁))) |
75 | 64, 73, 70, 74 | syl3anc 1318 |
. . . . . 6
⊢ ((𝜑 ∧ 𝑝 ∈ ℙ) → ((𝑝 ∥ 𝑀 ∧ 𝑝 ∥ 𝑁) ↔ 𝑝 ∥ (𝑀 gcd 𝑁))) |
76 | 62, 72, 75 | 3imtr3d 281 |
. . . . 5
⊢ ((𝜑 ∧ 𝑝 ∈ ℙ) → (𝑝 ∥ ((#‘𝐾) gcd 𝑁) → 𝑝 ∥ (𝑀 gcd 𝑁))) |
77 | 6, 76 | mtod 188 |
. . . 4
⊢ ((𝜑 ∧ 𝑝 ∈ ℙ) → ¬ 𝑝 ∥ ((#‘𝐾) gcd 𝑁)) |
78 | 77 | nrexdv 2984 |
. . 3
⊢ (𝜑 → ¬ ∃𝑝 ∈ ℙ 𝑝 ∥ ((#‘𝐾) gcd 𝑁)) |
79 | | exprmfct 15254 |
. . 3
⊢
(((#‘𝐾) gcd
𝑁) ∈
(ℤ≥‘2) → ∃𝑝 ∈ ℙ 𝑝 ∥ ((#‘𝐾) gcd 𝑁)) |
80 | 78, 79 | nsyl 134 |
. 2
⊢ (𝜑 → ¬ ((#‘𝐾) gcd 𝑁) ∈
(ℤ≥‘2)) |
81 | 24 | nnne0d 10942 |
. . . . . 6
⊢ (𝜑 → 𝑁 ≠ 0) |
82 | | simpr 476 |
. . . . . . 7
⊢
(((#‘𝐾) = 0
∧ 𝑁 = 0) → 𝑁 = 0) |
83 | 82 | necon3ai 2807 |
. . . . . 6
⊢ (𝑁 ≠ 0 → ¬
((#‘𝐾) = 0 ∧
𝑁 = 0)) |
84 | 81, 83 | syl 17 |
. . . . 5
⊢ (𝜑 → ¬ ((#‘𝐾) = 0 ∧ 𝑁 = 0)) |
85 | | gcdn0cl 15062 |
. . . . 5
⊢
((((#‘𝐾)
∈ ℤ ∧ 𝑁
∈ ℤ) ∧ ¬ ((#‘𝐾) = 0 ∧ 𝑁 = 0)) → ((#‘𝐾) gcd 𝑁) ∈ ℕ) |
86 | 67, 69, 84, 85 | syl21anc 1317 |
. . . 4
⊢ (𝜑 → ((#‘𝐾) gcd 𝑁) ∈ ℕ) |
87 | | elnn1uz2 11641 |
. . . 4
⊢
(((#‘𝐾) gcd
𝑁) ∈ ℕ ↔
(((#‘𝐾) gcd 𝑁) = 1 ∨ ((#‘𝐾) gcd 𝑁) ∈
(ℤ≥‘2))) |
88 | 86, 87 | sylib 207 |
. . 3
⊢ (𝜑 → (((#‘𝐾) gcd 𝑁) = 1 ∨ ((#‘𝐾) gcd 𝑁) ∈
(ℤ≥‘2))) |
89 | 88 | ord 391 |
. 2
⊢ (𝜑 → (¬ ((#‘𝐾) gcd 𝑁) = 1 → ((#‘𝐾) gcd 𝑁) ∈
(ℤ≥‘2))) |
90 | 80, 89 | mt3d 139 |
1
⊢ (𝜑 → ((#‘𝐾) gcd 𝑁) = 1) |