Metamath Proof Explorer


Theorem rpmulgcd

Description: If K and M are relatively prime, then the gcd of K and M x. N is the gcd of K and N . (Contributed by Scott Fenton, 12-Apr-2014) (Revised by Mario Carneiro, 19-Apr-2014) Antecedent generalized. (Revised by AV, 7-Nov-2026)

Ref Expression
Assertion rpmulgcd ⊢ K ∈ ℕ ∧ M ∈ ℤ ∧ N ∈ ℕ 0 ∧ K gcd M = 1 → K gcd M ⋅ N = K gcd N

Proof

Step Hyp Ref Expression
1 nn0z ⊢ N ∈ ℕ 0 → N ∈ ℤ
2 gcdmultiplez ⊢ K ∈ ℕ ∧ N ∈ ℤ → K gcd K ⋅ N = K
3 1 2 sylan2 ⊢ K ∈ ℕ ∧ N ∈ ℕ 0 → K gcd K ⋅ N = K
4 3 3adant2 ⊢ K ∈ ℕ ∧ M ∈ ℤ ∧ N ∈ ℕ 0 → K gcd K ⋅ N = K
5 4 oveq1d ⊢ K ∈ ℕ ∧ M ∈ ℤ ∧ N ∈ ℕ 0 → K gcd K ⋅ N gcd M ⋅ N = K gcd M ⋅ N
6 nnz ⊢ K ∈ ℕ → K ∈ ℤ
7 6 3ad2ant1 ⊢ K ∈ ℕ ∧ M ∈ ℤ ∧ N ∈ ℕ 0 → K ∈ ℤ
8 1 3ad2ant3 ⊢ K ∈ ℕ ∧ M ∈ ℤ ∧ N ∈ ℕ 0 → N ∈ ℤ
9 7 8 zmulcld ⊢ K ∈ ℕ ∧ M ∈ ℤ ∧ N ∈ ℕ 0 → K ⋅ N ∈ ℤ
10 simp2 ⊢ K ∈ ℕ ∧ M ∈ ℤ ∧ N ∈ ℕ 0 → M ∈ ℤ
11 10 8 zmulcld ⊢ K ∈ ℕ ∧ M ∈ ℤ ∧ N ∈ ℕ 0 → M ⋅ N ∈ ℤ
12 gcdass ⊢ K ∈ ℤ ∧ K ⋅ N ∈ ℤ ∧ M ⋅ N ∈ ℤ → K gcd K ⋅ N gcd M ⋅ N = K gcd K ⋅ N gcd M ⋅ N
13 7 9 11 12 syl3anc ⊢ K ∈ ℕ ∧ M ∈ ℤ ∧ N ∈ ℕ 0 → K gcd K ⋅ N gcd M ⋅ N = K gcd K ⋅ N gcd M ⋅ N
14 5 13 eqtr3d ⊢ K ∈ ℕ ∧ M ∈ ℤ ∧ N ∈ ℕ 0 → K gcd M ⋅ N = K gcd K ⋅ N gcd M ⋅ N
15 14 adantr ⊢ K ∈ ℕ ∧ M ∈ ℤ ∧ N ∈ ℕ 0 ∧ K gcd M = 1 → K gcd M ⋅ N = K gcd K ⋅ N gcd M ⋅ N
16 mulgcdr ⊢ K ∈ ℤ ∧ M ∈ ℤ ∧ N ∈ ℕ 0 → K ⋅ N gcd M ⋅ N = K gcd M ⋅ N
17 6 16 syl3an1 ⊢ K ∈ ℕ ∧ M ∈ ℤ ∧ N ∈ ℕ 0 → K ⋅ N gcd M ⋅ N = K gcd M ⋅ N
18 oveq1 ⊢ K gcd M = 1 → K gcd M ⋅ N = 1 ⋅ N
19 17 18 sylan9eq ⊢ K ∈ ℕ ∧ M ∈ ℤ ∧ N ∈ ℕ 0 ∧ K gcd M = 1 → K ⋅ N gcd M ⋅ N = 1 ⋅ N
20 nn0cn ⊢ N ∈ ℕ 0 → N ∈ ℂ
21 20 3ad2ant3 ⊢ K ∈ ℕ ∧ M ∈ ℤ ∧ N ∈ ℕ 0 → N ∈ ℂ
22 21 adantr ⊢ K ∈ ℕ ∧ M ∈ ℤ ∧ N ∈ ℕ 0 ∧ K gcd M = 1 → N ∈ ℂ
23 22 mullidd ⊢ K ∈ ℕ ∧ M ∈ ℤ ∧ N ∈ ℕ 0 ∧ K gcd M = 1 → 1 ⋅ N = N
24 19 23 eqtrd ⊢ K ∈ ℕ ∧ M ∈ ℤ ∧ N ∈ ℕ 0 ∧ K gcd M = 1 → K ⋅ N gcd M ⋅ N = N
25 24 oveq2d ⊢ K ∈ ℕ ∧ M ∈ ℤ ∧ N ∈ ℕ 0 ∧ K gcd M = 1 → K gcd K ⋅ N gcd M ⋅ N = K gcd N
26 15 25 eqtrd ⊢ K ∈ ℕ ∧ M ∈ ℤ ∧ N ∈ ℕ 0 ∧ K gcd M = 1 → K gcd M ⋅ N = K gcd N