初等数论证明题：求证mk范围内与m互素的数的计数等式

嘿，你的思路完全正确！这个等式本质上是欧拉函数的经典性质，咱们把这个证明严谨地梳理出来：

核心前提：互素性与模m余数的关系 #

首先明确一个由欧几里得算法直接推导的关键结论：

对于任意整数n，gcd(n, m) = gcd(n mod m, m)

这意味着：一个数和m互素，当且仅当它除以m的余数和m互素。这个结论是整个证明的核心。

正式证明过程 #

我们先定义欧拉函数φ(m)：它表示1≤n≤m范围内与m互素的正整数的个数，即：
$$\varphi(m) = \sum\limits_{\substack{1\le n \le m\\gcd(n,m)=1}} 1$$

我们的目标是证明：
$$\sum\limits_{\substack{1\le n \le mk \\gcd(n,m)=1}} 1 =k \cdot \varphi(m)$$

步骤1：将1~mk的数分组 #

把区间[1, mk]中的数分成k个互不重叠的子区间，每个区间对应一个完整的模m剩余类：

• 第1组：$1 \le n \le m$，对应余数$r=1,2,...,m$
• 第2组：$m+1 \le n \le 2m$，每个数可表示为$n = m + r$（$r=1,2,...,m$）
• ...
• 第k组：$(k-1)m +1 \le n \le km$，每个数可表示为$n = (k-1)m + r$（$r=1,2,...,m$）

步骤2：每组中与m互素的数的数量 #

对于任意一组中的数$n = qm + r$（其中$q$是0到k-1的整数，$r∈[1,m]$），根据核心前提：
$$\gcd(n, m) = \gcd(qm + r, m) = \gcd(r, m)$$

因此，$n$与m互素当且仅当$r$与m互素。而每组中$r$遍历1到m，所以每组中与m互素的数的数量恰好是$\varphi(m)$。

步骤3：求和得到总数 #

一共有k个这样的组，每个组贡献$\varphi(m)$个满足条件的数，因此总数为$k \cdot \varphi(m)$，即：
$$\sum\limits_{\substack{1\le n \le mk \\gcd(n,m)=1}} 1 =k \cdot \sum\limits_{\substack{1\le n \le m\\gcd(n,m)=1}} 1$$

总结 #

你的思路完全切中要害：模m意义下的同余类直接决定了互素性，每个完整的剩余类里的互素数数量和1~m区间的一致，k个类自然就是k倍的数量。

内容的提问来源于stack exchange，提问作者vfantina