gcd 的对称性
求证
$$ \forall n\geq 2,1\leq i<n, \gcd(n,i)=\gcd(n,n-i) $$
不妨设 $i > n-i$
$$
\begin{aligned}
\gcd(n,i)&=\gcd(i,n\bmod i)=\gcd(i,n-i) \\
\gcd(n,n-i)&=\gcd(i,n-i)
\end{aligned}
$$
设
$$ \gcd(n,i)=g,n=gk_1,i=gk_2 $$
则
$$
\begin{split}
n-i&=g(k_1-k_2) \\
\gcd(n,n-i)&=g\gcd(k_1,k_1-k_2)=\gcd(k_1,k_2) \\
\gcd(n,i)&=g\gcd(k_1,k_2)
\end{split}
$$
最后修改于 2021-08-11