最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

【数论与组合数学 1】数论简介、素数、算数基本定理

来源：博客园

数论简介、素数、算数基本定理

一、数的演化

  1. \(自然数 N \Rightarrow (取反) \Rightarrow 整数 Z \Rightarrow (除) \Rightarrow 有理数 Q \Rightarrow (实分析 / Dedekind Cut) \Rightarrow 实数 R \Rightarrow (负数开方) \Rightarrow 复数 C\)


    (资料图片)

  2. 定理 1：\(\sqrt{2}\) 是无理数

  • 证明：

    假设\(\sqrt{2}\) 是有理数，则满足：\(\sqrt{2}=a/b\)

    其中 a，b 为互质的正整数。则：\(a^2/b^2=2\) ，\(a^2=2b^2\)。因此，a 一定是偶数。

    令\(a=2k\) ，则 \(2b^2 = (2k)^2\)，\(b^2=2k^2\) ，b 一定是偶数。

    这与 a，b 互质相矛盾。

二、自然数

  1. 自然数的基本性质

    1. successor operation：\(s(n)=n+1\) 通过当前数找下一个数。

    2. 数学归纳法 PMI：\(P(1)\) 为真，且 \(P(n) \Rightarrow P(n+1)\) 。因此如果 \(P(n)\) 成立，所有的自然数也成立。

    3. 良序定理 WOP：自然数集的每个非空子集都有个最小元素，即自然数在其标准的大小关系下构成一良序集。

三、整除 (Divisibility)

  1. $ a|b \quad (a 整除 b)，$满足 \(b=ax\) ，且 \(a, b, x \in Z\) 且 \(a \neq 0\) 。

  2. 对于 $ \forall n \in N ，n | 0 $ 。

  3. \(a|b，b|c \Rightarrow a | c\) 。

  4. $ a|b，a|c \Rightarrow a|(bx+cy)$

    例子：3|6，6|36\(\Rightarrow\) 3|36 7|14，7|35 \(\Rightarrow\) 7|(14 \(\times\) 3 + 35 \(\times\) 2 = 112)

