Metamath Proof Explorer


Theorem gcdprime

Description: The greatest common divisor of a nonzero integer and a prime number is either 1 or the prime number itself. (Contributed by SN, 15-Nov-2026)

Ref Expression
Assertion gcdprime ⊢ M ∈ ℤ ∧ P ∈ ℙ → M gcd P = 1 ∨ M gcd P = P

Proof

Step Hyp Ref Expression
1 prmz ⊢ P ∈ ℙ → P ∈ ℤ
2 gcddvds ⊢ M ∈ ℤ ∧ P ∈ ℤ → M gcd P ∥ M ∧ M gcd P ∥ P
3 2 simprd ⊢ M ∈ ℤ ∧ P ∈ ℤ → M gcd P ∥ P
4 1 3 sylan2 ⊢ M ∈ ℤ ∧ P ∈ ℙ → M gcd P ∥ P
5 simpr ⊢ M ∈ ℤ ∧ P ∈ ℙ → P ∈ ℙ
6 prmnn ⊢ P ∈ ℙ → P ∈ ℕ
7 6 nnne0d ⊢ P ∈ ℙ → P ≠ 0
8 gcd2n0cl ⊢ M ∈ ℤ ∧ P ∈ ℤ ∧ P ≠ 0 → M gcd P ∈ ℕ
9 7 8 syl3an3 ⊢ M ∈ ℤ ∧ P ∈ ℤ ∧ P ∈ ℙ → M gcd P ∈ ℕ
10 1 9 syl3an2 ⊢ M ∈ ℤ ∧ P ∈ ℙ ∧ P ∈ ℙ → M gcd P ∈ ℕ
11 10 3anidm23 ⊢ M ∈ ℤ ∧ P ∈ ℙ → M gcd P ∈ ℕ
12 dvdsprime ⊢ P ∈ ℙ ∧ M gcd P ∈ ℕ → M gcd P ∥ P ↔ M gcd P = P ∨ M gcd P = 1
13 5 11 12 syl2anc ⊢ M ∈ ℤ ∧ P ∈ ℙ → M gcd P ∥ P ↔ M gcd P = P ∨ M gcd P = 1
14 4 13 mpbid ⊢ M ∈ ℤ ∧ P ∈ ℙ → M gcd P = P ∨ M gcd P = 1
15 14 orcomd ⊢ M ∈ ℤ ∧ P ∈ ℙ → M gcd P = 1 ∨ M gcd P = P