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

Metamath Proof Explorer

Theorem nndvdslegcd

Description: A positive integer which divides both positive operands of the gcd operator is bounded by it. (Contributed by AV, 9-Aug-2020)

Ref Expression
Assertion nndvdslegcd 
|- ( ( K e. NN /\ M e. NN /\ N e. NN ) -> ( ( K || M /\ K || N ) -> K <_ ( M gcd N ) ) )

Proof

Step Hyp Ref Expression
1 nnz 
 |-  ( K e. NN -> K e. ZZ )
2 nnz 
 |-  ( M e. NN -> M e. ZZ )
3 nnz 
 |-  ( N e. NN -> N e. ZZ )
4 1 2 3 3anim123i 
 |-  ( ( K e. NN /\ M e. NN /\ N e. NN ) -> ( K e. ZZ /\ M e. ZZ /\ N e. ZZ ) )
5 nnne0 
 |-  ( M e. NN -> M =/= 0 )
6 5 neneqd 
 |-  ( M e. NN -> -. M = 0 )
7 6 3ad2ant2 
 |-  ( ( K e. NN /\ M e. NN /\ N e. NN ) -> -. M = 0 )
8 7 intnanrd 
 |-  ( ( K e. NN /\ M e. NN /\ N e. NN ) -> -. ( M = 0 /\ N = 0 ) )
9 dvdslegcd 
 |-  ( ( ( K e. ZZ /\ M e. ZZ /\ N e. ZZ ) /\ -. ( M = 0 /\ N = 0 ) ) -> ( ( K || M /\ K || N ) -> K <_ ( M gcd N ) ) )
10 4 8 9 syl2anc 
 |-  ( ( K e. NN /\ M e. NN /\ N e. NN ) -> ( ( K || M /\ K || N ) -> K <_ ( M gcd N ) ) )