Metamath Proof Explorer

Theorem cncongrcoprm

Description: Corollary 1 of Cancellability of Congruences: Two products with a common factor are congruent modulo an integer being coprime to the common factor iff the other factors are congruent modulo the integer. (Contributed by AV, 13-Jul-2021)

Ref Expression
Assertion cncongrcoprm 
|- ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ ( C gcd N ) = 1 ) ) -> ( ( ( A x. C ) mod N ) = ( ( B x. C ) mod N ) <-> ( A mod N ) = ( B mod N ) ) )

Proof

Step Hyp Ref Expression
1 simpl 
 |-  ( ( N e. NN /\ ( C gcd N ) = 1 ) -> N e. NN )
2 nncn 
 |-  ( N e. NN -> N e. CC )
3 2 div1d 
 |-  ( N e. NN -> ( N / 1 ) = N )
4 oveq2 
 |-  ( ( C gcd N ) = 1 -> ( N / ( C gcd N ) ) = ( N / 1 ) )
5 4 eqcomd 
 |-  ( ( C gcd N ) = 1 -> ( N / 1 ) = ( N / ( C gcd N ) ) )
6 3 5 sylan9req 
 |-  ( ( N e. NN /\ ( C gcd N ) = 1 ) -> N = ( N / ( C gcd N ) ) )
7 1 6 jca 
 |-  ( ( N e. NN /\ ( C gcd N ) = 1 ) -> ( N e. NN /\ N = ( N / ( C gcd N ) ) ) )
8 cncongr 
 |-  ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ N = ( N / ( C gcd N ) ) ) ) -> ( ( ( A x. C ) mod N ) = ( ( B x. C ) mod N ) <-> ( A mod N ) = ( B mod N ) ) )
9 7 8 sylan2 
 |-  ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ ( C gcd N ) = 1 ) ) -> ( ( ( A x. C ) mod N ) = ( ( B x. C ) mod N ) <-> ( A mod N ) = ( B mod N ) ) )