4 数论

整数运算

例：求 $3^{644} \mod 645$。先将 644 展开成二进制 1010000100。

初始化：$ i = 0 $；因为 $ a_0 = 0 $，所以有 $ x = 1 $ 和 $ \text{power} = 3^2 \mod 645 = 9 \mod 645 = 9 $。
$ i = 1 $；因为 $ a_1 = 0 $，所以有 $ x = 1 $ 和 $ \text{power} = 9^2 \mod 645 = 81 \mod 645 = 81 $。
$ i = 2 $：因为 $ a_2 = 1 $，所以有 $ x = 1 \cdot 81 \mod 645 = 81 $ 和 $ \text{power} = 81^2 \mod 645 = 6561 \mod 645 = 111 $。
$ i = 3 $：因为 $ a_3 = 0 $，所以有 $ x = 81 $ 和 $ \text{power} = 111^2 \mod 645 = 12321 \mod 645 = 66 $。
$ i = 4 $：因为 $ a_4 = 0 $，所以有 $ x = 81 $ 和 $ \text{power} = 66^2 \mod 645 = 4356 \mod 645 = 486 $。
$ i = 5 $：因为 $ a_5 = 0 $，所以有 $ x = 81 $ 和 $ \text{power} = 486^2 \mod 645 = 236196 \mod 645 = 126 $。
$ i = 6 $：因为 $ a_6 = 0 $，所以有 $ x = 81 $ 和 $ \text{power} = 126^2 \mod 645 = 15876 \mod 645 = 396 $。
$ i = 7 $：因为 $ a_7 = 1 $，所以有 $ x = (81 \cdot 396) \mod 645 = 32084 \mod 645 = 471 $ 和 $ \text{power} = 396^2 \mod 645 = 156816 \mod 645 = 81 $。
$ i = 8 $：因为 $ a_8 = 0 $，所以有 $ x = 471 $ 和 $ \text{power} = 81^2 \mod 645 = 6561 \mod 645 = 111 $。
$ i = 9 $：因为 $ a_9 = 1 $，所以有 $ x = (471 \cdot 111) \mod 645 = 52381 \mod 645 = 36 $。

最终求得结果 $x=36$。

$ gcd(78, 35) = gcd(35, 8)=gcd(8,3)=gcd(3,2)=gcd(2,1) $

例：将 $gcd(78,35)=1$ 用线性表示：

\[ 78,35,2,8\\ 35,8,4,3\\ 8,3,2,2\\ 3,2,1,1\\ 1 = 11\times35 - 13\times78 \]

OK

如果 p 是质数，a 是整数且不能被 p 整除，则： $$ a^{p-1} \equiv 1_(modp) $$

满足费马小定理的合数。