Proof of Theorem bezoutr1
Step | Hyp | Ref
| Expression |
1 | | bezoutr 16125 |
. . . . . 6
⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ (𝑋 ∈ ℤ ∧ 𝑌 ∈ ℤ)) → (𝐴 gcd 𝐵) ∥ ((𝐴 · 𝑋) + (𝐵 · 𝑌))) |
2 | 1 | adantr 484 |
. . . . 5
⊢ ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ (𝑋 ∈ ℤ ∧ 𝑌 ∈ ℤ)) ∧ ((𝐴 · 𝑋) + (𝐵 · 𝑌)) = 1) → (𝐴 gcd 𝐵) ∥ ((𝐴 · 𝑋) + (𝐵 · 𝑌))) |
3 | | simpr 488 |
. . . . 5
⊢ ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ (𝑋 ∈ ℤ ∧ 𝑌 ∈ ℤ)) ∧ ((𝐴 · 𝑋) + (𝐵 · 𝑌)) = 1) → ((𝐴 · 𝑋) + (𝐵 · 𝑌)) = 1) |
4 | 2, 3 | breqtrd 5079 |
. . . 4
⊢ ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ (𝑋 ∈ ℤ ∧ 𝑌 ∈ ℤ)) ∧ ((𝐴 · 𝑋) + (𝐵 · 𝑌)) = 1) → (𝐴 gcd 𝐵) ∥ 1) |
5 | | gcdcl 16065 |
. . . . . . 7
⊢ ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) → (𝐴 gcd 𝐵) ∈
ℕ0) |
6 | 5 | nn0zd 12280 |
. . . . . 6
⊢ ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) → (𝐴 gcd 𝐵) ∈ ℤ) |
7 | 6 | ad2antrr 726 |
. . . . 5
⊢ ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ (𝑋 ∈ ℤ ∧ 𝑌 ∈ ℤ)) ∧ ((𝐴 · 𝑋) + (𝐵 · 𝑌)) = 1) → (𝐴 gcd 𝐵) ∈ ℤ) |
8 | | 1nn 11841 |
. . . . . 6
⊢ 1 ∈
ℕ |
9 | 8 | a1i 11 |
. . . . 5
⊢ ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ (𝑋 ∈ ℤ ∧ 𝑌 ∈ ℤ)) ∧ ((𝐴 · 𝑋) + (𝐵 · 𝑌)) = 1) → 1 ∈
ℕ) |
10 | | dvdsle 15871 |
. . . . 5
⊢ (((𝐴 gcd 𝐵) ∈ ℤ ∧ 1 ∈ ℕ)
→ ((𝐴 gcd 𝐵) ∥ 1 → (𝐴 gcd 𝐵) ≤ 1)) |
11 | 7, 9, 10 | syl2anc 587 |
. . . 4
⊢ ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ (𝑋 ∈ ℤ ∧ 𝑌 ∈ ℤ)) ∧ ((𝐴 · 𝑋) + (𝐵 · 𝑌)) = 1) → ((𝐴 gcd 𝐵) ∥ 1 → (𝐴 gcd 𝐵) ≤ 1)) |
12 | 4, 11 | mpd 15 |
. . 3
⊢ ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ (𝑋 ∈ ℤ ∧ 𝑌 ∈ ℤ)) ∧ ((𝐴 · 𝑋) + (𝐵 · 𝑌)) = 1) → (𝐴 gcd 𝐵) ≤ 1) |
13 | | simpll 767 |
. . . . 5
⊢ ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ (𝑋 ∈ ℤ ∧ 𝑌 ∈ ℤ)) ∧ ((𝐴 · 𝑋) + (𝐵 · 𝑌)) = 1) → (𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ)) |
14 | | oveq1 7220 |
. . . . . . . . . . . . 13
⊢ (𝐴 = 0 → (𝐴 · 𝑋) = (0 · 𝑋)) |
15 | | oveq1 7220 |
. . . . . . . . . . . . 13
⊢ (𝐵 = 0 → (𝐵 · 𝑌) = (0 · 𝑌)) |
16 | 14, 15 | oveqan12d 7232 |
. . . . . . . . . . . 12
⊢ ((𝐴 = 0 ∧ 𝐵 = 0) → ((𝐴 · 𝑋) + (𝐵 · 𝑌)) = ((0 · 𝑋) + (0 · 𝑌))) |
17 | | zcn 12181 |
. . . . . . . . . . . . . 14
⊢ (𝑋 ∈ ℤ → 𝑋 ∈
ℂ) |
18 | 17 | mul02d 11030 |
. . . . . . . . . . . . 13
⊢ (𝑋 ∈ ℤ → (0
· 𝑋) =
0) |
19 | | zcn 12181 |
. . . . . . . . . . . . . 14
⊢ (𝑌 ∈ ℤ → 𝑌 ∈
ℂ) |
20 | 19 | mul02d 11030 |
. . . . . . . . . . . . 13
⊢ (𝑌 ∈ ℤ → (0
· 𝑌) =
0) |
21 | 18, 20 | oveqan12d 7232 |
. . . . . . . . . . . 12
⊢ ((𝑋 ∈ ℤ ∧ 𝑌 ∈ ℤ) → ((0
· 𝑋) + (0 ·
𝑌)) = (0 +
0)) |
22 | 16, 21 | sylan9eqr 2800 |
. . . . . . . . . . 11
⊢ (((𝑋 ∈ ℤ ∧ 𝑌 ∈ ℤ) ∧ (𝐴 = 0 ∧ 𝐵 = 0)) → ((𝐴 · 𝑋) + (𝐵 · 𝑌)) = (0 + 0)) |
23 | | 00id 11007 |
. . . . . . . . . . 11
⊢ (0 + 0) =
0 |
24 | 22, 23 | eqtrdi 2794 |
. . . . . . . . . 10
⊢ (((𝑋 ∈ ℤ ∧ 𝑌 ∈ ℤ) ∧ (𝐴 = 0 ∧ 𝐵 = 0)) → ((𝐴 · 𝑋) + (𝐵 · 𝑌)) = 0) |
25 | 24 | adantll 714 |
. . . . . . . . 9
⊢ ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ (𝑋 ∈ ℤ ∧ 𝑌 ∈ ℤ)) ∧ (𝐴 = 0 ∧ 𝐵 = 0)) → ((𝐴 · 𝑋) + (𝐵 · 𝑌)) = 0) |
26 | | 0ne1 11901 |
. . . . . . . . . 10
⊢ 0 ≠
1 |
27 | 26 | a1i 11 |
. . . . . . . . 9
⊢ ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ (𝑋 ∈ ℤ ∧ 𝑌 ∈ ℤ)) ∧ (𝐴 = 0 ∧ 𝐵 = 0)) → 0 ≠ 1) |
28 | 25, 27 | eqnetrd 3008 |
. . . . . . . 8
⊢ ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ (𝑋 ∈ ℤ ∧ 𝑌 ∈ ℤ)) ∧ (𝐴 = 0 ∧ 𝐵 = 0)) → ((𝐴 · 𝑋) + (𝐵 · 𝑌)) ≠ 1) |
29 | 28 | ex 416 |
. . . . . . 7
⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ (𝑋 ∈ ℤ ∧ 𝑌 ∈ ℤ)) → ((𝐴 = 0 ∧ 𝐵 = 0) → ((𝐴 · 𝑋) + (𝐵 · 𝑌)) ≠ 1)) |
30 | 29 | necon2bd 2956 |
. . . . . 6
⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ (𝑋 ∈ ℤ ∧ 𝑌 ∈ ℤ)) →
(((𝐴 · 𝑋) + (𝐵 · 𝑌)) = 1 → ¬ (𝐴 = 0 ∧ 𝐵 = 0))) |
31 | 30 | imp 410 |
. . . . 5
⊢ ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ (𝑋 ∈ ℤ ∧ 𝑌 ∈ ℤ)) ∧ ((𝐴 · 𝑋) + (𝐵 · 𝑌)) = 1) → ¬ (𝐴 = 0 ∧ 𝐵 = 0)) |
32 | | gcdn0cl 16061 |
. . . . 5
⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ ¬
(𝐴 = 0 ∧ 𝐵 = 0)) → (𝐴 gcd 𝐵) ∈ ℕ) |
33 | 13, 31, 32 | syl2anc 587 |
. . . 4
⊢ ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ (𝑋 ∈ ℤ ∧ 𝑌 ∈ ℤ)) ∧ ((𝐴 · 𝑋) + (𝐵 · 𝑌)) = 1) → (𝐴 gcd 𝐵) ∈ ℕ) |
34 | | nnle1eq1 11860 |
. . . 4
⊢ ((𝐴 gcd 𝐵) ∈ ℕ → ((𝐴 gcd 𝐵) ≤ 1 ↔ (𝐴 gcd 𝐵) = 1)) |
35 | 33, 34 | syl 17 |
. . 3
⊢ ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ (𝑋 ∈ ℤ ∧ 𝑌 ∈ ℤ)) ∧ ((𝐴 · 𝑋) + (𝐵 · 𝑌)) = 1) → ((𝐴 gcd 𝐵) ≤ 1 ↔ (𝐴 gcd 𝐵) = 1)) |
36 | 12, 35 | mpbid 235 |
. 2
⊢ ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ (𝑋 ∈ ℤ ∧ 𝑌 ∈ ℤ)) ∧ ((𝐴 · 𝑋) + (𝐵 · 𝑌)) = 1) → (𝐴 gcd 𝐵) = 1) |
37 | 36 | ex 416 |
1
⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ (𝑋 ∈ ℤ ∧ 𝑌 ∈ ℤ)) →
(((𝐴 · 𝑋) + (𝐵 · 𝑌)) = 1 → (𝐴 gcd 𝐵) = 1)) |