数论 | 欧拉函数：定义与基础示例

1. 公式
   观察依据

   黑板上显示定义式中的函数符号 $\varphi$：$\varphi$ : $\mathbb{N} \rightarrow \mathbb{N}$。

2. 声音
   观察依据

   主讲人称其为“欧拉 phi 函数”或“欧拉总计函数”。

$\varphi$

欧拉总计函数用于计算小于或等于 n 且与 n 互质的正整数个数。

n 是自然数

1. 公式
   观察依据

   变量 n 出现在 $\varphi(n)$ 中，也出现在集合条件 $1 \le m \le n$ 里。

2. 声音
   观察依据

   主讲人在解释定义域与陪域时提到“自然数”。

n

输入至总计函数的一个自然数。

n 是自然数

1. 公式
   观察依据

   变量 m 是集合 \{ $1 \le m \le n \mid \gcd(m,n)=1$ \} 中的哑元元素。

m

一个从 1 到 n 的整数，用于检验它是否与 n 互质。

1 小于等于 m 小于等于 n

1. 公式
   观察依据

   表达式 $\gcd(m,n)=1$ 出现在黑板上，作为该集合中元素的隶属条件。

2. 声音
   观察依据

   说话人说“与 n 互素”，随后明确计算“2 与 8 的最大公约数为 2”。

$\gcd$

最大公约数函数；$\gcd(m,n)=1$ 表示 m 和 n 除 1 外没有其他公因数。

m、n 为自然数

1. 公式
   观察依据

   黑板上在定义下方写有 = |$U_n$|。

2. 声音
   观察依据

   说话人提到“模 n 的单位群”。

$U_n$

模 n 的单位群，即在模 n 乘法运算下与 n 互素的整数构成的群。

n 为自然数

1. 公式
   观察依据

   左板显示$\varphi:\mathbb{N}\to\mathbb{N}$和$\varphi(n)=\#\{1\le m<n\mid \gcd(m,n)=1\}$；右板随后显示$\varphi(p)=p-1$。

$\varphi$

欧拉函数，定义为小于$n$且与$n$互质的正整数的个数。

输入是一个自然数$n$；输出是一个非负整数计数值。

1. 公式
   观察依据

   定义式中使用了$\varphi(n)$，并附带条件$1\le m<n$。

$n$

欧拉函数一般定义中自变量所取的自然数。

对应的式子为：$n\in\mathbb{N}$。

1. 公式
   观察依据

   集合构建式定义使用 $m$ 在 $\{1\le m<n\mid \gcd(m,n)=1\}$ 中；证明中写作 $1\le m<p$ 且 $\gcd(p,m)=1$。

$m$

一个待检验是否与$\varphi$的自变量互质的整数。

在定义中为$1\le m<n$；在证明中为$1\le m<p$。

1. 公式
   观察依据

   定义中包含$\gcd(m,n)=1$，而证明最终得出$\gcd(p,m)=1$。

$\gcd(\cdot,\cdot)$

最大公约数函数；等于1表示两个整数互质。

应用于诸如$(m,n)$或$(p,m)$这样的正整数。

1. 公式
   观察依据

   左板书上写着$\varphi(n)=\#\{1\le m<n\mid \gcd(m,n)=1\}$。

$\#$

基数算子，用于计算所显示集合中元素的个数。

适用于整数的有限集合。

1. 公式
   观察依据

   右板书上写着‘对素数 p’，随后是$\varphi(p)=p-1$；该证明使用了$p$和$1\le m<p$的因数。

$p$

在命题及证明中，作为欧拉函数特殊输入的一个素数。

$p$是素数。

1. 公式
   观察依据

   左板书欧拉函数定义下方另有一行，形似$=|U_n|$。

1. 在所采样的帧中，该符号仅部分可辨。

2. 本片段未说明其作用。

$|U_n|$

定义下方可见另一表达式；可能为基数记号，但本片段未明确其确切含义。

本片段无法判断。

