Metamath Proof Explorer


Theorem zrpmulgcd

Description: If K and M are relatively prime, then the gcd of K and M x. N is the gcd of K and N . Generalization of rpmulgcd . (Contributed by by AV, 7-Nov-2026)

Ref Expression
Assertion zrpmulgcd ( ( ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) ∧ ( 𝐾 gcd 𝑀 ) = 1 ) → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) )

Proof

Step Hyp Ref Expression
1 elz ⊢ ( 𝐾 ∈ ℤ ↔ ( 𝐾 ∈ ℝ ∧ ( 𝐾 = 0 ∨ 𝐾 ∈ ℕ ∨ - 𝐾 ∈ ℕ ) ) )
2 1 biimpi ⊢ ( 𝐾 ∈ ℤ → ( 𝐾 ∈ ℝ ∧ ( 𝐾 = 0 ∨ 𝐾 ∈ ℕ ∨ - 𝐾 ∈ ℕ ) ) )
3 elznn0 ⊢ ( 𝑁 ∈ ℤ ↔ ( 𝑁 ∈ ℝ ∧ ( 𝑁 ∈ ℕ0 ∨ - 𝑁 ∈ ℕ0 ) ) )
4 3 biimpi ⊢ ( 𝑁 ∈ ℤ → ( 𝑁 ∈ ℝ ∧ ( 𝑁 ∈ ℕ0 ∨ - 𝑁 ∈ ℕ0 ) ) )
5 zcn ⊢ ( 𝑀 ∈ ℤ → 𝑀 ∈ ℂ )
6 zcn ⊢ ( 𝑁 ∈ ℤ → 𝑁 ∈ ℂ )
7 absmul ⊢ ( ( 𝑀 ∈ ℂ ∧ 𝑁 ∈ ℂ ) → ( abs ‘ ( 𝑀 · 𝑁 ) ) = ( ( abs ‘ 𝑀 ) · ( abs ‘ 𝑁 ) ) )
8 5 6 7 syl2an ⊢ ( ( 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( abs ‘ ( 𝑀 · 𝑁 ) ) = ( ( abs ‘ 𝑀 ) · ( abs ‘ 𝑁 ) ) )
9 8 adantr ⊢ ( ( ( 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) ∧ ( abs ‘ 𝑀 ) = 1 ) → ( abs ‘ ( 𝑀 · 𝑁 ) ) = ( ( abs ‘ 𝑀 ) · ( abs ‘ 𝑁 ) ) )
10 oveq1 ⊢ ( ( abs ‘ 𝑀 ) = 1 → ( ( abs ‘ 𝑀 ) · ( abs ‘ 𝑁 ) ) = ( 1 · ( abs ‘ 𝑁 ) ) )
11 10 adantl ⊢ ( ( ( 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) ∧ ( abs ‘ 𝑀 ) = 1 ) → ( ( abs ‘ 𝑀 ) · ( abs ‘ 𝑁 ) ) = ( 1 · ( abs ‘ 𝑁 ) ) )
12 6 abscld ⊢ ( 𝑁 ∈ ℤ → ( abs ‘ 𝑁 ) ∈ ℝ )
13 12 adantl ⊢ ( ( 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( abs ‘ 𝑁 ) ∈ ℝ )
14 13 adantr ⊢ ( ( ( 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) ∧ ( abs ‘ 𝑀 ) = 1 ) → ( abs ‘ 𝑁 ) ∈ ℝ )
15 14 recnd ⊢ ( ( ( 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) ∧ ( abs ‘ 𝑀 ) = 1 ) → ( abs ‘ 𝑁 ) ∈ ℂ )
16 15 mullidd ⊢ ( ( ( 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) ∧ ( abs ‘ 𝑀 ) = 1 ) → ( 1 · ( abs ‘ 𝑁 ) ) = ( abs ‘ 𝑁 ) )
17 9 11 16 3eqtrd ⊢ ( ( ( 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) ∧ ( abs ‘ 𝑀 ) = 1 ) → ( abs ‘ ( 𝑀 · 𝑁 ) ) = ( abs ‘ 𝑁 ) )
18 17 ex ⊢ ( ( 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( ( abs ‘ 𝑀 ) = 1 → ( abs ‘ ( 𝑀 · 𝑁 ) ) = ( abs ‘ 𝑁 ) ) )
19 gcd0id ⊢ ( 𝑀 ∈ ℤ → ( 0 gcd 𝑀 ) = ( abs ‘ 𝑀 ) )
20 19 adantr ⊢ ( ( 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( 0 gcd 𝑀 ) = ( abs ‘ 𝑀 ) )
21 20 eqeq1d ⊢ ( ( 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( ( 0 gcd 𝑀 ) = 1 ↔ ( abs ‘ 𝑀 ) = 1 ) )
22 zmulcl ⊢ ( ( 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( 𝑀 · 𝑁 ) ∈ ℤ )
23 gcd0id ⊢ ( ( 𝑀 · 𝑁 ) ∈ ℤ → ( 0 gcd ( 𝑀 · 𝑁 ) ) = ( abs ‘ ( 𝑀 · 𝑁 ) ) )
24 22 23 syl ⊢ ( ( 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( 0 gcd ( 𝑀 · 𝑁 ) ) = ( abs ‘ ( 𝑀 · 𝑁 ) ) )
25 gcd0id ⊢ ( 𝑁 ∈ ℤ → ( 0 gcd 𝑁 ) = ( abs ‘ 𝑁 ) )
26 25 adantl ⊢ ( ( 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( 0 gcd 𝑁 ) = ( abs ‘ 𝑁 ) )
27 24 26 eqeq12d ⊢ ( ( 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( ( 0 gcd ( 𝑀 · 𝑁 ) ) = ( 0 gcd 𝑁 ) ↔ ( abs ‘ ( 𝑀 · 𝑁 ) ) = ( abs ‘ 𝑁 ) ) )
28 18 21 27 3imtr4d ⊢ ( ( 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( ( 0 gcd 𝑀 ) = 1 → ( 0 gcd ( 𝑀 · 𝑁 ) ) = ( 0 gcd 𝑁 ) ) )
29 oveq1 ⊢ ( 𝐾 = 0 → ( 𝐾 gcd 𝑀 ) = ( 0 gcd 𝑀 ) )
30 29 eqeq1d ⊢ ( 𝐾 = 0 → ( ( 𝐾 gcd 𝑀 ) = 1 ↔ ( 0 gcd 𝑀 ) = 1 ) )
31 oveq1 ⊢ ( 𝐾 = 0 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 0 gcd ( 𝑀 · 𝑁 ) ) )
32 oveq1 ⊢ ( 𝐾 = 0 → ( 𝐾 gcd 𝑁 ) = ( 0 gcd 𝑁 ) )
33 31 32 eqeq12d ⊢ ( 𝐾 = 0 → ( ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ↔ ( 0 gcd ( 𝑀 · 𝑁 ) ) = ( 0 gcd 𝑁 ) ) )
34 30 33 imbi12d ⊢ ( 𝐾 = 0 → ( ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) ↔ ( ( 0 gcd 𝑀 ) = 1 → ( 0 gcd ( 𝑀 · 𝑁 ) ) = ( 0 gcd 𝑁 ) ) ) )
35 28 34 imbitrrid ⊢ ( 𝐾 = 0 → ( ( 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) ) )
36 35 expd ⊢ ( 𝐾 = 0 → ( 𝑀 ∈ ℤ → ( 𝑁 ∈ ℤ → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) ) ) )
37 36 a1d ⊢ ( 𝐾 = 0 → ( ( 𝑁 ∈ ℕ0 ∨ - 𝑁 ∈ ℕ0 ) → ( 𝑀 ∈ ℤ → ( 𝑁 ∈ ℤ → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) ) ) ) )
38 37 a1i ⊢ ( 𝐾 ∈ ℤ → ( 𝐾 = 0 → ( ( 𝑁 ∈ ℕ0 ∨ - 𝑁 ∈ ℕ0 ) → ( 𝑀 ∈ ℤ → ( 𝑁 ∈ ℤ → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) ) ) ) ) )
39 rpmulgcd ⊢ ( ( ( 𝐾 ∈ ℕ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ0 ) ∧ ( 𝐾 gcd 𝑀 ) = 1 ) → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) )
40 39 ex ⊢ ( ( 𝐾 ∈ ℕ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ0 ) → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) )
41 40 a1d ⊢ ( ( 𝐾 ∈ ℕ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ0 ) → ( 𝑁 ∈ ℤ → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) ) )
42 41 3exp ⊢ ( 𝐾 ∈ ℕ → ( 𝑀 ∈ ℤ → ( 𝑁 ∈ ℕ0 → ( 𝑁 ∈ ℤ → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) ) ) ) )
43 42 com23 ⊢ ( 𝐾 ∈ ℕ → ( 𝑁 ∈ ℕ0 → ( 𝑀 ∈ ℤ → ( 𝑁 ∈ ℤ → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) ) ) ) )
44 nnz ⊢ ( 𝐾 ∈ ℕ → 𝐾 ∈ ℤ )
45 simpll ⊢ ( ( ( 𝐾 ∈ ℕ ∧ - 𝑁 ∈ ℕ0 ) ∧ ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) ) → 𝐾 ∈ ℕ )
46 simpr2 ⊢ ( ( ( 𝐾 ∈ ℕ ∧ - 𝑁 ∈ ℕ0 ) ∧ ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) ) → 𝑀 ∈ ℤ )
47 simplr ⊢ ( ( ( 𝐾 ∈ ℕ ∧ - 𝑁 ∈ ℕ0 ) ∧ ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) ) → - 𝑁 ∈ ℕ0 )
48 rpmulgcd ⊢ ( ( ( 𝐾 ∈ ℕ ∧ 𝑀 ∈ ℤ ∧ - 𝑁 ∈ ℕ0 ) ∧ ( 𝐾 gcd 𝑀 ) = 1 ) → ( 𝐾 gcd ( 𝑀 · - 𝑁 ) ) = ( 𝐾 gcd - 𝑁 ) )
49 48 ex ⊢ ( ( 𝐾 ∈ ℕ ∧ 𝑀 ∈ ℤ ∧ - 𝑁 ∈ ℕ0 ) → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · - 𝑁 ) ) = ( 𝐾 gcd - 𝑁 ) ) )
50 45 46 47 49 syl3anc ⊢ ( ( ( 𝐾 ∈ ℕ ∧ - 𝑁 ∈ ℕ0 ) ∧ ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) ) → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · - 𝑁 ) ) = ( 𝐾 gcd - 𝑁 ) ) )
51 mulneg2 ⊢ ( ( 𝑀 ∈ ℂ ∧ 𝑁 ∈ ℂ ) → ( 𝑀 · - 𝑁 ) = - ( 𝑀 · 𝑁 ) )
52 5 6 51 syl2an ⊢ ( ( 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( 𝑀 · - 𝑁 ) = - ( 𝑀 · 𝑁 ) )
53 52 3adant1 ⊢ ( ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( 𝑀 · - 𝑁 ) = - ( 𝑀 · 𝑁 ) )
54 53 oveq2d ⊢ ( ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( 𝐾 gcd ( 𝑀 · - 𝑁 ) ) = ( 𝐾 gcd - ( 𝑀 · 𝑁 ) ) )
55 simp1 ⊢ ( ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → 𝐾 ∈ ℤ )
56 22 3adant1 ⊢ ( ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( 𝑀 · 𝑁 ) ∈ ℤ )
57 gcdneg ⊢ ( ( 𝐾 ∈ ℤ ∧ ( 𝑀 · 𝑁 ) ∈ ℤ ) → ( 𝐾 gcd - ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) )
58 55 56 57 syl2anc ⊢ ( ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( 𝐾 gcd - ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) )
59 54 58 eqtrd ⊢ ( ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( 𝐾 gcd ( 𝑀 · - 𝑁 ) ) = ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) )
60 59 adantl ⊢ ( ( ( 𝐾 ∈ ℕ ∧ - 𝑁 ∈ ℕ0 ) ∧ ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) ) → ( 𝐾 gcd ( 𝑀 · - 𝑁 ) ) = ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) )
61 gcdneg ⊢ ( ( 𝐾 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( 𝐾 gcd - 𝑁 ) = ( 𝐾 gcd 𝑁 ) )
62 61 3adant2 ⊢ ( ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( 𝐾 gcd - 𝑁 ) = ( 𝐾 gcd 𝑁 ) )
63 62 adantl ⊢ ( ( ( 𝐾 ∈ ℕ ∧ - 𝑁 ∈ ℕ0 ) ∧ ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) ) → ( 𝐾 gcd - 𝑁 ) = ( 𝐾 gcd 𝑁 ) )
64 60 63 eqeq12d ⊢ ( ( ( 𝐾 ∈ ℕ ∧ - 𝑁 ∈ ℕ0 ) ∧ ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) ) → ( ( 𝐾 gcd ( 𝑀 · - 𝑁 ) ) = ( 𝐾 gcd - 𝑁 ) ↔ ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) )
65 50 64 sylibd ⊢ ( ( ( 𝐾 ∈ ℕ ∧ - 𝑁 ∈ ℕ0 ) ∧ ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) ) → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) )
66 65 3exp2 ⊢ ( ( 𝐾 ∈ ℕ ∧ - 𝑁 ∈ ℕ0 ) → ( 𝐾 ∈ ℤ → ( 𝑀 ∈ ℤ → ( 𝑁 ∈ ℤ → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) ) ) ) )
67 66 ex ⊢ ( 𝐾 ∈ ℕ → ( - 𝑁 ∈ ℕ0 → ( 𝐾 ∈ ℤ → ( 𝑀 ∈ ℤ → ( 𝑁 ∈ ℤ → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) ) ) ) ) )
68 44 67 mpid ⊢ ( 𝐾 ∈ ℕ → ( - 𝑁 ∈ ℕ0 → ( 𝑀 ∈ ℤ → ( 𝑁 ∈ ℤ → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) ) ) ) )
69 43 68 jaod ⊢ ( 𝐾 ∈ ℕ → ( ( 𝑁 ∈ ℕ0 ∨ - 𝑁 ∈ ℕ0 ) → ( 𝑀 ∈ ℤ → ( 𝑁 ∈ ℤ → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) ) ) ) )
70 69 a1i ⊢ ( 𝐾 ∈ ℤ → ( 𝐾 ∈ ℕ → ( ( 𝑁 ∈ ℕ0 ∨ - 𝑁 ∈ ℕ0 ) → ( 𝑀 ∈ ℤ → ( 𝑁 ∈ ℤ → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) ) ) ) ) )
71 3ancomb ⊢ ( ( - 𝐾 ∈ ℕ ∧ 𝑁 ∈ ℕ0 ∧ 𝑀 ∈ ℤ ) ↔ ( - 𝐾 ∈ ℕ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ0 ) )
72 rpmulgcd ⊢ ( ( ( - 𝐾 ∈ ℕ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ0 ) ∧ ( - 𝐾 gcd 𝑀 ) = 1 ) → ( - 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( - 𝐾 gcd 𝑁 ) )
73 71 72 sylanb ⊢ ( ( ( - 𝐾 ∈ ℕ ∧ 𝑁 ∈ ℕ0 ∧ 𝑀 ∈ ℤ ) ∧ ( - 𝐾 gcd 𝑀 ) = 1 ) → ( - 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( - 𝐾 gcd 𝑁 ) )
74 73 ex ⊢ ( ( - 𝐾 ∈ ℕ ∧ 𝑁 ∈ ℕ0 ∧ 𝑀 ∈ ℤ ) → ( ( - 𝐾 gcd 𝑀 ) = 1 → ( - 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( - 𝐾 gcd 𝑁 ) ) )
75 74 adantl ⊢ ( ( 𝐾 ∈ ℤ ∧ ( - 𝐾 ∈ ℕ ∧ 𝑁 ∈ ℕ0 ∧ 𝑀 ∈ ℤ ) ) → ( ( - 𝐾 gcd 𝑀 ) = 1 → ( - 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( - 𝐾 gcd 𝑁 ) ) )
76 simp3 ⊢ ( ( - 𝐾 ∈ ℕ ∧ 𝑁 ∈ ℕ0 ∧ 𝑀 ∈ ℤ ) → 𝑀 ∈ ℤ )
77 neggcd ⊢ ( ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ) → ( - 𝐾 gcd 𝑀 ) = ( 𝐾 gcd 𝑀 ) )
78 76 77 sylan2 ⊢ ( ( 𝐾 ∈ ℤ ∧ ( - 𝐾 ∈ ℕ ∧ 𝑁 ∈ ℕ0 ∧ 𝑀 ∈ ℤ ) ) → ( - 𝐾 gcd 𝑀 ) = ( 𝐾 gcd 𝑀 ) )
79 78 eqeq1d ⊢ ( ( 𝐾 ∈ ℤ ∧ ( - 𝐾 ∈ ℕ ∧ 𝑁 ∈ ℕ0 ∧ 𝑀 ∈ ℤ ) ) → ( ( - 𝐾 gcd 𝑀 ) = 1 ↔ ( 𝐾 gcd 𝑀 ) = 1 ) )
80 nn0z ⊢ ( 𝑁 ∈ ℕ0 → 𝑁 ∈ ℤ )
81 80 3ad2ant2 ⊢ ( ( - 𝐾 ∈ ℕ ∧ 𝑁 ∈ ℕ0 ∧ 𝑀 ∈ ℤ ) → 𝑁 ∈ ℤ )
82 76 81 zmulcld ⊢ ( ( - 𝐾 ∈ ℕ ∧ 𝑁 ∈ ℕ0 ∧ 𝑀 ∈ ℤ ) → ( 𝑀 · 𝑁 ) ∈ ℤ )
83 neggcd ⊢ ( ( 𝐾 ∈ ℤ ∧ ( 𝑀 · 𝑁 ) ∈ ℤ ) → ( - 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) )
84 82 83 sylan2 ⊢ ( ( 𝐾 ∈ ℤ ∧ ( - 𝐾 ∈ ℕ ∧ 𝑁 ∈ ℕ0 ∧ 𝑀 ∈ ℤ ) ) → ( - 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) )
85 neggcd ⊢ ( ( 𝐾 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( - 𝐾 gcd 𝑁 ) = ( 𝐾 gcd 𝑁 ) )
86 81 85 sylan2 ⊢ ( ( 𝐾 ∈ ℤ ∧ ( - 𝐾 ∈ ℕ ∧ 𝑁 ∈ ℕ0 ∧ 𝑀 ∈ ℤ ) ) → ( - 𝐾 gcd 𝑁 ) = ( 𝐾 gcd 𝑁 ) )
87 84 86 eqeq12d ⊢ ( ( 𝐾 ∈ ℤ ∧ ( - 𝐾 ∈ ℕ ∧ 𝑁 ∈ ℕ0 ∧ 𝑀 ∈ ℤ ) ) → ( ( - 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( - 𝐾 gcd 𝑁 ) ↔ ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) )
88 75 79 87 3imtr3d ⊢ ( ( 𝐾 ∈ ℤ ∧ ( - 𝐾 ∈ ℕ ∧ 𝑁 ∈ ℕ0 ∧ 𝑀 ∈ ℤ ) ) → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) )
89 88 a1d ⊢ ( ( 𝐾 ∈ ℤ ∧ ( - 𝐾 ∈ ℕ ∧ 𝑁 ∈ ℕ0 ∧ 𝑀 ∈ ℤ ) ) → ( 𝑁 ∈ ℤ → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) ) )
90 89 3exp2 ⊢ ( 𝐾 ∈ ℤ → ( - 𝐾 ∈ ℕ → ( 𝑁 ∈ ℕ0 → ( 𝑀 ∈ ℤ → ( 𝑁 ∈ ℤ → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) ) ) ) ) )
91 simpll ⊢ ( ( ( - 𝐾 ∈ ℕ ∧ - 𝑁 ∈ ℕ0 ) ∧ ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) ) → - 𝐾 ∈ ℕ )
92 simpr2 ⊢ ( ( ( - 𝐾 ∈ ℕ ∧ - 𝑁 ∈ ℕ0 ) ∧ ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) ) → 𝑀 ∈ ℤ )
93 simplr ⊢ ( ( ( - 𝐾 ∈ ℕ ∧ - 𝑁 ∈ ℕ0 ) ∧ ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) ) → - 𝑁 ∈ ℕ0 )
94 rpmulgcd ⊢ ( ( ( - 𝐾 ∈ ℕ ∧ 𝑀 ∈ ℤ ∧ - 𝑁 ∈ ℕ0 ) ∧ ( - 𝐾 gcd 𝑀 ) = 1 ) → ( - 𝐾 gcd ( 𝑀 · - 𝑁 ) ) = ( - 𝐾 gcd - 𝑁 ) )
95 94 ex ⊢ ( ( - 𝐾 ∈ ℕ ∧ 𝑀 ∈ ℤ ∧ - 𝑁 ∈ ℕ0 ) → ( ( - 𝐾 gcd 𝑀 ) = 1 → ( - 𝐾 gcd ( 𝑀 · - 𝑁 ) ) = ( - 𝐾 gcd - 𝑁 ) ) )
96 91 92 93 95 syl3anc ⊢ ( ( ( - 𝐾 ∈ ℕ ∧ - 𝑁 ∈ ℕ0 ) ∧ ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) ) → ( ( - 𝐾 gcd 𝑀 ) = 1 → ( - 𝐾 gcd ( 𝑀 · - 𝑁 ) ) = ( - 𝐾 gcd - 𝑁 ) ) )
97 77 3adant3 ⊢ ( ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( - 𝐾 gcd 𝑀 ) = ( 𝐾 gcd 𝑀 ) )
98 97 eqeq1d ⊢ ( ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( ( - 𝐾 gcd 𝑀 ) = 1 ↔ ( 𝐾 gcd 𝑀 ) = 1 ) )
99 98 adantl ⊢ ( ( ( - 𝐾 ∈ ℕ ∧ - 𝑁 ∈ ℕ0 ) ∧ ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) ) → ( ( - 𝐾 gcd 𝑀 ) = 1 ↔ ( 𝐾 gcd 𝑀 ) = 1 ) )
100 53 oveq2d ⊢ ( ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( - 𝐾 gcd ( 𝑀 · - 𝑁 ) ) = ( - 𝐾 gcd - ( 𝑀 · 𝑁 ) ) )
101 2neggcd ⊢ ( ( 𝐾 ∈ ℤ ∧ ( 𝑀 · 𝑁 ) ∈ ℤ ) → ( - 𝐾 gcd - ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) )
102 55 56 101 syl2anc ⊢ ( ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( - 𝐾 gcd - ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) )
103 100 102 eqtrd ⊢ ( ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( - 𝐾 gcd ( 𝑀 · - 𝑁 ) ) = ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) )
104 2neggcd ⊢ ( ( 𝐾 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( - 𝐾 gcd - 𝑁 ) = ( 𝐾 gcd 𝑁 ) )
105 104 3adant2 ⊢ ( ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( - 𝐾 gcd - 𝑁 ) = ( 𝐾 gcd 𝑁 ) )
106 103 105 eqeq12d ⊢ ( ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( ( - 𝐾 gcd ( 𝑀 · - 𝑁 ) ) = ( - 𝐾 gcd - 𝑁 ) ↔ ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) )
107 106 adantl ⊢ ( ( ( - 𝐾 ∈ ℕ ∧ - 𝑁 ∈ ℕ0 ) ∧ ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) ) → ( ( - 𝐾 gcd ( 𝑀 · - 𝑁 ) ) = ( - 𝐾 gcd - 𝑁 ) ↔ ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) )
108 96 99 107 3imtr3d ⊢ ( ( ( - 𝐾 ∈ ℕ ∧ - 𝑁 ∈ ℕ0 ) ∧ ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) ) → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) )
109 108 3exp2 ⊢ ( ( - 𝐾 ∈ ℕ ∧ - 𝑁 ∈ ℕ0 ) → ( 𝐾 ∈ ℤ → ( 𝑀 ∈ ℤ → ( 𝑁 ∈ ℤ → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) ) ) ) )
110 109 expcom ⊢ ( - 𝑁 ∈ ℕ0 → ( - 𝐾 ∈ ℕ → ( 𝐾 ∈ ℤ → ( 𝑀 ∈ ℤ → ( 𝑁 ∈ ℤ → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) ) ) ) ) )
111 110 com13 ⊢ ( 𝐾 ∈ ℤ → ( - 𝐾 ∈ ℕ → ( - 𝑁 ∈ ℕ0 → ( 𝑀 ∈ ℤ → ( 𝑁 ∈ ℤ → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) ) ) ) ) )
112 90 111 jaodd ⊢ ( 𝐾 ∈ ℤ → ( - 𝐾 ∈ ℕ → ( ( 𝑁 ∈ ℕ0 ∨ - 𝑁 ∈ ℕ0 ) → ( 𝑀 ∈ ℤ → ( 𝑁 ∈ ℤ → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) ) ) ) ) )
113 38 70 112 3jaod ⊢ ( 𝐾 ∈ ℤ → ( ( 𝐾 = 0 ∨ 𝐾 ∈ ℕ ∨ - 𝐾 ∈ ℕ ) → ( ( 𝑁 ∈ ℕ0 ∨ - 𝑁 ∈ ℕ0 ) → ( 𝑀 ∈ ℤ → ( 𝑁 ∈ ℤ → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) ) ) ) ) )
114 113 com23 ⊢ ( 𝐾 ∈ ℤ → ( ( 𝑁 ∈ ℕ0 ∨ - 𝑁 ∈ ℕ0 ) → ( ( 𝐾 = 0 ∨ 𝐾 ∈ ℕ ∨ - 𝐾 ∈ ℕ ) → ( 𝑀 ∈ ℤ → ( 𝑁 ∈ ℤ → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) ) ) ) ) )
115 114 com15 ⊢ ( 𝑁 ∈ ℤ → ( ( 𝑁 ∈ ℕ0 ∨ - 𝑁 ∈ ℕ0 ) → ( ( 𝐾 = 0 ∨ 𝐾 ∈ ℕ ∨ - 𝐾 ∈ ℕ ) → ( 𝑀 ∈ ℤ → ( 𝐾 ∈ ℤ → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) ) ) ) ) )
116 115 adantld ⊢ ( 𝑁 ∈ ℤ → ( ( 𝑁 ∈ ℝ ∧ ( 𝑁 ∈ ℕ0 ∨ - 𝑁 ∈ ℕ0 ) ) → ( ( 𝐾 = 0 ∨ 𝐾 ∈ ℕ ∨ - 𝐾 ∈ ℕ ) → ( 𝑀 ∈ ℤ → ( 𝐾 ∈ ℤ → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) ) ) ) ) )
117 4 116 mpd ⊢ ( 𝑁 ∈ ℤ → ( ( 𝐾 = 0 ∨ 𝐾 ∈ ℕ ∨ - 𝐾 ∈ ℕ ) → ( 𝑀 ∈ ℤ → ( 𝐾 ∈ ℤ → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) ) ) ) )
118 117 com14 ⊢ ( 𝐾 ∈ ℤ → ( ( 𝐾 = 0 ∨ 𝐾 ∈ ℕ ∨ - 𝐾 ∈ ℕ ) → ( 𝑀 ∈ ℤ → ( 𝑁 ∈ ℤ → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) ) ) ) )
119 118 adantld ⊢ ( 𝐾 ∈ ℤ → ( ( 𝐾 ∈ ℝ ∧ ( 𝐾 = 0 ∨ 𝐾 ∈ ℕ ∨ - 𝐾 ∈ ℕ ) ) → ( 𝑀 ∈ ℤ → ( 𝑁 ∈ ℤ → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) ) ) ) )
120 2 119 mpd ⊢ ( 𝐾 ∈ ℤ → ( 𝑀 ∈ ℤ → ( 𝑁 ∈ ℤ → ( ( 𝐾 gcd 𝑀 ) = 1 → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) ) ) ) )
121 120 3imp1 ⊢ ( ( ( 𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) ∧ ( 𝐾 gcd 𝑀 ) = 1 ) → ( 𝐾 gcd ( 𝑀 · 𝑁 ) ) = ( 𝐾 gcd 𝑁 ) )