Theorem gcdadd

Description: The GCD of two numbers is the same as the GCD of the left and their sum. (Contributed by Scott Fenton, 20-Apr-2014)

	Ref	Expression
Assertion	gcdadd	⊢ ( ( 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( 𝑀 gcd 𝑁 ) = ( 𝑀 gcd ( 𝑁 + 𝑀 ) ) )

Proof

Step	Hyp	Ref	Expression
1		1z	⊢ 1 ∈ ℤ
2		gcdaddm	⊢ ( ( 1 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( 𝑀 gcd 𝑁 ) = ( 𝑀 gcd ( 𝑁 + ( 1 · 𝑀 ) ) ) )
3	1 2	mp3an1	⊢ ( ( 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( 𝑀 gcd 𝑁 ) = ( 𝑀 gcd ( 𝑁 + ( 1 · 𝑀 ) ) ) )
4		zcn	⊢ ( 𝑀 ∈ ℤ → 𝑀 ∈ ℂ )
5		mulid2	⊢ ( 𝑀 ∈ ℂ → ( 1 · 𝑀 ) = 𝑀 )
6	5	oveq2d	⊢ ( 𝑀 ∈ ℂ → ( 𝑁 + ( 1 · 𝑀 ) ) = ( 𝑁 + 𝑀 ) )
7	6	oveq2d	⊢ ( 𝑀 ∈ ℂ → ( 𝑀 gcd ( 𝑁 + ( 1 · 𝑀 ) ) ) = ( 𝑀 gcd ( 𝑁 + 𝑀 ) ) )
8	4 7	syl	⊢ ( 𝑀 ∈ ℤ → ( 𝑀 gcd ( 𝑁 + ( 1 · 𝑀 ) ) ) = ( 𝑀 gcd ( 𝑁 + 𝑀 ) ) )
9	8	adantr	⊢ ( ( 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( 𝑀 gcd ( 𝑁 + ( 1 · 𝑀 ) ) ) = ( 𝑀 gcd ( 𝑁 + 𝑀 ) ) )
10	3 9	eqtrd	⊢ ( ( 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ) → ( 𝑀 gcd 𝑁 ) = ( 𝑀 gcd ( 𝑁 + 𝑀 ) ) )