1. 公式
   观察依据

   黑板显示定义：欧拉函数 $\varphi$ : $\mathbb{N} \rightarrow \mathbb{N}$，且 $\varphi(n)$ = \# \{ $1 \le m \le n \mid \gcd(m,n)=1$ \}。

2. 声音
   观察依据

   说话人陈述：“我们将其定义为从自然数集到自然数集的函数……且 $\varphi(n)$ 等于该集合中元素的个数……即所有介于 1 与 n 之间且与 n 互素的自然数。”

欧拉函数 $\varphi(n)$ 计算不超过 n 的正整数 m 的个数，这些 m 与 n 互素（即它们的最大公约数为 1）。

1. n 是一个自然数

1. $\varphi$
2. n
3. m
4. $\gcd$

1. 公式
   观察依据

   主讲人在集合定义正下方直接写下 = |$U_n$|。

2. 声音
   观察依据

   主讲人解释道，模 n 的单位群恰好包含这些元素，因此其元素个数等于模 n 的单位群的元素个数。

$φ(n)$ 的值等于模 n 的整数乘法群（记作 $U_n$）的阶（即大小）。

1. n 是一个自然数。

1. 欧拉函数的定义
2. $U_n$

1. 公式
   观察依据

   左板书展示了$\varphi:\mathbb{N}\to\mathbb{N}$和$\varphi(n)=\#\{1\le m<n\mid \gcd(m,n)=1\}$。

2. 声音
   观察依据

   主讲人提到，在证明下一个结论之前，他们已‘定义了欧拉函数’。

视频将欧拉函数呈现为一个从自然数到自然数的映射。对每个$n$，$\varphi(n)$统计满足$m$和$1\le m<n$的整数个数$\gcd(m,n)=1$。用文字表述，它统计的是小于$n$且与$n$互素的正整数个数。

1. $n$是一个自然数。

2. 被统计的整数$m$满足$1\le m<n$。

3. 互素性由$\gcd(m,n)=1$表示。

1. 公式
   观察依据

   右侧黑板显示$\varphi(15)=\#\{1,2,4,7,8,11,13,14\}=8$。

2. 声音
   观察依据

   主讲人说，他们不得不跳过12、跳过9，依此类推，而计数结果为8。

该例题直接应用定义计算$n=15$。所列集合包含所有小于15且与15互素的整数，最终计数结果为8。口述讲解强调需排除3和5的倍数，这与黑板上可见的列表一致——列表中省略了诸如3、6、9、12和15等数字。

1. 使用定义，代入$n=15$。

2. 仅考虑整数 $m$ 满足 $1\le m<15$ 的情况。

3. 仅保留满足 $m$ 的那些 $\gcd(m,15)=1$。

1. 欧拉函数的定义

1. 公式
   观察依据

   右侧黑板上写着：“命题：对任意素数p，有$\varphi(p)=p-1$。”

2. 声音
   观察依据

   讲师表示将证明一个关于素数的$\varphi$值的公式。

对每一个素数$p$，都有$\varphi(p)=p-1$。

1. $p$是素数。

对所有素数$p$成立。

1. 公式
   观察依据

   右侧黑板上的证明包含以下内容：‘注意到p的唯一正因数是1和p’，‘令$1\le m<p$’，以及‘$p\nmid m \Rightarrow \gcd(p,m)=1$’。

2. 声音
   观察依据

   讲师解释道：$p$的唯一正因数是1和$p$；任何$m<p$都不能被$p$整除；因此$\gcd(p,m)=1$；于是从1到$p-1$的所有整数都被计入。

1. 公式

   $$$$
   解释

   从如下事实出发：若$p$是素数，则它的唯一正因数是1和它自身$p$。

   步骤依据

   素数的定义。

   视频直接表达
2. 公式

   $$1\le m<p$$
   解释

   取一个任意整数$m$，它位于欧拉函数定义中输入$p$所使用的范围内。

   步骤依据

   $\varphi(p)$的定义统计了满足与$m$互素的$1\le m<p$。

   视频直接表达
