date
type
status
slug
summary
tags
category
password
icon
我很早就听说过费马小定理有一种组合证明的方式,也一直对此很好奇,今天终于见到了一道让我们用组合数学来证明费马小定理的题目(出自 UC Berkeley 的公开课 CS70),于是便记录下来分享一下。本文假定读者了解基础的模运算。

题目描述

是一个素数,而 是一个正整数。我们有 种不同颜色的珠子,且任何两颗相同颜色的珠子是无法区分的。
假设我们需要将 个珠子放在一条成环的绳子上,形成一条腕带。如果通过旋转一条腕带可以得到另一条腕带,则认为这两条腕带是相同的。
例如,如果我们有 种颜色,红色 (R)、绿色 (G) 和蓝色 (B),那么长度 的项链RGGBG、GGBGR、GBGRG、BGRGG 和 GRGGB 都是相同的,因为它们都是各自的旋转版本。
如果我们要求腕带上的珠子颜色不全相同,求出所有不同的腕带的数量。

解决问题

如何解决这个问题?让我们来分析几个更简单的问题,循序渐进。
是一个素数而 是一个正整数。我们有 种不同颜色的珠子,其中任何两颗相同颜色的珠子是无法区分的。考虑以下问题:
  1. 珠子的排列方式: 我们将 个珠子放在一根不成环的绳子上。问:最多使用 种不同颜色的 个珠子,有多少种不同的排列方式?
  1. 多色串珠序列: 在上述 个珠子的序列中,至少使用两种颜色的排列方式有多少种?
 
这两个问题应该都不困难,第一个问题的答案是 ,第二个问题的答案是 ,证明给读者留作练习。让我们回到最开始的问题,如果腕带成环且腕带上至少有两种颜色的珠子,我们能找到多少种不同的腕带?
首先让我们考虑一个腕带对应多少个不同的序列。有以下命题成立:对一个给定的总长度为 的腕带,如果腕带上至少有两种颜色的珠子且 是一个素数,那么通过旋转它我们可以得到 种不同的序列。
比如对 RGGBG 这个腕带,通过旋转我们可以得到 RGGBG、GGBGR、GBGRG、BGRGG 和 GRGGB 五种不同的序列。
为什么这个命题成立?让我们用反证法。假设旋转了 次得到的序列与不旋转的序列相同,那么显然 . 设不旋转的序列为 , 并设 ,就有
特别地,有
由于 是素数,结合 ,故 . 因此, 在模 意义下两两不等,从而有 ,这与”腕带上至少有两种颜色的珠子“矛盾。因此,对一个给定的总长度为 的腕带,如果腕带上至少有两种颜色的珠子,那么通过旋转它我们可以得到 种不同的序列。
而我们前面已经知道一共有 种珠子序列(由问题2),因此我们一共能找到 种不同的腕带。根据组合意义, 是一个”数量“,从而它一定是一个整数,我们也就由此证明了费马小定理:
读者不妨试着用一个合数 代替 ,并看看我们的推导过程会在哪里出现问题。

参考资料

LeetCode 周赛 365 解析CS188 Reinforcement Learning笔记