Loading...
注：本节内容为《具体数学》(原书第二版) 第四章 数论 4.3 素数的例子 的旁注。 P90 证明素数有无穷多个的补充 第一行写了如下的话： 这 $k$ 个素数没有一个能整除 $M$，因为他们都整除 $M-1$ 这个理由看起来不怎么好理解，我们这么看见就好了： 也就是 $M$ 模任何一个数都为 $1$。而最小的素数为 $2$，即不能被任何素数整除。 P90 欧几里得数的补充 为什么欧几...
注：本节内容为《具体数学》(原书第二版) 第四章 数论 4.2 素数 的旁注。 P88 关于唯一分解定理的证明 本页下方写道： 我们要证明 $p_1 = q_1$。如若不然，我们可以假设 $p_1 < q_1$ 突然冒出这句话让人非常不解。这里做出补充。 我们的最终目的是证明所有分解出的素数按照从小到大的顺序排列都是相同的。那么对于 所以我们证明了他们分别是公约数和公倍数。接下来...
Stern-Brocot Tree 我们主要研究下面几个问题： 为何出现在这棵树中的每个数都是最简分数，即 $m\perp n$ 为何所有可能的分数 $m/n$ 都恰好出现一次 为何所有的数从左到右都是递增的 介绍 参加具体数学 4.5 互素 Relative Primality 重要结论：$m'n-n'm=1$ 证明： 我们首先验证初始情况：$1\times 1-0\times 0=...
引言 再看扩展欧几里得的时候，我一直有一个疑问，即： 为什么扩欧一定有解？ 我们可以通过说明欧几里得算法一定有解，来论证扩展欧几里得也一定有解。这显然是正确的，但是这个结论总感觉有点微妙。 我们不妨来考虑下面这个问题：对于方程 特例 注意：裴蜀定理有非常有用的特例： 方程 $ax+by=1$ 有整数解 $(x,y)$ 当且仅当 $a,b$ 互素，即 $\gcd(a,b)=1, ...
欧几里得算法与扩展欧几里得算法 注：本节可以独立阅读，但同时也是 《具体数学》(原书第二版) 4.1 整除性 的旁注。 一个基本事实 记 $n = am + b$，其中 $n,m,a,b \in \mathbb Z$，则 $d$ 为 $m,n$ 的公因数当且仅当 $d$ 为 $m,b$ 的公因数。 证明： 充分性： 若 $d \mid m$，$d \mid n$ 则必有 是一个等价结论，所...
注：本节内容为《具体数学》(原书第二版) 第二章 2.7 无限和式 的旁注。 背景 看这节的时候，从定义开始就非常绕，所以特意写一篇独立的文章，来补充无限和式这节。 每一项都非负时无限和式值的定义 在 $a_k \geq 0$，$K$ 可以是无限的情况下，定义：如果有一个常数 $A$ 为界，使得所有有限子集 $F \subset K$ (注意，这里一定是真包含) 都有 总结与反思 纵观整个...