3. 公式

   $$p\nmid m$$
   解释

   由于$m$严格小于$p$，因此$m$不可能是$p$的倍数。

   步骤依据

   $p$的一个正倍数至少为$p$本身。

   视频直接表达
4. 公式

   $$\gcd(p,m)=1$$
   解释

   由于$p$的唯一正因数是1和$p$，且$p$不能整除$m$，因此$p$与$m$的唯一公因数是1。

   步骤依据

   $p$与$m$的公因数必为$p$的因数；排除$p$后，仅剩1。

   视频直接表达
5. 公式

   $$\varphi(p)=p-1$$
   解释

   因此每个整数 $m$ 与 $1\le m<p$ 互质$p$，因此所计数的集合恰好有 $p-1$ 个元素。

   步骤依据

   应用 $\varphi$ 的定义，前提是先确立 $\gcd(p,m)=1$ 对所有 $1\le m<p$ 成立。

   视频直接表达

从1到$p-1$的所有整数均与质数$p$互素，因此有$\varphi(p)=p-1$个。

1. 公式
   观察依据

   黑板上显示 $φ(5)$ = # { 1, 2, 3, 4 } = 4。

2. 声音
   观察依据

   主讲人列出所有小于 5 且与 5 互素的正整数：1、2、3 和 4，并得出 $φ(5) = 4$。

计算 $φ(5)$。

1. n 等于5

求满足 $1 \le m \le 5$ 且 gcd(m, 5) = 1 的整数 m 的个数。

1. 公式

   $$\{ 1, 2, 3, 4 \}$$
   解释

   列出从 1 到 5 中所有与 5 互素的整数。

   步骤依据

   由于5是质数，所有小于5的正整数都与它互质。

   视频直接表达
2. 公式

   $$4$$
   解释

   统计该集合中的元素个数。

   步骤依据

   共列出4个元素。

   视频直接表达

$φ(5) = 4$

直接计数与定义一致。

1. 公式
   观察依据

   黑板上显示 $φ(8)$ = #{1, 3, 5, 7} = 4。

2. 声音
   观察依据

   主讲人跳过偶数，因为它们与8的最大公约数不等于1（例如：gcd(2,8) = 2，gcd(4,8) = 4，gcd(6,8) = 2），剩下1、3、5、7。

计算 $φ(8)$。

1. n 等于 8

求满足$1 \le m \le 8$且 gcd(m,8) = 1的整数 m 的个数。

1. 公式

   $$\{ 1, 3, 5, 7 \}$$
   解释

   列出从1到8的所有奇数。

   步骤依据

   偶数共享一个因数 2 与 8，因此它们与 8 不互质。

   视频直接表达
2. 公式

   $$4$$
   解释

   统计集合中的元素个数。

   步骤依据

   所列元素共有4个。

   视频直接表达

$φ(8) = 4$

直接计数并逐一验证最大公约数，可确认该结果。

1. 公式
   观察依据

   黑板上显示：$φ(15)$ = #{1, 2, 4, 7, 8, 11, 13, 14}。

2. 声音
   观察依据

   讲话者列举了所有与15互质的数，并明确跳过了3和5的倍数（即3、5、6、9、10、12、15）。

1. 视频结束前，黑板上未写出$φ(15)$的最终计数值，但该集合包含8个元素。

计算$φ(15)$。

1. n 等于15

求满足$1 \le m \le 15$且gcd(m, 15) = 1的整数m的个数。

1. 公式

   $$\{ 1, 2, 4, 7, 8, 11, 13, 14 \}$$
   解释

   列出从1到15之间所有不与15有公共因数的整数（即不能被3或5整除）。

   步骤依据

   $15 = 3 \times 5$，因此任何3或5的倍数与1的最大公约数都大于15。

   视频直接表达

该集合包含8个元素，故 $φ(15) = 8$（隐含结论，黑板上未明确写出最终数值）。

