Metamath Proof Explorer


Theorem coprmgcdb

Description: Two positive integers are coprime, i.e. the only positive integer that divides both of them is 1, iff their greatest common divisor is 1. (Contributed by AV, 9-Aug-2020)

Ref Expression
Assertion coprmgcdb ( ( 𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ) → ( ∀ 𝑖 ∈ ℕ ( ( 𝑖𝐴𝑖𝐵 ) → 𝑖 = 1 ) ↔ ( 𝐴 gcd 𝐵 ) = 1 ) )

Proof

Step Hyp Ref Expression
1 nnz ( 𝐴 ∈ ℕ → 𝐴 ∈ ℤ )
2 nnz ( 𝐵 ∈ ℕ → 𝐵 ∈ ℤ )
3 gcddvds ( ( 𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ) → ( ( 𝐴 gcd 𝐵 ) ∥ 𝐴 ∧ ( 𝐴 gcd 𝐵 ) ∥ 𝐵 ) )
4 1 2 3 syl2an ( ( 𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ) → ( ( 𝐴 gcd 𝐵 ) ∥ 𝐴 ∧ ( 𝐴 gcd 𝐵 ) ∥ 𝐵 ) )
5 simpr ( ( ( 𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ) ∧ ( ( 𝐴 gcd 𝐵 ) ∥ 𝐴 ∧ ( 𝐴 gcd 𝐵 ) ∥ 𝐵 ) ) → ( ( 𝐴 gcd 𝐵 ) ∥ 𝐴 ∧ ( 𝐴 gcd 𝐵 ) ∥ 𝐵 ) )
6 gcdnncl ( ( 𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ) → ( 𝐴 gcd 𝐵 ) ∈ ℕ )
7 6 adantr ( ( ( 𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ) ∧ ( ( 𝐴 gcd 𝐵 ) ∥ 𝐴 ∧ ( 𝐴 gcd 𝐵 ) ∥ 𝐵 ) ) → ( 𝐴 gcd 𝐵 ) ∈ ℕ )
8 breq1 ( 𝑖 = ( 𝐴 gcd 𝐵 ) → ( 𝑖𝐴 ↔ ( 𝐴 gcd 𝐵 ) ∥ 𝐴 ) )
9 breq1 ( 𝑖 = ( 𝐴 gcd 𝐵 ) → ( 𝑖𝐵 ↔ ( 𝐴 gcd 𝐵 ) ∥ 𝐵 ) )
10 8 9 anbi12d ( 𝑖 = ( 𝐴 gcd 𝐵 ) → ( ( 𝑖𝐴𝑖𝐵 ) ↔ ( ( 𝐴 gcd 𝐵 ) ∥ 𝐴 ∧ ( 𝐴 gcd 𝐵 ) ∥ 𝐵 ) ) )
11 eqeq1 ( 𝑖 = ( 𝐴 gcd 𝐵 ) → ( 𝑖 = 1 ↔ ( 𝐴 gcd 𝐵 ) = 1 ) )
12 10 11 imbi12d ( 𝑖 = ( 𝐴 gcd 𝐵 ) → ( ( ( 𝑖𝐴𝑖𝐵 ) → 𝑖 = 1 ) ↔ ( ( ( 𝐴 gcd 𝐵 ) ∥ 𝐴 ∧ ( 𝐴 gcd 𝐵 ) ∥ 𝐵 ) → ( 𝐴 gcd 𝐵 ) = 1 ) ) )
13 12 rspcv ( ( 𝐴 gcd 𝐵 ) ∈ ℕ → ( ∀ 𝑖 ∈ ℕ ( ( 𝑖𝐴𝑖𝐵 ) → 𝑖 = 1 ) → ( ( ( 𝐴 gcd 𝐵 ) ∥ 𝐴 ∧ ( 𝐴 gcd 𝐵 ) ∥ 𝐵 ) → ( 𝐴 gcd 𝐵 ) = 1 ) ) )
14 7 13 syl ( ( ( 𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ) ∧ ( ( 𝐴 gcd 𝐵 ) ∥ 𝐴 ∧ ( 𝐴 gcd 𝐵 ) ∥ 𝐵 ) ) → ( ∀ 𝑖 ∈ ℕ ( ( 𝑖𝐴𝑖𝐵 ) → 𝑖 = 1 ) → ( ( ( 𝐴 gcd 𝐵 ) ∥ 𝐴 ∧ ( 𝐴 gcd 𝐵 ) ∥ 𝐵 ) → ( 𝐴 gcd 𝐵 ) = 1 ) ) )
15 5 14 mpid ( ( ( 𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ) ∧ ( ( 𝐴 gcd 𝐵 ) ∥ 𝐴 ∧ ( 𝐴 gcd 𝐵 ) ∥ 𝐵 ) ) → ( ∀ 𝑖 ∈ ℕ ( ( 𝑖𝐴𝑖𝐵 ) → 𝑖 = 1 ) → ( 𝐴 gcd 𝐵 ) = 1 ) )
16 4 15 mpdan ( ( 𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ) → ( ∀ 𝑖 ∈ ℕ ( ( 𝑖𝐴𝑖𝐵 ) → 𝑖 = 1 ) → ( 𝐴 gcd 𝐵 ) = 1 ) )
17 simpl ( ( ( 𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ) ∧ ( 𝐴 gcd 𝐵 ) = 1 ) → ( 𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ) )
18 17 anim1ci ( ( ( ( 𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ) ∧ ( 𝐴 gcd 𝐵 ) = 1 ) ∧ 𝑖 ∈ ℕ ) → ( 𝑖 ∈ ℕ ∧ ( 𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ) ) )
19 3anass ( ( 𝑖 ∈ ℕ ∧ 𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ) ↔ ( 𝑖 ∈ ℕ ∧ ( 𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ) ) )
20 18 19 sylibr ( ( ( ( 𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ) ∧ ( 𝐴 gcd 𝐵 ) = 1 ) ∧ 𝑖 ∈ ℕ ) → ( 𝑖 ∈ ℕ ∧ 𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ) )
21 nndvdslegcd ( ( 𝑖 ∈ ℕ ∧ 𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ) → ( ( 𝑖𝐴𝑖𝐵 ) → 𝑖 ≤ ( 𝐴 gcd 𝐵 ) ) )
22 20 21 syl ( ( ( ( 𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ) ∧ ( 𝐴 gcd 𝐵 ) = 1 ) ∧ 𝑖 ∈ ℕ ) → ( ( 𝑖𝐴𝑖𝐵 ) → 𝑖 ≤ ( 𝐴 gcd 𝐵 ) ) )
23 breq2 ( ( 𝐴 gcd 𝐵 ) = 1 → ( 𝑖 ≤ ( 𝐴 gcd 𝐵 ) ↔ 𝑖 ≤ 1 ) )
24 23 adantr ( ( ( 𝐴 gcd 𝐵 ) = 1 ∧ 𝑖 ∈ ℕ ) → ( 𝑖 ≤ ( 𝐴 gcd 𝐵 ) ↔ 𝑖 ≤ 1 ) )
25 nnge1 ( 𝑖 ∈ ℕ → 1 ≤ 𝑖 )
26 nnre ( 𝑖 ∈ ℕ → 𝑖 ∈ ℝ )
27 1red ( 𝑖 ∈ ℕ → 1 ∈ ℝ )
28 26 27 letri3d ( 𝑖 ∈ ℕ → ( 𝑖 = 1 ↔ ( 𝑖 ≤ 1 ∧ 1 ≤ 𝑖 ) ) )
29 28 biimprd ( 𝑖 ∈ ℕ → ( ( 𝑖 ≤ 1 ∧ 1 ≤ 𝑖 ) → 𝑖 = 1 ) )
30 25 29 mpan2d ( 𝑖 ∈ ℕ → ( 𝑖 ≤ 1 → 𝑖 = 1 ) )
31 30 adantl ( ( ( 𝐴 gcd 𝐵 ) = 1 ∧ 𝑖 ∈ ℕ ) → ( 𝑖 ≤ 1 → 𝑖 = 1 ) )
32 24 31 sylbid ( ( ( 𝐴 gcd 𝐵 ) = 1 ∧ 𝑖 ∈ ℕ ) → ( 𝑖 ≤ ( 𝐴 gcd 𝐵 ) → 𝑖 = 1 ) )
33 32 adantll ( ( ( ( 𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ) ∧ ( 𝐴 gcd 𝐵 ) = 1 ) ∧ 𝑖 ∈ ℕ ) → ( 𝑖 ≤ ( 𝐴 gcd 𝐵 ) → 𝑖 = 1 ) )
34 22 33 syld ( ( ( ( 𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ) ∧ ( 𝐴 gcd 𝐵 ) = 1 ) ∧ 𝑖 ∈ ℕ ) → ( ( 𝑖𝐴𝑖𝐵 ) → 𝑖 = 1 ) )
35 34 ralrimiva ( ( ( 𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ) ∧ ( 𝐴 gcd 𝐵 ) = 1 ) → ∀ 𝑖 ∈ ℕ ( ( 𝑖𝐴𝑖𝐵 ) → 𝑖 = 1 ) )
36 35 ex ( ( 𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ) → ( ( 𝐴 gcd 𝐵 ) = 1 → ∀ 𝑖 ∈ ℕ ( ( 𝑖𝐴𝑖𝐵 ) → 𝑖 = 1 ) ) )
37 16 36 impbid ( ( 𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ) → ( ∀ 𝑖 ∈ ℕ ( ( 𝑖𝐴𝑖𝐵 ) → 𝑖 = 1 ) ↔ ( 𝐴 gcd 𝐵 ) = 1 ) )