Euclidean algorithm and Fermat’s theorem on sums of two squares
Euclidean algorithm, 也就是常说的辗转相除法, 通过有限步骤来找出两个整数 \(a,b\) 的最大公约数 \((a,b)\). 具体说来, \(a,b\in\Bbb Z\), 我们假定 \(b>0\), 并记 \(r_0=a, r_1=b\). 据带余除法, 可有 \[r_0=q_1r_1+r_2,\quad 0<r_2<r_1, q_1=\left[\frac{r_0}{r_1}\right];\] \[r_1=q_2r_2+r_3,\quad 0<r_3<r_2, q_2=\left[\frac{r_1}{r_2}\right];\] \[\cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots\] \[r_{n-1}=q_nr_n,\quad q_n=\left[\frac{r_{n-1}}{r_n}\right].\] \(\left[x\right]\) …
Euclidean algorithm and Fermat’s theorem on sums of two squares Read More