= 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, proving
$$
\boxed{\gcd(m,n)=\gcd(m+kn,n)}.
$$
This 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$. Thus
$$
\boxed{p\mid mn\ \Longrightarrow\ p\mid m\text{ or }p\mid n},
$$
which proves the <Euclid lemma> from the requested identity. The separately numbered entries use these arithmetic facts for the <Fibonacci numbers>.
Back to article page
