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

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 mullid ⊢ ( 𝑀 ∈ ℂ → ( 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 ( 𝑁 + 𝑀 ) ) )