数字是 (3³² − 2³²)。挑战在于找到这个数字的四个小于 100 的质因数。如果可以的话，没有计算机或计算器。
你会如何开始？
对我来说，这是使用平方差规则进行因式分解：
x ² − y ² = ( x − y )( x + y )
开始了…
(3³² − 2³²)
= (3¹⁶)² − (2¹⁶)²
= (3¹⁶ − 2¹⁶)(3¹⁶ + 2¹⁶)
然后……再做一次！
(3¹⁶ − 2¹⁶)(3¹⁶ + 2¹⁶)
= (3⁸ − 2⁸)(3⁸ + 2⁸)(3¹⁶ + 2¹⁶)
然后再次…
(3⁸ − 2⁸)(3⁸ + 2⁸)(3¹⁶ + 2¹⁶)
= (3⁴ − 2⁴)(3⁴ + 2⁴)(3⁸ + 2⁸)(3¹⁶ + 2¹⁶)
一次又一次……
(3⁴ − 2⁴)(3⁴ + 2⁴)(3⁸ + 2⁸)(3¹⁶ + 2¹⁶)
= (3² − 2²)(3² + 2²)(3⁴ + 2⁴)(3⁸ + 2⁸)(3¹⁶ + 2¹⁶)
= (3 − 2)(3 + 2)(3² + 2²)(3⁴ + 2⁴)(3⁸ + 2⁸)(3¹⁶ + 2¹⁶)
哇哦！（拳头碰撞）
我们有 6 个因素。我们只需要 4 个小于 100 的质因数。
但是我们还没有完成……
第一个因子 (3 − 2) 给出 1，它不属于素数（1 是唯一既不是素数也不是合数的正整数）。
- 第二个因数 (3 − 2) 给出 5，它是质数。那是一个！
- 第三个因数 (3² + 2²) 得到 13，这也是质数。那是两个！
- 第四个因子 (3⁴ + 2⁴) 给出 81 + 16 = 97，这是素数。那是三个！
但是然后呢？
我不得不承认，我认为上面的因式分解会让我一路找到答案。为了提供一些背景信息，这是英国数学奥林匹克竞赛第 1 轮第 1 题（从 2006 年开始）。它应该在我的击球区内。
但是这个问题肯定要求四个小于 100 的质因数。
那我们还能做什么？
剩下的因素是 (3⁸ + 2⁸) 和 (3¹⁶ + 2¹⁶)。我不知道有什么方便的公式可以分解这些。我确实知道一个分解x ³ + y ³的公式，但 8 和 16 都不是 3 的倍数，所以我看不出这有什么用。
我想将 3⁸ 重新表示为 (2 + 1)⁸ 并使用二项式定理对其进行扩展，但这将给出 9 项，而且我看不出这会有什么帮助。
这时，我伸手去拿我的计算器。
我对我的 TI-nspire 能够分解这么大的数字感到有些惊讶！但要向设计它的德州人致敬，因为它做到了：
所以 17 是难以捉摸的第四素数。但为什么？
如果没有计算器，我们怎么能算出来呢？
好吧，一种方法是拿出笔和纸，卷起袖子做一些老式的算术。
3⁸ + 2⁸ = 81² + 16²，结果是 6817。如果你心算好，或者愿意做足够多的试错，你可能会认出这是 401 × 17。
但是，作为一个奥林匹克问题，当然有一个更优雅的解决方案。它涉及一种完全不同的方法……
模运算
实际上，这就是我的学生首先采取的解决问题的方法。
她能够证明 5 是质因数，因为 3³² 和 2³² 都等于 1 mod 5（这意味着它们在除以 5 后都留下 1 的余数）。
这是如何运作的？
任何数字的幂总是循环重复，模n。在这种情况下，3 的幂在长度为 4、模 5 的循环中重复，对于 2 的幂、模 5 也是如此。
一旦其中一个幂为 1，幂的循环就必须从头开始重复（因为 1 × a = a）。
现在，因为 2 和 3 的幂都以 4 为周期重复，我们有
2³² ≡ 2⁴ (mod 5) ≡ 1 (mod 5)
和
3³² ≡ 3⁴ (mod 5) ≡ 1 (mod 5)
所以 (3³² − 2³²) ≡ (1 − 1) (mod 5) ≡ 0 (mod 5)
这证明 5 是 (3³² − 2³²) 的因数。
但是，我们是否期望对所有p小于 100 的素数以p为模来研究这个幂循环，直到我们找到四个有效的素数？
不，我们还可以使用其他东西：
费马小定理
对于质数p和不可被p整除的整数 a ：
a ^( p − 1) ≡ 1 (mod p )
这不是高中数学课程的一部分（至少我来自那里），但每个认真的奥林匹克竞赛学生都知道。
证明并不简单（如果您有兴趣，请参阅此处），但这里是如何应用定理来证明 17 是 (3³² − 2³²) 的因数。
应用p = 17的定理，可以直接得出 2^16 和 3^16 都等于 1 mod 17。
反向计算，这意味着 2⁸ 和 3⁸ 必须是 1 mod 17 或− 1 mod 17（因为它们是唯一平方等于 1 的数字）。
再次逆向推导，很容易看出 2⁴ = 16 ≡ − 1 (mod 17)
但是 3⁴ = 81，既不是 1 也不是− 1 mod 17。17 最接近 81 的倍数是 5 × 17 = 85，所以3⁴ ≡ − 4（模 17）。
这足以证明 3⁸ = (3⁴)² ≡ ( − 4)² (mod 17)。
这给出 16 (mod 17) ≡ − 1 (mod 17)。
所以 (2⁸ + 3⁸) (mod 17)
≡ (1 − 1) (mod 17)
≡ 0 (mod 17)
这样，我们就完成了。