统计所列元素个数，得到8。

1. 公式
   观察依据

   右侧板书列出了$\varphi(15)=\#\{1,2,4,7,8,11,13,14\}=8$。

2. 声音
   观察依据

   讲师说跳过12、跳过9，依此类推，然后计数得到8。

利用欧拉函数的定义计算$\varphi(15)$。

1. 对应的式子为：$n=15$。

2. $\varphi(n)$统计满足$m$且$1\le m<n$和$\gcd(m,n)=1$的整数个数。

求小于15且与15互素的正整数的个数。

1. 公式

   $$1\le m<15$$
   解释

   考虑小于15的候选整数。

   步骤依据

   直接依据$\varphi(15)$的定义。

   视频直接表达
2. 公式

   $$\{1,2,4,7,8,11,13,14\}$$
   解释

   仅保留那些与15的最大公约数为1的候选数；黑板上显示的是这一留存集合。

   步骤依据

   $\gcd(m,15)=1$的应用。

   视频直接表达
3. 公式

   $$8$$
   解释

   统计所展示集合中的元素个数。

   步骤依据

   所列有限集合的基数。

   视频直接表达

对应的式子为：$\varphi(15)=8$。

口述讲解中提到跳过诸如9和12这样的倍数，这与排除那些与15有公共因子的数是一致的。

1. 公式
   观察依据

   右侧黑板同样展示了$\varphi(5)=\#\{1,2,3,4\}=4$和$\varphi(8)=\#\{1,3,5,7\}=4$。

1. 这些例子在本片段中可见，但未口头详细演算。

阅读黑板上已写出的其余欧拉函数示例。

1. 对应的式子为：$\varphi(5)=\#\{1,2,3,4\}=4$。

2. 对应的式子为：$\varphi(8)=\#\{1,3,5,7\}=4$。

直接记录黑板上显示的示例数值，无需额外推导。

1. 公式

   $$\varphi(5)=4$$
   解释

   黑板列出了小于5的四个正整数，并给出其个数。

   步骤依据

   黑板上可见的已演算示例。

   视频直接表达
2. 公式

   $$\varphi(8)=4$$
   解释

   黑板列出了小于8的奇数，并给出其个数。

   步骤依据

   黑板上可见的已演算示例。

   视频直接表达

$\varphi(5)=4$和$\varphi(8)=4$。

两条线均符合左侧黑板上所示的同一集合计数定义。

1. 图示
   观察依据

   黑板被一条黄色竖直线分割。左侧预先写有欧拉函数的定义。

1. 黑板

2. 黄色分隔线

3. 左侧预先写好的文字

1. 左侧在举例过程中保持不变。

该布局将形式化定义与具体例题计算分隔开来。

1. 动画
   观察依据

   主讲人于右侧写下“例题”，并依次计算 $φ(5)$、$φ(8)$ 和 $φ(15)$。

1. 粉笔

2. 黑板右侧

1. 文字随说话者逐个计算示例而依次出现。

1. 左侧的定义始终保持可见。

将定义应用于具体数字的视觉化过程。

1. 动画
   观察依据

   黑板右侧包含示例的部分被擦除，仅左侧的定义保持可见。

2. 声音
   观察依据

   讲师表示他将清理黑板，然后证明一个关于素数的$\varphi$值的公式。

1. 黑板左侧面板显示$\varphi$的定义。

2. 黑板右侧面板列出示例$\varphi(5)$、$\varphi(8)$和$\varphi(15)$。

1. 右侧的示例计算被擦除。

2. 左侧的定义仍保持可见。

3. 随后在右侧写入新标题“命题”。

1. 左侧的$\varphi$定义保留在屏幕上。

2. 讲座主题仍为欧拉函数。

该视觉过渡标志着讲解从具体示例转向关于素数的一般性陈述。

1. 动画
   观察依据

   在‘证明：’下方，讲师写出了除数性质、假设$1\le m<p$以及蕴含式$p\nmid m\Rightarrow\gcd(p,m)=1$。

