第1620题：一个最大公约数小定理

本题反复利用 $(a,b)=(a-b,b)$ 及 $(a,b)=(a+b,b)$ 证明一个定理.

设 $u,v$ 是两个互素的正奇数，证明 $(2^u+1,2^v+1)=$ ？

不妨设 $u>v$ ,则

$(2^u+1,2^v+1)$

$=(2^u-2^v,2^v+1)$

$=(2^v(2^{u-v}-1),2^v+1)$

$=(2^{u-v}-1,2^v+1)$

$=(2^{u-v}+2^v,2^v+1)$

如果 $u-v>v$ ，那么可得

$(2^u+1,2^v+1)=$$(2^{u-2v}+1,2^v+1)$

如果 $u-v \leqslant v$ ，那么可得

$(2^u+1,2^v+1)=$ $(2^{2v-u}+1,2^v+1)$

用 $u-2v($ 或 $2v-u$ )代替 $u$ 重复上述讨论，利用辗转相除的方法，可得

$(2^u+1,2^v+1)=$ $2^{(u,v)}$ $+1$ $=$ ?

注意：每一次辗转相除得到的两个幂次都为奇数.