Skip to content

Instantly share code, notes, and snippets.

@scturtle
Created May 31, 2012 16:03
Show Gist options
  • Save scturtle/2844408 to your computer and use it in GitHub Desktop.
Save scturtle/2844408 to your computer and use it in GitHub Desktop.
Number Theory - Mathematics for Computer Science

Number Theory - Mathematics for Computer Science

Divisibility

整除的性质:

Lemma 23. The following statements about divisibility hold.

  1. If $a\mid b$, then $a\mid bc$ for all $c$.
  2. If $a\mid b$ and $b\mid c$, then $a\mid c$.
  3. If $a\mid b$ and $a\mid c$, then $a\mid sb+tc$ for all $s$ and $t$.
  4. For all $c \neq 0$, $a\mid b$ if and only if $ca\mid cb$.

质数是大于1的除了1和其本身不被其它数整除的数.

Theorem 24. Let $p$ be a prime. If $p \mid a_1a_2 ... a_n$, then $p$ divides some $a_i$.

除数和余数的唯一性:

Theorem 25 (Division Algorithm). Let $n$ and $d$ be integers such that $d > 0$. Then there exists a unique pair of integers $q$ and $r$ such that $n = qd + r$ and $0 ≤ r < d$.

余数被记做 $b\ rem\ a$. $rem$ 相当于 $%$.

Modular Arithmetic

高斯定义 $a$$b$$c$ 同余当且仅当 $c \mid (a − b)$. 记做 $a \equiv b (mod\ c)$.

Lemma 26. $a\equiv b (mod\ c)$ if and only if $(a\ rem\ c)=(b\ rem\ c)$

加法

$a\equiv b(mod\ n)$ implies $a+c\equiv b+c (mod\ n)$

乘法

Lemma 27.

  1. If $a_1\equiv b_1(mod\ n)$ and $a_2\equiv b_2(mod\ n)$, then $a_1 a_2\equiv b_1 b_2(mod\ n)$.
  2. $a\ rem\ n \equiv a (mod\ n)$.
  3. $(a_1\ rem\ n) \cdot (a_2\ rem\ n) \cdots (a_k\ rem\ n) \equiv a_1 \cdot a_2 \cdots a_k (mod\ n)$.

消去律(狭义)

Lemma 28.
Suppose $p$ is a prime and $k$ is not a multiple of $p$. If $a k \equiv b k\ (mod\ p)$ then $a\equiv b\ (mod\ p)$.

重排律(狭义)

Corollary 29. Suppose p is a prime and k is not a multiple of p. Then the sequence:
$(0\cdot k)\ rem\ p, (1\cdot k)\ rem\ p, (2\cdot k)\ rem\ p, \cdots, (p−1)\cdot k\ rem\ p$
is a permutation of the sequence:
$0, 1, 2, \cdots, (p−1)$
This remains true if the first term is deleted from both sequence.

除法

乘法逆元(狭义)

Corollary 30. Let $p$ be a prime. If $k$ is not a multiple of $p$, then there exists an integer $ k^{−1} \epsilon \{1, 2, \cdots, p − 1\}$ such that $k \cdot k^{−1} \equiv 1\ (mod\ p)$.

费马小定理

Theorem 31 (Fermat’s Theorem). Suppose $p$ is a prime and $k$ is not a multiple of $p$. Then: $k^{p−1} \equiv 1\ (mod\ p)$.

根据费马小定理求乘法逆元: $k^{−2} \cdot k \equiv 1\ (mod\ n)$.

线性组合

Theorem 35. $gcd(a,b)$ is equal to the smallest positive linear combination of $a$ and $b$.

Corollary 36. Every linear combination of $a$ and $b$ is a multiple of $gcd(a, b)$ and vice versa.

$gcd(a,b)$ 的倍数和 $a,b$ 的线性组合可以互相转换, 在证明中非常有用.

最大公约数的一些性质:

Lemma 38. The following statements about the greatest common divisor hold:

  1. Every common divisor of $a$ and $b$ divides $gcd(a, b)$.
  2. $gcd(ka,kb)=k \cdot gcd(a,b)$ for all $k>0$.
  3. If $gcd(a,b) = 1$ and $gcd(a,c) = 1$, then $gcd(a,bc) = 1$.
  4. If $a \mid bc$ and $gcd(a,b)=1$,then $a \mid c$.
  5. $gcd(a, b) = gcd(a\ rem\ b, b)$ (Euclid’s algorithm).

算数基本定理:

Every positive integer $n$ can be written in a unique way as a product of primes:
$n = p1 \cdot p2 \cdots pj\ (p1 \leq p2 \leq \cdots \leq pj)$

需要强调两点:

  • 1不能算质数
  • 0个质数相乘结果应该记为1

Lemma 40. If $p$ is a prime and $p \mid ab$, then $p \mid a$ or $p \mid b$.
Lemma 41. Let $p$ be a prime. If $p \mid a_1 a_2 \cdots a_n$, then $p$ divides some $a_i$.

任意模数的运算

a 和 b 互质当且仅当 $gcd(a,b) = 1$.

欧拉函数 $\phi(n)$ 定义为 $\{1,2, \cdots, n-1\}$ 中和 n 互质的个数.

$\phi(n)$的求法:

Theorem 42. The function $\phi$ obeys the following relationships:

  1. If $a$ and $b$ are relatively prime, then $\phi(ab) = \phi(a)\phi(b)$.
  2. If $p$ is a prime, then $\phi(p^k)=p^k −p^{k−1}$ for $k\geq 1$.

乘法逆元(广义)

Lemma 43. Let $n$ be a positive integer. If $k$ is relatively prime to $n$, then there exists an integer $k^{−1}$ such that $k \cdot k^{−1} \equiv 1\ (mod\ n)$.

消除律(广义)

Corollary 44. Suppose $n$ is a positive integer and $k$ is relatively prime to $n$. If $ak \equiv bk\ (mod\ n)$ then $a \equiv b\ (mod\ n)$.

Euler’s Theorem

a generalization of Fermat’s Theorem to an arbitrary modulus

重排律(广义)

Lemma 45. Suppose $n$ is a positive integer and $k$ is relatively prime to $n$.
Let $k_1, \cdots, k_r$ denote all the integers relatively prime to n in the range $0 \leq k_i \lt n$.
Then the sequence:
$(k_1 \cdot k)\ rem\ n, (k_2 \cdot k)\ rem\ n, (k_3 \cdot k)\ rem\ n, \cdots, (k_r \cdot k)\ rem\ n$
is a permutation of the sequence:
$k_1, k_2, \cdots, k_r$

Then

Theorem 46 (Euler’s Theorem). Suppose $n$ is a positive integer and $k$ is relatively prime to $n$. Then: $k^{\phi(n)} \equiv 1\ (mod\ n)$

We can find multiplicative inverses using Euler’s theorem as we did with Fermat’s theorem: if $k$ is relatively prime to $n$, then $k^{\phi(n)−1}$ is a multiplicative inverse of $k$ modulo $n$.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment