Site Overlay

离散数学笔记(数论部分)

divmod 记号

用法:

$ 2 = 8 \operatorname{div} 4 = 9 \operatorname{div} 4$ 除法向下取整

$ 0 = 8 \operatorname{mod} 4; 1 = 9 \operatorname{mod} 4 $ 除法余数

$ \equiv $ 记号

$ 17 \equiv 5 (\operatorname{mod} 6) $ 因为 17 - 5 = 12 ,能够整除 6。

$ a \equiv b \operatorname{mod} m $ 表示 a -b 可以整除 m,或者说 a,b 除以m之后余数相同,简称同余

$ | $ 记号

$ a|b $ 表示a能整除b。

模 m 算数

$ 7 +_{11}9 = (7+9) \operatorname{mod} 11 = 5 $

$ 7 \cdot_{11}9 = (7 \cdot 9) \operatorname{mod} 11 = 8 $

素数

大于 1 且只能被 1 和自己整除的数。

最大公约数 GCD

$ \operatorname{gcd}(a,b) $ 表示 a, b 的所有因数的交集中的最大值。

互素

$ \operatorname{gcd}(a,b) = 1 $$ a,b $ 互素。

欧几里德算法(辗转相除法)

两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。

$ \operatorname{gcd}(91, 287) $

$$
287 = 91 \cdot 3 +14\\
91 = 14 \cdot 6 + 7\\
14 = 7 \cdot 2 + 0
$$

所以 $ \gcd (14,7) = 7 = \operatorname{gcd}(91, 287) $

发表评论

电子邮件地址不会被公开。 必填项已用*标注