Metamath Proof Explorer

Theorem pcgcd

Description: The prime count of a GCD is the minimum of the prime counts of the arguments. (Contributed by Mario Carneiro, 3-Oct-2014)

Ref Expression
Assertion pcgcd 
|- ( ( P e. Prime /\ A e. ZZ /\ B e. ZZ ) -> ( P pCnt ( A gcd B ) ) = if ( ( P pCnt A ) <_ ( P pCnt B ) , ( P pCnt A ) , ( P pCnt B ) ) )

Proof

Step Hyp Ref Expression
1 pcgcd1 
 |-  ( ( ( P e. Prime /\ A e. ZZ /\ B e. ZZ ) /\ ( P pCnt A ) <_ ( P pCnt B ) ) -> ( P pCnt ( A gcd B ) ) = ( P pCnt A ) )
2 iftrue 
 |-  ( ( P pCnt A ) <_ ( P pCnt B ) -> if ( ( P pCnt A ) <_ ( P pCnt B ) , ( P pCnt A ) , ( P pCnt B ) ) = ( P pCnt A ) )
3 2 adantl 
 |-  ( ( ( P e. Prime /\ A e. ZZ /\ B e. ZZ ) /\ ( P pCnt A ) <_ ( P pCnt B ) ) -> if ( ( P pCnt A ) <_ ( P pCnt B ) , ( P pCnt A ) , ( P pCnt B ) ) = ( P pCnt A ) )
4 1 3 eqtr4d 
 |-  ( ( ( P e. Prime /\ A e. ZZ /\ B e. ZZ ) /\ ( P pCnt A ) <_ ( P pCnt B ) ) -> ( P pCnt ( A gcd B ) ) = if ( ( P pCnt A ) <_ ( P pCnt B ) , ( P pCnt A ) , ( P pCnt B ) ) )
5 gcdcom 
 |-  ( ( A e. ZZ /\ B e. ZZ ) -> ( A gcd B ) = ( B gcd A ) )
6 5 3adant1 
 |-  ( ( P e. Prime /\ A e. ZZ /\ B e. ZZ ) -> ( A gcd B ) = ( B gcd A ) )
7 6 adantr 
 |-  ( ( ( P e. Prime /\ A e. ZZ /\ B e. ZZ ) /\ -. ( P pCnt A ) <_ ( P pCnt B ) ) -> ( A gcd B ) = ( B gcd A ) )
8 7 oveq2d 
 |-  ( ( ( P e. Prime /\ A e. ZZ /\ B e. ZZ ) /\ -. ( P pCnt A ) <_ ( P pCnt B ) ) -> ( P pCnt ( A gcd B ) ) = ( P pCnt ( B gcd A ) ) )
9 iffalse 
 |-  ( -. ( P pCnt A ) <_ ( P pCnt B ) -> if ( ( P pCnt A ) <_ ( P pCnt B ) , ( P pCnt A ) , ( P pCnt B ) ) = ( P pCnt B ) )
10 9 adantl 
 |-  ( ( ( P e. Prime /\ A e. ZZ /\ B e. ZZ ) /\ -. ( P pCnt A ) <_ ( P pCnt B ) ) -> if ( ( P pCnt A ) <_ ( P pCnt B ) , ( P pCnt A ) , ( P pCnt B ) ) = ( P pCnt B ) )
11 zq 
 |-  ( A e. ZZ -> A e. QQ )
12 pcxcl 
 |-  ( ( P e. Prime /\ A e. QQ ) -> ( P pCnt A ) e. RR* )
13 11 12 sylan2 
 |-  ( ( P e. Prime /\ A e. ZZ ) -> ( P pCnt A ) e. RR* )
14 13 3adant3 
 |-  ( ( P e. Prime /\ A e. ZZ /\ B e. ZZ ) -> ( P pCnt A ) e. RR* )
15 zq 
 |-  ( B e. ZZ -> B e. QQ )
16 pcxcl 
 |-  ( ( P e. Prime /\ B e. QQ ) -> ( P pCnt B ) e. RR* )
17 15 16 sylan2 
 |-  ( ( P e. Prime /\ B e. ZZ ) -> ( P pCnt B ) e. RR* )
18 xrletri 
 |-  ( ( ( P pCnt A ) e. RR* /\ ( P pCnt B ) e. RR* ) -> ( ( P pCnt A ) <_ ( P pCnt B ) \/ ( P pCnt B ) <_ ( P pCnt A ) ) )
19 14 17 18 3imp3i2an 
 |-  ( ( P e. Prime /\ A e. ZZ /\ B e. ZZ ) -> ( ( P pCnt A ) <_ ( P pCnt B ) \/ ( P pCnt B ) <_ ( P pCnt A ) ) )
20 19 orcanai 
 |-  ( ( ( P e. Prime /\ A e. ZZ /\ B e. ZZ ) /\ -. ( P pCnt A ) <_ ( P pCnt B ) ) -> ( P pCnt B ) <_ ( P pCnt A ) )
21 3ancomb 
 |-  ( ( P e. Prime /\ A e. ZZ /\ B e. ZZ ) <-> ( P e. Prime /\ B e. ZZ /\ A e. ZZ ) )
22 pcgcd1 
 |-  ( ( ( P e. Prime /\ B e. ZZ /\ A e. ZZ ) /\ ( P pCnt B ) <_ ( P pCnt A ) ) -> ( P pCnt ( B gcd A ) ) = ( P pCnt B ) )
23 21 22 sylanb 
 |-  ( ( ( P e. Prime /\ A e. ZZ /\ B e. ZZ ) /\ ( P pCnt B ) <_ ( P pCnt A ) ) -> ( P pCnt ( B gcd A ) ) = ( P pCnt B ) )
24 20 23 syldan 
 |-  ( ( ( P e. Prime /\ A e. ZZ /\ B e. ZZ ) /\ -. ( P pCnt A ) <_ ( P pCnt B ) ) -> ( P pCnt ( B gcd A ) ) = ( P pCnt B ) )
25 10 24 eqtr4d 
 |-  ( ( ( P e. Prime /\ A e. ZZ /\ B e. ZZ ) /\ -. ( P pCnt A ) <_ ( P pCnt B ) ) -> if ( ( P pCnt A ) <_ ( P pCnt B ) , ( P pCnt A ) , ( P pCnt B ) ) = ( P pCnt ( B gcd A ) ) )
26 8 25 eqtr4d 
 |-  ( ( ( P e. Prime /\ A e. ZZ /\ B e. ZZ ) /\ -. ( P pCnt A ) <_ ( P pCnt B ) ) -> ( P pCnt ( A gcd B ) ) = if ( ( P pCnt A ) <_ ( P pCnt B ) , ( P pCnt A ) , ( P pCnt B ) ) )
27 4 26 pm2.61dan 
 |-  ( ( P e. Prime /\ A e. ZZ /\ B e. ZZ ) -> ( P pCnt ( A gcd B ) ) = if ( ( P pCnt A ) <_ ( P pCnt B ) , ( P pCnt A ) , ( P pCnt B ) ) )