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 ( ( 𝑀 ∈ ℤ ∧ 𝑃 ∈ ℙ ) → ( ( 𝑀 gcd 𝑃 ) = 1 ∨ ( 𝑀 gcd 𝑃 ) = 𝑃 ) )

Proof

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