This is an inofficial mirror of http://metamath.tirix.org for personal testing of a visualizer extension only.

Metamath Proof Explorer

Theorem divides

Description: Define the divides relation. M || N means M divides into N with no remainder. For example, 3 || 6 ( ex-dvds ). As proven in dvdsval3 , M || N <-> ( N mod M ) = 0 . See divides and dvdsval2 for other equivalent expressions. (Contributed by Paul Chapman, 21-Mar-2011)

Ref Expression
Assertion divides 
|- ( ( M e. ZZ /\ N e. ZZ ) -> ( M || N <-> E. n e. ZZ ( n x. M ) = N ) )

Proof

Step Hyp Ref Expression
1 df-br 
 |-  ( M || N <-> <. M , N >. e. || )
2 df-dvds 
 |-  || = { <. x , y >. | ( ( x e. ZZ /\ y e. ZZ ) /\ E. n e. ZZ ( n x. x ) = y ) }
3 2 eleq2i 
 |-  ( <. M , N >. e. || <-> <. M , N >. e. { <. x , y >. | ( ( x e. ZZ /\ y e. ZZ ) /\ E. n e. ZZ ( n x. x ) = y ) } )
4 1 3 bitri 
 |-  ( M || N <-> <. M , N >. e. { <. x , y >. | ( ( x e. ZZ /\ y e. ZZ ) /\ E. n e. ZZ ( n x. x ) = y ) } )
5 oveq2 
 |-  ( x = M -> ( n x. x ) = ( n x. M ) )
6 5 eqeq1d 
 |-  ( x = M -> ( ( n x. x ) = y <-> ( n x. M ) = y ) )
7 6 rexbidv 
 |-  ( x = M -> ( E. n e. ZZ ( n x. x ) = y <-> E. n e. ZZ ( n x. M ) = y ) )
8 eqeq2 
 |-  ( y = N -> ( ( n x. M ) = y <-> ( n x. M ) = N ) )
9 8 rexbidv 
 |-  ( y = N -> ( E. n e. ZZ ( n x. M ) = y <-> E. n e. ZZ ( n x. M ) = N ) )
10 7 9 opelopab2 
 |-  ( ( M e. ZZ /\ N e. ZZ ) -> ( <. M , N >. e. { <. x , y >. | ( ( x e. ZZ /\ y e. ZZ ) /\ E. n e. ZZ ( n x. x ) = y ) } <-> E. n e. ZZ ( n x. M ) = N ) )
11 4 10 bitrid 
 |-  ( ( M e. ZZ /\ N e. ZZ ) -> ( M || N <-> E. n e. ZZ ( n x. M ) = N ) )