Step | Hyp | Ref
| Expression |
1 | | ncoprmgcdgt1b 15364 |
. . . 4
⊢ ((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ) →
(∃𝑖 ∈
(ℤ≥‘2)(𝑖 ∥ 𝐴 ∧ 𝑖 ∥ 𝐵) ↔ 1 < (𝐴 gcd 𝐵))) |
2 | 1 | bicomd 213 |
. . 3
⊢ ((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ) → (1 <
(𝐴 gcd 𝐵) ↔ ∃𝑖 ∈
(ℤ≥‘2)(𝑖 ∥ 𝐴 ∧ 𝑖 ∥ 𝐵))) |
3 | 2 | 3adant3 1081 |
. 2
⊢ ((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) → (1 < (𝐴 gcd 𝐵) ↔ ∃𝑖 ∈
(ℤ≥‘2)(𝑖 ∥ 𝐴 ∧ 𝑖 ∥ 𝐵))) |
4 | | simp1 1061 |
. . . . . . . . . . . . . 14
⊢ ((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) → 𝐴 ∈ ℕ) |
5 | | eluzelz 11697 |
. . . . . . . . . . . . . 14
⊢ (𝑖 ∈
(ℤ≥‘2) → 𝑖 ∈ ℤ) |
6 | 4, 5 | anim12ci 591 |
. . . . . . . . . . . . 13
⊢ (((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) ∧ 𝑖 ∈ (ℤ≥‘2))
→ (𝑖 ∈ ℤ
∧ 𝐴 ∈
ℕ)) |
7 | | dvdsle 15032 |
. . . . . . . . . . . . 13
⊢ ((𝑖 ∈ ℤ ∧ 𝐴 ∈ ℕ) → (𝑖 ∥ 𝐴 → 𝑖 ≤ 𝐴)) |
8 | 6, 7 | syl 17 |
. . . . . . . . . . . 12
⊢ (((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) ∧ 𝑖 ∈ (ℤ≥‘2))
→ (𝑖 ∥ 𝐴 → 𝑖 ≤ 𝐴)) |
9 | | nnre 11027 |
. . . . . . . . . . . . . . . . . . . . . 22
⊢ (𝐴 ∈ ℕ → 𝐴 ∈
ℝ) |
10 | | nnre 11027 |
. . . . . . . . . . . . . . . . . . . . . 22
⊢ (𝐵 ∈ ℕ → 𝐵 ∈
ℝ) |
11 | | eluzelre 11698 |
. . . . . . . . . . . . . . . . . . . . . 22
⊢ (𝑖 ∈
(ℤ≥‘2) → 𝑖 ∈ ℝ) |
12 | 9, 10, 11 | 3anim123i 1247 |
. . . . . . . . . . . . . . . . . . . . 21
⊢ ((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝑖 ∈
(ℤ≥‘2)) → (𝐴 ∈ ℝ ∧ 𝐵 ∈ ℝ ∧ 𝑖 ∈ ℝ)) |
13 | | 3anrot 1043 |
. . . . . . . . . . . . . . . . . . . . 21
⊢ ((𝑖 ∈ ℝ ∧ 𝐴 ∈ ℝ ∧ 𝐵 ∈ ℝ) ↔ (𝐴 ∈ ℝ ∧ 𝐵 ∈ ℝ ∧ 𝑖 ∈
ℝ)) |
14 | 12, 13 | sylibr 224 |
. . . . . . . . . . . . . . . . . . . 20
⊢ ((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝑖 ∈
(ℤ≥‘2)) → (𝑖 ∈ ℝ ∧ 𝐴 ∈ ℝ ∧ 𝐵 ∈ ℝ)) |
15 | | lelttr 10128 |
. . . . . . . . . . . . . . . . . . . 20
⊢ ((𝑖 ∈ ℝ ∧ 𝐴 ∈ ℝ ∧ 𝐵 ∈ ℝ) → ((𝑖 ≤ 𝐴 ∧ 𝐴 < 𝐵) → 𝑖 < 𝐵)) |
16 | 14, 15 | syl 17 |
. . . . . . . . . . . . . . . . . . 19
⊢ ((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝑖 ∈
(ℤ≥‘2)) → ((𝑖 ≤ 𝐴 ∧ 𝐴 < 𝐵) → 𝑖 < 𝐵)) |
17 | 16 | expcomd 454 |
. . . . . . . . . . . . . . . . . 18
⊢ ((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝑖 ∈
(ℤ≥‘2)) → (𝐴 < 𝐵 → (𝑖 ≤ 𝐴 → 𝑖 < 𝐵))) |
18 | 17 | 3exp 1264 |
. . . . . . . . . . . . . . . . 17
⊢ (𝐴 ∈ ℕ → (𝐵 ∈ ℕ → (𝑖 ∈
(ℤ≥‘2) → (𝐴 < 𝐵 → (𝑖 ≤ 𝐴 → 𝑖 < 𝐵))))) |
19 | 18 | com34 91 |
. . . . . . . . . . . . . . . 16
⊢ (𝐴 ∈ ℕ → (𝐵 ∈ ℕ → (𝐴 < 𝐵 → (𝑖 ∈ (ℤ≥‘2)
→ (𝑖 ≤ 𝐴 → 𝑖 < 𝐵))))) |
20 | 19 | 3imp1 1280 |
. . . . . . . . . . . . . . 15
⊢ (((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) ∧ 𝑖 ∈ (ℤ≥‘2))
→ (𝑖 ≤ 𝐴 → 𝑖 < 𝐵)) |
21 | 20 | imp 445 |
. . . . . . . . . . . . . 14
⊢ ((((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) ∧ 𝑖 ∈ (ℤ≥‘2))
∧ 𝑖 ≤ 𝐴) → 𝑖 < 𝐵) |
22 | | nnz 11399 |
. . . . . . . . . . . . . . . . . 18
⊢ (𝐵 ∈ ℕ → 𝐵 ∈
ℤ) |
23 | 22 | 3ad2ant2 1083 |
. . . . . . . . . . . . . . . . 17
⊢ ((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) → 𝐵 ∈ ℤ) |
24 | 23, 5 | anim12ci 591 |
. . . . . . . . . . . . . . . 16
⊢ (((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) ∧ 𝑖 ∈ (ℤ≥‘2))
→ (𝑖 ∈ ℤ
∧ 𝐵 ∈
ℤ)) |
25 | 24 | adantr 481 |
. . . . . . . . . . . . . . 15
⊢ ((((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) ∧ 𝑖 ∈ (ℤ≥‘2))
∧ 𝑖 ≤ 𝐴) → (𝑖 ∈ ℤ ∧ 𝐵 ∈ ℤ)) |
26 | | zltlem1 11430 |
. . . . . . . . . . . . . . 15
⊢ ((𝑖 ∈ ℤ ∧ 𝐵 ∈ ℤ) → (𝑖 < 𝐵 ↔ 𝑖 ≤ (𝐵 − 1))) |
27 | 25, 26 | syl 17 |
. . . . . . . . . . . . . 14
⊢ ((((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) ∧ 𝑖 ∈ (ℤ≥‘2))
∧ 𝑖 ≤ 𝐴) → (𝑖 < 𝐵 ↔ 𝑖 ≤ (𝐵 − 1))) |
28 | 21, 27 | mpbid 222 |
. . . . . . . . . . . . 13
⊢ ((((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) ∧ 𝑖 ∈ (ℤ≥‘2))
∧ 𝑖 ≤ 𝐴) → 𝑖 ≤ (𝐵 − 1)) |
29 | 28 | ex 450 |
. . . . . . . . . . . 12
⊢ (((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) ∧ 𝑖 ∈ (ℤ≥‘2))
→ (𝑖 ≤ 𝐴 → 𝑖 ≤ (𝐵 − 1))) |
30 | 8, 29 | syldc 48 |
. . . . . . . . . . 11
⊢ (𝑖 ∥ 𝐴 → (((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) ∧ 𝑖 ∈ (ℤ≥‘2))
→ 𝑖 ≤ (𝐵 − 1))) |
31 | 30 | adantr 481 |
. . . . . . . . . 10
⊢ ((𝑖 ∥ 𝐴 ∧ 𝑖 ∥ 𝐵) → (((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) ∧ 𝑖 ∈ (ℤ≥‘2))
→ 𝑖 ≤ (𝐵 − 1))) |
32 | 31 | impcom 446 |
. . . . . . . . 9
⊢ ((((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) ∧ 𝑖 ∈ (ℤ≥‘2))
∧ (𝑖 ∥ 𝐴 ∧ 𝑖 ∥ 𝐵)) → 𝑖 ≤ (𝐵 − 1)) |
33 | | peano2zm 11420 |
. . . . . . . . . . . . . . 15
⊢ (𝐵 ∈ ℤ → (𝐵 − 1) ∈
ℤ) |
34 | 22, 33 | syl 17 |
. . . . . . . . . . . . . 14
⊢ (𝐵 ∈ ℕ → (𝐵 − 1) ∈
ℤ) |
35 | 34 | 3ad2ant2 1083 |
. . . . . . . . . . . . 13
⊢ ((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) → (𝐵 − 1) ∈ ℤ) |
36 | 35 | anim1i 592 |
. . . . . . . . . . . 12
⊢ (((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) ∧ 𝑖 ∈ (ℤ≥‘2))
→ ((𝐵 − 1)
∈ ℤ ∧ 𝑖
∈ (ℤ≥‘2))) |
37 | 36 | ancomd 467 |
. . . . . . . . . . 11
⊢ (((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) ∧ 𝑖 ∈ (ℤ≥‘2))
→ (𝑖 ∈
(ℤ≥‘2) ∧ (𝐵 − 1) ∈
ℤ)) |
38 | 37 | adantr 481 |
. . . . . . . . . 10
⊢ ((((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) ∧ 𝑖 ∈ (ℤ≥‘2))
∧ (𝑖 ∥ 𝐴 ∧ 𝑖 ∥ 𝐵)) → (𝑖 ∈ (ℤ≥‘2)
∧ (𝐵 − 1) ∈
ℤ)) |
39 | | elfz5 12334 |
. . . . . . . . . 10
⊢ ((𝑖 ∈
(ℤ≥‘2) ∧ (𝐵 − 1) ∈ ℤ) → (𝑖 ∈ (2...(𝐵 − 1)) ↔ 𝑖 ≤ (𝐵 − 1))) |
40 | 38, 39 | syl 17 |
. . . . . . . . 9
⊢ ((((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) ∧ 𝑖 ∈ (ℤ≥‘2))
∧ (𝑖 ∥ 𝐴 ∧ 𝑖 ∥ 𝐵)) → (𝑖 ∈ (2...(𝐵 − 1)) ↔ 𝑖 ≤ (𝐵 − 1))) |
41 | 32, 40 | mpbird 247 |
. . . . . . . 8
⊢ ((((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) ∧ 𝑖 ∈ (ℤ≥‘2))
∧ (𝑖 ∥ 𝐴 ∧ 𝑖 ∥ 𝐵)) → 𝑖 ∈ (2...(𝐵 − 1))) |
42 | | breq1 4656 |
. . . . . . . . 9
⊢ (𝑗 = 𝑖 → (𝑗 ∥ 𝐵 ↔ 𝑖 ∥ 𝐵)) |
43 | 42 | adantl 482 |
. . . . . . . 8
⊢
(((((𝐴 ∈
ℕ ∧ 𝐵 ∈
ℕ ∧ 𝐴 < 𝐵) ∧ 𝑖 ∈ (ℤ≥‘2))
∧ (𝑖 ∥ 𝐴 ∧ 𝑖 ∥ 𝐵)) ∧ 𝑗 = 𝑖) → (𝑗 ∥ 𝐵 ↔ 𝑖 ∥ 𝐵)) |
44 | | simprr 796 |
. . . . . . . 8
⊢ ((((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) ∧ 𝑖 ∈ (ℤ≥‘2))
∧ (𝑖 ∥ 𝐴 ∧ 𝑖 ∥ 𝐵)) → 𝑖 ∥ 𝐵) |
45 | 41, 43, 44 | rspcedvd 3317 |
. . . . . . 7
⊢ ((((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) ∧ 𝑖 ∈ (ℤ≥‘2))
∧ (𝑖 ∥ 𝐴 ∧ 𝑖 ∥ 𝐵)) → ∃𝑗 ∈ (2...(𝐵 − 1))𝑗 ∥ 𝐵) |
46 | | rexnal 2995 |
. . . . . . . 8
⊢
(∃𝑗 ∈
(2...(𝐵 − 1)) ¬
¬ 𝑗 ∥ 𝐵 ↔ ¬ ∀𝑗 ∈ (2...(𝐵 − 1)) ¬ 𝑗 ∥ 𝐵) |
47 | | notnotb 304 |
. . . . . . . . . 10
⊢ (𝑗 ∥ 𝐵 ↔ ¬ ¬ 𝑗 ∥ 𝐵) |
48 | 47 | bicomi 214 |
. . . . . . . . 9
⊢ (¬
¬ 𝑗 ∥ 𝐵 ↔ 𝑗 ∥ 𝐵) |
49 | 48 | rexbii 3041 |
. . . . . . . 8
⊢
(∃𝑗 ∈
(2...(𝐵 − 1)) ¬
¬ 𝑗 ∥ 𝐵 ↔ ∃𝑗 ∈ (2...(𝐵 − 1))𝑗 ∥ 𝐵) |
50 | 46, 49 | bitr3i 266 |
. . . . . . 7
⊢ (¬
∀𝑗 ∈
(2...(𝐵 − 1)) ¬
𝑗 ∥ 𝐵 ↔ ∃𝑗 ∈ (2...(𝐵 − 1))𝑗 ∥ 𝐵) |
51 | 45, 50 | sylibr 224 |
. . . . . 6
⊢ ((((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) ∧ 𝑖 ∈ (ℤ≥‘2))
∧ (𝑖 ∥ 𝐴 ∧ 𝑖 ∥ 𝐵)) → ¬ ∀𝑗 ∈ (2...(𝐵 − 1)) ¬ 𝑗 ∥ 𝐵) |
52 | 51 | olcd 408 |
. . . . 5
⊢ ((((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) ∧ 𝑖 ∈ (ℤ≥‘2))
∧ (𝑖 ∥ 𝐴 ∧ 𝑖 ∥ 𝐵)) → (¬ 𝐵 ∈ (ℤ≥‘2)
∨ ¬ ∀𝑗 ∈
(2...(𝐵 − 1)) ¬
𝑗 ∥ 𝐵)) |
53 | | df-nel 2898 |
. . . . . 6
⊢ (𝐵 ∉ ℙ ↔ ¬
𝐵 ∈
ℙ) |
54 | | ianor 509 |
. . . . . . 7
⊢ (¬
(𝐵 ∈
(ℤ≥‘2) ∧ ∀𝑗 ∈ (2...(𝐵 − 1)) ¬ 𝑗 ∥ 𝐵) ↔ (¬ 𝐵 ∈ (ℤ≥‘2)
∨ ¬ ∀𝑗 ∈
(2...(𝐵 − 1)) ¬
𝑗 ∥ 𝐵)) |
55 | | isprm3 15396 |
. . . . . . 7
⊢ (𝐵 ∈ ℙ ↔ (𝐵 ∈
(ℤ≥‘2) ∧ ∀𝑗 ∈ (2...(𝐵 − 1)) ¬ 𝑗 ∥ 𝐵)) |
56 | 54, 55 | xchnxbir 323 |
. . . . . 6
⊢ (¬
𝐵 ∈ ℙ ↔
(¬ 𝐵 ∈
(ℤ≥‘2) ∨ ¬ ∀𝑗 ∈ (2...(𝐵 − 1)) ¬ 𝑗 ∥ 𝐵)) |
57 | 53, 56 | bitri 264 |
. . . . 5
⊢ (𝐵 ∉ ℙ ↔ (¬
𝐵 ∈
(ℤ≥‘2) ∨ ¬ ∀𝑗 ∈ (2...(𝐵 − 1)) ¬ 𝑗 ∥ 𝐵)) |
58 | 52, 57 | sylibr 224 |
. . . 4
⊢ ((((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) ∧ 𝑖 ∈ (ℤ≥‘2))
∧ (𝑖 ∥ 𝐴 ∧ 𝑖 ∥ 𝐵)) → 𝐵 ∉ ℙ) |
59 | 58 | ex 450 |
. . 3
⊢ (((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) ∧ 𝑖 ∈ (ℤ≥‘2))
→ ((𝑖 ∥ 𝐴 ∧ 𝑖 ∥ 𝐵) → 𝐵 ∉ ℙ)) |
60 | 59 | rexlimdva 3031 |
. 2
⊢ ((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) → (∃𝑖 ∈
(ℤ≥‘2)(𝑖 ∥ 𝐴 ∧ 𝑖 ∥ 𝐵) → 𝐵 ∉ ℙ)) |
61 | 3, 60 | sylbid 230 |
1
⊢ ((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝐴 < 𝐵) → (1 < (𝐴 gcd 𝐵) → 𝐵 ∉ ℙ)) |