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 ) ) )