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={nm:m,n∈Z,n=0}
- 实数(Real Numbers):
- R=a1a2...akb1b2...
在N和Z中,不同的数字代表不同的数值:
1=2=3
在Q和R中,不同的数字可以代表相同的数值:
21=42=63
实数与整数之间的转换
使用最大整数(ceiling)与最小整数(floor)概念。
- 最大整数 ⌈x⌉:the greatest integer≤x
- 最小整数 ⌊x⌋:the least integer≥x
⌊π⌋=3=⌈e⌉
以下是一些关于最大整数与最小整数的简单理论:
1
因为有 ⌊−x⌋=−⌈x⌉,所以有⌊x⌋=−⌈−x⌉。
2
对于所有的 t∈Z,均有:
- ⌊x+t⌋=⌊x⌋+t
- ⌈x+t⌉=⌈x⌉+t
3
令 k,m,n∈Z,并且 k>1,m≥n,则 k 在区间 [n, m] 的整数倍数的数量为:
⌊km⌋−⌊kn−1⌋
可约分性
定义
对于 m,n∈Z,如果n=k∗m,k∈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
Definition of GCD
gcd(m, n)=largest d∈Z>0 such thatd∣m and d∣n.
最小公倍数:Least common multiple,LCM
Definition of LCM
lcm(m, n)=smallest k∈Z>0 such thatm∣k and n∣k.
最大公约数和最小公倍数是非负的,不管 m n的正负性。
并且有事实:
gcd(m,n) ∗ lcm(m,n)=∣m∣ ∗ ∣n∣
由此可得,当 m,n>0 时,如果有:
lcm(m,n)=m ∗ n
则有:
gcd(m,n)=1
即:m,n 是互质数。
互质数(Relatively Prime)
如果gcd(m,n)=1,我们就认为 m 和 n 是互质数,也说他们两个是互质的。
模运算
已知:对于任意的整数 m,均有:
m=n∗q+r,r∈[0,m)
可以用模运算符 % 或 mod 对 r 进行表示:
r=m%nr=m mod n
此外,模运算还存在同余概念:
m=(n)p if n∣(m−p)
这表示,m 与 p 在模 n 的意义下同余(即在相同的除数的情况下具有相同的余数)。
需要注意的是,m=(n)p 并不是一个标准的数学符号,更常见的表示方法是:
m=p (mod n)
以下是一些基本事实:
欧里几德算法
最基本的欧里几德算法没有涉及到模运算,它使用了递归的思路,经过大量重复之后回归到模运算的结果。
gcd(m,n)=
m, (m=n)gcd(m−n,n), (m>n)gcd(m,n−m), (m<n)
以下是当 m>n 时,公式的证明方法:
然而,在掌握了模运算后,该公式可以简化为:
gcd(m,n)=
m, (m=n or n=0)n, (m=0)gcd(m%n,n) (m>n>0)gcd(m,n%m) (0<m<n)