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 ⊢ K ∈ ℤ ∧ M ∈ ℤ ∧ N ∈ ℤ ∧ K gcd M = 1 → K gcd M ⋅ N = K gcd N

Proof

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