 Solution

For integers $m,n$ not both zero, their greatest common divisor is the greatest positive integer dividing both. For the degenerate pair $(0,0)$ use the conventional value zero. A number $d$ divides both $m,n$ exactly when it divides both $m+kn,n$: one direction uses closure of divisibility under sums; the reverse subtracts $kn$. The positive common-divisor sets are therefore identical, provingThis also holds for $(0,0)$ under the stated convention and does not depend on the signs of the integers.

Bezout identity states that there exist integers $a,b$ such that $am+bn=\gcd (m,n)$. If a prime $p$ divides $mn$ but does not divide $m$, then $\gcd (p,m)=1$, so choose $a,b$ with $ap+bm=1$. Multiplying by $n$ gives $apn+bmn=n$. Both terms on the left are divisible by $p$, so $p\mid n$. Thuswhich proves the Euclid lemma from the requested identity. The separately numbered entries use these arithmetic facts for the Fibonacci numbers.