正整数的常见表示方法

· · 算法·理论

Update on 2026/7/5：添加一种表示方法，并修改了一些表达错误。

进制表示

十进制

对于正整数 n，我们可以得到：

n = \sum_{i = 0}^k a_i \cdot 10^i

其中 0 \le a_i \le 9，a_k \ne 0，k 为正整数 n 的位数。

我们平常使用的就是十进制表示方法。

b 进制

对于十进制下正整数的 n，在 b 进制下表示为：

n = \sum_{i = 0}^{k_b} a_i \cdot b^i

其中 0 \le a_i < b，a_k \ne 0。

在计算机最底层的语言就是用二进制编写的。

同时，这里有一个结论：

任意正整数在给定进制 b \ge 2 下进制表示唯一。

算术运算拆分表示

自然数和拆分

把 n 写成若干正整数之和，即：

n = \sum_i x_i

其中 x_i \in \mathbb{N}^+

这能拆分的证明是显然的。

乘法素因数分解

这个又称作算术基本定理。

定理：

对于任意一个大于 1 的整数 n，一定能被唯一分解为素数的乘积。 即：

n = \prod_{i} p_i^{\alpha_i}

其中 p_i 为质数，\alpha_i 为正整数。

证明：

存在性：

假设存在一个最小的大于 1 的正整数 n，它的的因数均为合数。

即 n = a \times b，其中 a, b 也为合数，并且它们的因数均为合数。

与上面的假设矛盾，存在性得证。 唯一性： 假设存在一个 $n$ 满足是 $n = ab$ 和 $n = ac$，其中 $a, b, c$ 均为质数。 那么 $b$ 与 $c$ 是互质的，所以 $ab$ 和 $ac$ 的最小公因数是 $a$，即 $(n, n) = a$，又因为 $(n, n) = n$，所以 $n = a$，得出 $b = c = 1$。 但是 $b, c$ 为质数，与求出的值矛盾，唯一性得证。 ## 数论经典表示 ### 带余除法表示 对任意正整数 $m \ge 1$ 和正整数 $n$，存在唯一 $q, r \in \mathbb{N}$，满足： $$ n = qm + r $$ 同时，$0 \le r < m$。 考虑证明： 存在性： 对于固定的 $m$，和一个的 $q$，有区间 $[qm,(q+1)m-1]$。 对于每个 $q$，有它们对应的相邻的区间所代表的整数域是连续的。故存在性得证。 唯一性： 假设存在两组 $(q_1, r_1)$，$(q_2, r_2)$ 都满足： $$ \begin{cases} n = q_1m + r_1 & 0 \le r_1 < m\\ n = q_2m + r_2 & 0 \le r_2 < m \end{cases} $$ 将两式相减得到 $m(q_1-q_2) = r_2-r_1$。 设 $q_1-q_2 = d$，而且 $d$ 为整数。 所以得到 $md = r_2-r_1$。 由余数的范围得到 $-m < md < m

简化的到 -1 < d < 1。

因为 d 为整数，所以 d = 0。

带回相减后的式子得到 r_2 - r_1 = 0，唯一性得证。

2 的幂和

这个与 b 进制表示基本一致，这里就不过多赘述。

拉格朗日四平方定理

定理：任意正整数可表为至多四个整数平方和。即满足任意一个正整数 n，使得：

n = a^2 + b^2 + c^2 + d^2

其中 a, b, c, d \in \mathbb{Z}。

考虑证明：

我们只需要证明三个东西就可以了。

首先需要证明：

(x_1^2+x_2^2+x_3^2+x_4^2)(y_1^2+y_2^2+y_3^2+y_4^2) = z_1^2+z_2^2+z_3^2+z_4^2

这个东西中的 z_1, z_2, z_3, z_4 可以被 x_1, x_2, x_3, x_4, y_1, y_2, y_3, y_4 表示出来就行了。

