Metamath Proof Explorer

Theorem zeqzmulgcd

Description: An integer is the product of an integer and the gcd of it and another integer. (Contributed by AV, 11-Jul-2021)

Ref Expression
Assertion zeqzmulgcd 
|- ( ( A e. ZZ /\ B e. ZZ ) -> E. n e. ZZ A = ( n x. ( A gcd B ) ) )

Proof

Step Hyp Ref Expression
1 gcddvds 
 |-  ( ( A e. ZZ /\ B e. ZZ ) -> ( ( A gcd B ) || A /\ ( A gcd B ) || B ) )
2 gcdcl 
 |-  ( ( A e. ZZ /\ B e. ZZ ) -> ( A gcd B ) e. NN0 )
3 2 nn0zd 
 |-  ( ( A e. ZZ /\ B e. ZZ ) -> ( A gcd B ) e. ZZ )
4 simpl 
 |-  ( ( A e. ZZ /\ B e. ZZ ) -> A e. ZZ )
5 divides 
 |-  ( ( ( A gcd B ) e. ZZ /\ A e. ZZ ) -> ( ( A gcd B ) || A <-> E. n e. ZZ ( n x. ( A gcd B ) ) = A ) )
6 3 4 5 syl2anc 
 |-  ( ( A e. ZZ /\ B e. ZZ ) -> ( ( A gcd B ) || A <-> E. n e. ZZ ( n x. ( A gcd B ) ) = A ) )
7 eqcom 
 |-  ( ( n x. ( A gcd B ) ) = A <-> A = ( n x. ( A gcd B ) ) )
8 7 a1i 
 |-  ( ( A e. ZZ /\ B e. ZZ ) -> ( ( n x. ( A gcd B ) ) = A <-> A = ( n x. ( A gcd B ) ) ) )
9 8 rexbidv 
 |-  ( ( A e. ZZ /\ B e. ZZ ) -> ( E. n e. ZZ ( n x. ( A gcd B ) ) = A <-> E. n e. ZZ A = ( n x. ( A gcd B ) ) ) )
10 9 biimpd 
 |-  ( ( A e. ZZ /\ B e. ZZ ) -> ( E. n e. ZZ ( n x. ( A gcd B ) ) = A -> E. n e. ZZ A = ( n x. ( A gcd B ) ) ) )
11 6 10 sylbid 
 |-  ( ( A e. ZZ /\ B e. ZZ ) -> ( ( A gcd B ) || A -> E. n e. ZZ A = ( n x. ( A gcd B ) ) ) )
12 11 adantrd 
 |-  ( ( A e. ZZ /\ B e. ZZ ) -> ( ( ( A gcd B ) || A /\ ( A gcd B ) || B ) -> E. n e. ZZ A = ( n x. ( A gcd B ) ) ) )
13 1 12 mpd 
 |-  ( ( A e. ZZ /\ B e. ZZ ) -> E. n e. ZZ A = ( n x. ( A gcd B ) ) )