Numbers and Numerical Operations【数字与数值运算】

Divisibility【可约分性】

Greatest Common Divisor & Least Common Multiple【最大公约数与最小公倍数】

Modular Arithmetic【模运算】

Euclidean Algorithm【欧里几德算法】

数字与数值计算

Notation for Numbers

• 自然数（Natural Numbers）：
  • $N = \{0,1,2,...\}$
• 整数（Integers）：
  • $Z=\{...,-1,0,1,2,...\}$
• 正整数（Positive Integers）：
  • $N_{>0}=Z_{>0}=\{1,2,...\}$
• 有理数/分数（Rational Numbers / Fractions）：
  • $Q=\{\frac{m}{n}:m,n \in Z,n \ne 0\}$
• 实数（Real Numbers）：
  • $R=a_1 a_2...a_k b_1 b_2 ...$

在$N$和$Z$中，不同的数字代表不同的数值：

在$Q$和$R$中，不同的数字可以代表相同的数值：

实数与整数之间的转换

使用最大整数(ceiling)与最小整数（floor）概念。

• 最大整数 $⌈x⌉$：$the\ greatest\ integer \le x$
• 最小整数 $⌊x⌋$：$the\ least\ integer \ge x$

以下是一些关于最大整数与最小整数的简单理论：

可约分性

定义

对于 $m,n \in Z$，如果$n = k * m, k \in Z$，我们可以称$m$可约$n$（$m$ divides $n$），记作：

同时也可以说：

• $n$对$m$是可约的。（$n$ is divisible by $m$）
• $m$是$n$的约数。（$m$ is a divisor of $n$）
• $n$是$m$的倍数。（$n$ is a multiple of $m$）

最大公约数和最小公倍数

最大公约数：Greatest common divisor，GCD

最小公倍数：Least common multiple，LCM

最大公约数和最小公倍数是非负的，不管 $m$ $n$的正负性。

并且有事实：

由此可得，当 $m, n > 0$ 时，如果有：

则有：

即：$m,n$ 是互质数。

模运算

已知：对于任意的整数 $m$，均有：

可以用模运算符 $\%$ 或 $mod$ 对 $r$ 进行表示：

此外，模运算还存在同余概念：

这表示，$m$ 与 $p$ 在模 $n$ 的意义下同余（即在相同的除数的情况下具有相同的余数）。

需要注意的是，$m = _{(n)}p$ 并不是一个标准的数学符号，更常见的表示方法是：

以下是一些基本事实：

欧里几德算法

最基本的欧里几德算法没有涉及到模运算，它使用了递归的思路，经过大量重复之后回归到模运算的结果。

$gcd(m,n)=$

以下是当 $m>n$ 时，公式的证明方法：

然而，在掌握了模运算后，该公式可以简化为：

$gcd(m,n)=$