四平方数定理：探索自然数的平方和奥秘

什么是四平方数定理？

四平方数定理（Lagrange's four-square theorem），又称拉格朗日四平方和定理，是数论中一个极其优美且基础的定理。该定理断言：任何一个正整数都可以表示为四个整数的平方和。

用数学符号表示，对于任意正整数 ，都存在非负整数 ，使得：

需要注意的是，这里的“整数”通常指非负整数，且允许某些系数为零。例如，数字 1 可以表示为 ，数字 3 可以表示为 。

1.1 最少需要几个平方数？

虽然定理保证四个平方数足够，但许多数实际上可以用更少的平方数表示。

• 1个平方数：完全平方数，如 1, 4, 9, 16... (n = k²)
• 2个平方数：如 2 (1²+1²), 5 (2²+1²), 10 (3²+1²)...
• 3个平方数：如 3 (1²+1²+1²), 6 (2²+1²+1²)...
• 4个平方数：必须使用四个非零平方数的数有特定形式。

历史背景与发现历程

四平方数定理的发现并非一蹴而就，它跨越了数百年的数学史，凝聚了多位伟大数学家的智慧。

数学证明思路解析

虽然拉格朗日的原始证明非常复杂，但现代数学教育中通常采用简化版的证明思路，主要依赖于欧拉四平方恒等式和无限下降法。

3.1 欧拉四平方恒等式

莱昂哈德·欧拉（Leonhard Euler）发现了一个重要的恒等式，它表明两个可以表示为四个平方数之和的数的乘积，仍然可以表示为四个平方数之和。

(a₁² + a₂² + a₃² + a₄²)(b₁² + b₂² + b₃² + b₄²) =
(c₁² + c₂² + c₃² + c₄²)
其中：
c₁ = a₁b₁ - a₂b₂ - a₃b₃ - a₄b₄
c₂ = a₁b₂ + a₂b₁ + a₃b₄ - a₄b₃
c₃ = a₁b₃ - a₂b₄ + a₃b₁ + a₄b₂
c₄ = a₁b₄ + a₂b₃ - a₃b₂ + a₄b₁
            

这意味着，如果我们能证明所有素数都可以表示为四个平方数之和，那么根据恒等式，所有合数也都可以表示为四个平方数之和，从而完成定理的证明。

3.2 费马无限下降法

证明素数情形的关键工具是费马的无限下降法（Infinite Descent）。其核心逻辑是：假设存在一个不能表示为四个平方数之和的最小正整数 ，然后构造出一个更小的正整数 ，它也具有相同的性质，这与 是最小的假设矛盾。

具体步骤包括：
1. 对于任意素数 ，存在整数 使得 能被 整除。
2. 构造一个倍数 ，其中 。
3. 通过模运算和恒等式，将 减小，直到 ，从而证明 本身可以表示为四个平方数之和。

编程实战：如何求解四平方和？

在计算机科学中，四平方数定理常被用作算法练习题，例如 LeetCode 上的 "Perfect Squares" 或 "Sum of Square Numbers"。以下是几种常见的实现思路。

import math
def numSquares(n):
    """
    返回表示 n 所需的最少完全平方数个数
    """
    # 预处理平方数列表
    squares = [ii for i in range(1, int(math.sqrt(n)) + 1)]
    # 如果 n 本身是平方数，直接返回 1
    if n in squares:
        return 1
    # 检查是否是两个平方数之和
    for s in squares:
        if (n - s) in squares:
            return 2
    # 根据勒让德三平方定理，排除形如 4^a(8k+7) 的数
    while n % 4 == 0:
        n //= 4
    if n % 8 == 7:
        return 4
    # 否则，根据定理，结果一定是 3
    return 3
测试
print(numSquares(12))  # 输出: 3 (4+4+4)
print(numSquares(13))  # 输出: 2 (9+4)
                

#include 
#include 
#include 
#include 
using namespace std;
int numSquares(int n) {
    vector dp(n + 1, INT_MAX);
    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j  j <= i; ++j) {
            dp[i] = min(dp[i], dp[i - j  j] + 1);
        }
    }
    return dp[n];
}
int main() {
    cout << numSquares(12) << endl; // Output: 3
    cout << numSquares(13) << endl; // Output: 2
    return 0;
}
                

import java.util.;
class Solution {
    public int numSquares(int n) {
        Queue queue = new LinkedList<>();
        Set visited = new HashSet<>();
        queue.offer(n);
        visited.add(n);
        int depth = 0;
        while (!queue.isEmpty()) {
            depth++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int curr = queue.poll();
                for (int j = 1; j  j <= curr; j++) {
                    int next = curr - j  j;
                    if (next == 0) return depth;
                    if (!visited.contains(next)) {
                        visited.add(next);
                        queue.offer(next);
                    }
                }
            }
        }
        return -1;
    }
}
                

算法复杂度分析：
1. DP方法：时间复杂度 ，空间复杂度 。
2. BFS方法：在最坏情况下时间复杂度较高，但通常能找到较浅的解。
3. 数学优化方法：利用勒让德三平方定理，可以将时间复杂度降低到 或 ，这是最高效的方法。

网友们还关心：与四平方数定理紧密相关的数学知识

在学习了四平方数定理之后，许多网民和数学爱好者往往会进一步探索以下相关话题。这些知识不仅丰富了数论的版图，也在密码学、物理学等领域有着潜在的应用。

常见问题解答 (FAQ)