具体数学-第10课（素数和阶乘的有趣性质二）

互素

定义

m 和 n 互素定义为 ，记作 。

互素也有很多性质。

性质1

性质2

其中 就是两个数的素数指数表示法，详细定义见上一节课。

或者可以表示为

性质3

Stern-Brocot树

如上图所示，Stern-Brocot树就是0到1之间的分数生成的一棵二叉树。

初始时只有 两个数，第一轮将两者分母相加，分子也相加作为新的分数的分母分子。第二轮再对相邻的两个分数做相同的操作，生成新的分数序列。不断生成下去，得到了上图的二叉树。

Stern-Brocot树有下面四个性质：

1. 0到1之间的所有有理数都出现在了这棵树中。
   
2. 每个分数仅出现了1次。
   
3. 每个分数都是不可约分的，即分子分母互素。
   
4. 生成的序列是单调递增的。
   

下面我们来一个一个证明。

引理

对于相邻的两个分数 ，满足：

证明

用数学归纳法证明。

性质4就是证明：

结论是很显然的，这样性质2同时就成立了。

性质1的话，对于任意有理数 ，假设 。

我们采用如下策略生成 。

• 如果 ，那么成功。
• 如果 ，那么令 。
• 如果 ，那么令 。

那么有

所以

而左边式子就等于 ，所以

因为 都在不断增加，所以最多 轮就能生成 。

性质3的话，同样用数学归纳法。通过引理可以得到

由扩展欧几里得定理可以得到 与 互素。

Farey序列

我们引申出Farey序列的概念，定义如下：

关于它的更多性质，留到下一节课继续。