1. 文字‘证明：’。

2. 关于$p$的唯一正因数的句子。

3. 不等式$1\le m<p$。

4. 涉及$p\nmid m$与$\gcd(p,m)=1$的蕴含式。

1. 每一步证明都依次添加在右侧黑板上。

2. 论证从因数的性质出发，最终得出最大公约数的结论。

1. 左侧对$\varphi$的定义在整个过程中始终可见。

2. 命题$\varphi(p)=p-1$始终显示在证明上方。

书写顺序与逻辑结构一致：先写素数因数性质，再设任意$m<p$，接着排除被$p$整除的可能性，最后得出互质性。

1. 声音
   观察依据

   在计算 $\varphi(8)$ 时，说话者指出必须跳过偶数，因为它们与 8 的最大公约数不等于 1。

假设所有不超过 n 的数都计入总数。

仅统计满足 $\gcd(m,n)=1$ 的数 m；对于合数 n（如 8），许多数（例如偶数）被排除。

1. 声音
   观察依据

   讲师指出，该结论看似显然，因为只有素数的倍数才不与该素数互质；但为了练习，他们将给出一个更严谨的证明。

有人可能认为$\varphi(p)=p-1$无需证明，因为它从$p$的倍数行为来看显然成立。

该视频明确将直观理由与更严谨的证明区分开来，表明结论仍需从素因子和最大公约数（gcd）的定义出发加以论证。

1. 声音
   观察依据

   说话者将集合定义与模 n 的单位群联系起来。

2. 公式
   观察依据

   写下 = |$U_n$|。

互质数集合的基数恰好等于模 n 单位群的阶。

1. 公式
   观察依据

   该证明反复使用定义$\varphi(n)=\#\{1\le m<n\mid \gcd(m,n)=1\}$，并代入$n=p$。

命题$\varphi(p)=p-1$通过将$\varphi$的一般定义应用于特例$n=p$并分析$\gcd(p,m)$而得以证明。

1. 公式
   观察依据

   例子$\varphi(5)$、$\varphi(8)$和$\varphi(15)$被写作符合左侧定义的集合的基数。

所展示的例题通过列举相关的互素整数并计数，使抽象定义具体化。

1. 公式
   观察依据

   该证明将‘p 的唯一正因数是1和 p’与结论$\gcd(p,m)=1$联系起来，前提是$p\nmid m$已知。

证明中的关键要素是素数的因数结构，随后这一结构被转化为关于最大公约数（gcd）的陈述。

1. 公式
   观察依据

   黑板展示定义。

1. 欧拉函数的定义

1. 公式
   观察依据

   黑板展示对8的计算过程。

1. 例：$φ(8)$

1. 公式
   观察依据

   左侧黑板展示了$\varphi(n)$的完整定义。

1. 欧拉函数的定义

1. 公式
   观察依据

   右侧板书陈述并证明了 $\varphi(p)=p-1$（其中 为素数）$p$。

1. 素数的欧拉函数值等于$p-1$。
2. 证明$\varphi(p)=p-1$。

1. 公式
   观察依据

   黑板上列出了$\varphi(15)=\#\{1,2,4,7,8,11,13,14\}=8$。

2. 声音
   观察依据

   讲师提到跳过 12 和 9 再计数到 8。

1. 例题$\varphi(15)=8$
2. 通过列出互素整数来计算$\varphi(15)$。

1. 公式
   观察依据

   定义和证明均使用$\gcd(\cdot,\cdot)=1$来表达互质性。

1. 欧拉函数的定义
2. 证明$\varphi(p)=p-1$。

1. 公式
   观察依据

   黑板上还展示了$\varphi(5)=4$和$\varphi(8)=4$。

1. 这些例子在画面中可见，但在本片段的音频中未作详细讨论。

1. 其他可见的例子：$\varphi(5)$和$\varphi(8)$