四、带余除法 (被除数=除数\(\times\)商+余数)

  1. 定理1：假设 $a，b \in Z $ 且 \(a>0\)，则 $ \exists q,r \in Z$，满足\(b=aq+r，0 \leq r < a\)

  • 证明：

    令$ S= {b+ka：k \in Z，b+ka \geq 0}$

    S 非空：

    \[\begin{cases}b>0，当 (b+0a) \in S\\b<0, 当累加 a 足够多次数使其为正数\\\end{cases}\]

    因为 S 非空，对于某些 k ，它便有一个最小的元素\(r=b+ka\) (WOP)。

    令$ q=-k$，则 \(r=b-qa\)。由于 r 在 S 中，故 \(r \geq 0\) 。

    而且\(r

五、最大公因数 GCD(Greatest Commom Divisor)

  1. 如果 a 和 b 都不为 0，\(gcd(a,b)\) 或者 \((a,b)\) 为 a 和 b 的最大公因数
  • 例子：\(gcd(24,38) = 2\)
  1. 定理2：如果 $ g=gcd(a,b)$，则 $ \exists , x_0，y_0 \in Z$，使 $ g=ax_0 + by_0$ 。

  • 证明：

    令$ S = {ax+by：x，y \in Z，ax+by>0 }$，并且假设 a，b 不全为零。

    假设$ a \neq 0$，S 非空：

    \[ \begin{cases}a>0，\Rightarrow a \in S \\a<0， \Rightarrow -a \in S\\\end{cases}\]

    由于 S 非空，故有一个最小元素$ g=ax+by$ (WOP)

    反证 \(g|a\) ：假设 g 不整除 a，\(a=gq+r，0

    则\(r=a-gq=a-q(ax+by)=a(1-qx)-b(qy) \Rightarrow r \in S\)

    然而，\(r

    如果 \(d|a\) ， 并且 \(d|b\) ，那么 \(d|ax+by=g\)。

    由于 \(g|a，g|b\)，并且 g 是最大的公共因数，则 \(g=gcd(a,b)\)

六、互素 (Coprime)

  1. 如果 $ gcd(a,b)=1$，则 a，b 互素
  • 例子：10 和 9 互素，10 和 12 不互素
  1. 推论：如果 \(gcd(a,m)=1\) 并且 \(gcd(b,m)=1\)，则 \(gcd(ab,m)=1\)

  • 证明：

    $ 1=ax+my，ax=1-my，$ \(1=bx^{"}+my^{"}\)，\(bx^{"}=1-my^{"}\)

    \(abxx^{"}=(1-my)(1-my^{"})=1-my-my^{"}+m^{2}yy^{"}=1+m(-y-y^{"}+myy^{"})\)

    \(1=ab(xx^{"})+m(y+y^{"}-myy^{"})\)

  • 例子： \(gcd(5,24)=1，gcd(7,24)=1 \Rightarrow gcd(35,24)=1\)

  1. 推论：如果 \(c| ab\)，并且 \(gcd(c,a)=1\)，那么 \(c|b\) 。

  • 证明：

    \(gcd(a,c)=1 \Rightarrow 1=ax+cy \Rightarrow b=abx+bcy\)

    \(c|ab，c|bc \Rightarrow c|(abx+bcy)=b\)

  • 例子：\(35|1050，gcd(35,6)=1 \Rightarrow 35|175\)

七、欧几里得GCD算法(辗转相除法)

  1. 给定 \(a，b \in Z\)，并不全为 0，可通过如下步骤找到 \(gcd(a,b)\)：
    1. 如果 \(a,b<0\)，取对应的相反数。
    2. 如果 \(a>b\)，交换 \(a,b\) 。
    3. 如果 \(a=0\)，\(gcd(a,b)=b\) 。
    4. 如果 \(a>0\)，令 \(b=aq+r，0 \leq r

  • 证明：

    第一步和第二步不影响 GCD，所以只需要证明当\(b=aq+r\)时，\(gcd(a,b)=gcd(r,a)\)

    令\(d=gcd(r,a)\) 并且 \(e=gcd(a,b)\)。

    由\(d=gcd(r,a) \Rightarrow d|a，d|r \Rightarrow d|aq+r=b \Rightarrow d|a,b \Rightarrow d|gcd(a,b)=e\)

    \(e=gcd(a,b) \Rightarrow e|a，e|b \Rightarrow e|b-aq=r \Rightarrow e|r,a \Rightarrow e|gcd(r,a)=d\)

    由于 d 和 e 都是正数并且互相整除，因此 \(d=e\) 。

八、素数

  1. 素数 p 是一个大于一的整数，并且不能被写成 \(p=ab，a,b>1\) 的形式。
  • 例子：11是素数，111不是素数
  1. 定理3(算数基本定理)：每个正整数都能写成素数乘积的形式 (素数重复但表达式唯一)
  • 例子：\(72=2^{3} \times 3^{2}\)，\(999999=3^{3} \times 7 \times 11 \times 13 \times 37\)

  1. 推论：如果 \(p|a_{1}a_{2} \cdots a_{n}\)，那么对于某些 i，满足 \(p|a_{i}\) 。

  2. 定理4：有无限多的素数

    证明：

    假设有有限个素数\(p_{1}，p_{2}，\cdots，p_{n}，n \geq 1\) 。

    令$ N=p_{1}p_{2}\cdots p_{n}+1$，根据算数基本定理，一定有一个素数整除 N。

    由欧几里得gcd算法可知：\((p_{i},p_{1}p_{2}\cdots p_{n}+1) = (p_{i},1) = 1\)，所以 \(p_{i}\) 不整除 N。

    所以对于任意的 i，\(q \neq p_{i}\)，并且 q 是一个新的素数，与假设冲突。

  3. 与素数相关的著名猜想

  • 哥德巴赫猜想(Goldbach Conjecture)
  • 孪生素数猜想(Twin Prime Conjecture)
  • 梅森素数猜想(Mersenne Prime Conjecture) 等

关键词：