其次，根据算术基本定理，每个大于 1 的数能被分解为多个素数的乘积，所以只需要证明质数能被四个整数的平方和表示出来就行了。

最后，因为 1 不能被适用于算术基本定理，所以，要找出 1 的表达式。

我们先易后难。

然后，我们要表示 $z_1, z_2, z_3, z_4$。 当然，这是可以被表示出来的。 通过与欧拉的联系，这里有一组特解： $$ \begin{cases} z_1 = x_1y_1-x_2y_2-x_3y_4-x_4y_4 \\ z_2 = x_1y_2+x_2y_1+x_3y_4-x_4y_3 \\ z_3 = x_1y_3-x_2y_4+x_3y_1+x_4y_2 \\ z_4 = x_1y_4+x_2y_3-x_3y_2+x_4y_1 \\ \end{cases} $$ 那么，最后一个问题，质数是否能被表示。 对于偶质数： 因为只存在一个 $2$，所以可以直接计算得到。 $$ 2 = 1^2 + 1^2 + 0^2 + 0^2 $$ 所以偶质数是可以用四个正整数的平方所表示的。 对于奇质数： 我们有一个引理： 如果 $p$ 是一个奇质数，那么存在整数 $x,y$，使得 $p \mid (x^2+y^2+1)$。这个东西是比较好证，只需要用鸽巢原理即可。 所以对于 $p$，假设： $$ kp = x^2 + y^2 + 1^2 + 0^2 $$ 只要我们得到 $k = 1$，就可以证明出来了。 我们将这个 $1, 0$ 变为变量。 得到： $$ kp = \sum_{i = 1}^4 a_i^2 $$ 对每个 $a_i$ 取模 $k$ 剩余得到： $$ \exists b_i \in \mathbb{Z},|b_i| \le \frac{k}{2}, a_i \equiv b_i \pmod k $$ 对于这个条件 $|b_i| \le \frac{k}{2}$，可能会有疑问，其实这个 $b_i$ 可以是负余数，所以才有这个条件。 我们记： $$ \sum_{i = 1}^4 b_i^2 = lk,l \in \mathbb{N} $$ 可以大致推一下这个的由来。 因为 $a_i^2 \equiv b_i^2 \pmod k$，所以可以得到这个式子 $\sum_{i = 1}^4 a_i^2 \equiv \sum_{i = 1}^4 b_i^2 \pmod k$。 因为 $kp \equiv 0 \pmod k$，那么 $\sum_{i = 1}^4 a_i^2 \equiv 0 \pmod k$，所以 $\sum_{i = 1}^4 b_i^2 \equiv 0 \pmod k$ 的。 所以才有了上面的式子。 因为 $lk \le 4⋅(\frac{k}{2})^2$，所以 $l \le k$。 分情况讨论一下： 当 $l = 0$ 时，所以 $k \mid a_i$ 可以得到 $k^2 \mid kp$，所以 $k \mid p$，因为 $p$ 素数，$k < p$，所以可以得出 $k = 1$。 当 $l = k$ 时，所以 $b_i = \pm \frac{k}{2}$，那么 $a_i \equiv \frac{k}{2}\pmod k$，然后得出 $2a_i \equiv 0 \pmod k$，所以 $k$ 偶数。 我们带进去会发现 $k$ 只能为 $2$ 或者 $4$。 当 $k = 2$ 时，条件矛盾，故不会出现这种情况。 当 $k = 4$ 时，$p$ 直接可以被写成四平方和，所以 $k$ 可以等于 $1$。 当 $1 \le l < k$ 时，可以得到 $(kp)(lk) = z_1^2+z_2^2+z_3^2+z_4^2$，左边为 $k^2lp$。 因为 $a_i \equiv b_i \pmod k$，所以等式右端四个平方项全被 $k$ 整除，设 $z_i = kd_i$，于是 $k^2lp = k^2 \sum_{i = 1}^4 d_i^2$，于是乎 $lp = \sum_{i = 1}^4 d_i^2$。 因为 $l < k$，$lp$ 为四平方和，新的 $k$ 将会递减，在所有情况下，最后只能为 $1$。 证毕。 现在，有几道题可以水过去了（？）。 - CF2231F - P2019 ## 数列表示 ### 齐肯多夫定理 定理：每一个正整数都可以**唯一**表示为若干个互不相同的、且不相邻的斐波那契数之和。 举一个例子。$4 = 3 + 1$，同时 $4 = 2 + 1 + 1$，但是后者不满足互不相同和不相邻两个条件。 考虑证明。 先证明存在性，那么我们需要证明的命题就是每一个正整数都可以表示为若干个互不相同的、且不相邻的斐波那契数之和。 对于证明一段区间使得命题成立，通常采用数学归纳法。 即，首先证明边界情况，然后由特殊推一般。 对于 $1$ 到 $3$ 均为斐波那契数，$4$ 只有 $1 + 3$ 这种情况。 我们假设所有**小于** $m(m \ge 5)$ 的正整数，命题都成立，那么只需要证明 $m$ 也可以让命题成立就证明出存在性了。 我们找到第一个比 $m$ 小的斐波那契数 $f_n$。 令 $m_2 = m - f_n$，则可以得到 $m_2 < f_{n+1}-f_n$，即 $m_2 < f_{n-1}$。所以我们可以得出，$m_2$ 的齐肯多夫的表示中，没有 $f_{n-1}$ 这个数，所以存在性得证。 然后考虑证明唯一性。 现在的命题就是最开头的定义了。 我们定义新的斐波那契数列，即 $f_1 = 1,f_2 = 2, f_n=f_{n-1}+f_{n-2}$，下面的证明都是用的是这个新数列。 这样呈现的是 $f = {1, 2, 3, 5, 7 \dots}$。 依旧考虑用数归证明。 我们假设所有**小于** $m(m \ge 5)$ 的正整数，命题都成立，那么只需要证明 $m$ 也可以让命题成立就证明出唯一性了。 我们猜测 $m$ 的齐肯多夫的表示中一定有 $f_n$ 这个数，$f_n$ 表示第一个比 $m$ 小的斐波那契数。 那么就只需要证明 $f_{n-1}+f_{n-3}+f_{n-5}+\dots < f_n$ 就行了。 这里，读者可能有个问题。 为什么右式是这样子的？这样既可以满足命题中不相邻的条件，又可以让此时的和最大。 回归正题，注意到，右式就相当于同奇偶性相加，而且对于两个数 $f_n$，$f_{n-1}$ 可以得到 $f_{n+1}$。 那么对于 $n$，右式加一个 $1$ 就是 $f_n$，所以我们的猜测式正确的。 不理解？举几个例子看看吧。 对于 $n = 7$ 来说，得出： $$ \begin{aligned} f_6+f_4+f_2+1 &= f_6+f_4+f_2+f_1 \\ &= f_6+f_4+f_3 \\ &= f_6+f_5 \\ &= f_7 \end{aligned} $$ 所以 $f_6+f_4+f_2+1 = f_7$。 再来，对于 $n = 8$ 来说，可知： $$ \begin{aligned} f_7+f_5+f_3+f_1+1 &= f_7+f_5+f_3+2 \\ &= f_7+f_5+f_3+f_2 \\ &= f_7+f_5+f_4 \\ &= f_7+f_6 \\ &= f_8 \end{aligned} $$ 所以 $f_7+f_5+f_3+f_1+1 = f_8$。 总体来说，$f_{n-1}+f_{n-3}+f_{n-5}+\dots < f_n$ 是正确的。 所以 $m$ 的齐肯多夫的表示中一定有 $f_n$ 这个数。 后面的，便跟原来的证明存在性的就一样了，这里不过多赘述。 推荐题目： - P3424 ## 总结 综上，正整数的常见表示方法基本就是这些了。 欢迎补充和指出问题（？）。