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 e. ZZ /\ P e. Prime ) -> ( ( M gcd P ) = 1 \/ ( M gcd P ) = P ) )

Proof

Step Hyp Ref Expression
1 prmz
 |-  ( P e. Prime -> P e. ZZ )
2 gcddvds
 |-  ( ( M e. ZZ /\ P e. ZZ ) -> ( ( M gcd P ) || M /\ ( M gcd P ) || P ) )
3 2 simprd
 |-  ( ( M e. ZZ /\ P e. ZZ ) -> ( M gcd P ) || P )
4 1 3 sylan2
 |-  ( ( M e. ZZ /\ P e. Prime ) -> ( M gcd P ) || P )
5 simpr
 |-  ( ( M e. ZZ /\ P e. Prime ) -> P e. Prime )
6 prmnn
 |-  ( P e. Prime -> P e. NN )
7 6 nnne0d
 |-  ( P e. Prime -> P =/= 0 )
8 gcd2n0cl
 |-  ( ( M e. ZZ /\ P e. ZZ /\ P =/= 0 ) -> ( M gcd P ) e. NN )
9 7 8 syl3an3
 |-  ( ( M e. ZZ /\ P e. ZZ /\ P e. Prime ) -> ( M gcd P ) e. NN )
10 1 9 syl3an2
 |-  ( ( M e. ZZ /\ P e. Prime /\ P e. Prime ) -> ( M gcd P ) e. NN )
11 10 3anidm23
 |-  ( ( M e. ZZ /\ P e. Prime ) -> ( M gcd P ) e. NN )
12 dvdsprime
 |-  ( ( P e. Prime /\ ( M gcd P ) e. NN ) -> ( ( M gcd P ) || P <-> ( ( M gcd P ) = P \/ ( M gcd P ) = 1 ) ) )
13 5 11 12 syl2anc
 |-  ( ( M e. ZZ /\ P e. Prime ) -> ( ( M gcd P ) || P <-> ( ( M gcd P ) = P \/ ( M gcd P ) = 1 ) ) )
14 4 13 mpbid
 |-  ( ( M e. ZZ /\ P e. Prime ) -> ( ( M gcd P ) = P \/ ( M gcd P ) = 1 ) )
15 14 orcomd
 |-  ( ( M e. ZZ /\ P e. Prime ) -> ( ( M gcd P ) = 1 \/ ( M gcd P ) = P ) )