Metamath Proof Explorer


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 ( 𝑁 + 𝑀 ) ) )