费马小定理和欧几里得算法是什么？

美国数学竞赛AMC分代数、几何、概率与排列组合、数论几大类题型。其中，数论题最不为中国学生所熟悉，数论领域的定理也听着让人晕头转向的：

数论四大定理

威尔逊定理、欧拉定理、孙子定理、费马小定理并称数论四大定理。

1、威尔逊定理

若p为质数，则p可整除(p-1)!+1。

2、欧拉定理

(18世纪瑞士数学家欧拉，被称为“数学英雄”)

3、孙子定理

孙子定理，又称中国剩余定理。孙子定理是中国古代求解一次同余式组（见同余）的方法。

4、费马小定理

假如p是质数，若p不能整除a，则 a^(p-1) ≡1（mod p），若p能整除a，则a^(p-1) ≡0（mod p）。

若p是质数，且a,p互质，那么 a的(p-1)次方除以p的余数恒等于1。

（17世纪法国数学家费马）

估计大多数同学都没听说过这些。那么，是不是不会这些数论的定理，就不能做AMC10的数论题了呢？

答案是：不会数论定理，通过思路的学习，也同样可以掌握AMC10的数论题的。

不用费马小定理解2017 10B/第14题

用费马小定理解法如下：

简洁是非常简洁的。但是很多同学看了一脸懵啊，什么是Fermat’s Little Theorem呢？

当然，我们可以花时间去学习这个非常经典的定理，但说实话对于大多数同学来说，学了也记不住的。我一直主张参加竞赛要记忆的定理要最小化。

我们来看一下不用费马小定理的话，也可以用列举-找规律的方法来做，这也是数论题的一个常用方法。

【解答】题目研究的是N¹⁶除以5的余数，我们知道一个数除以5的余数只需要看个位就够了。虽然16次方比较费劲，但如果只乘出来个位计算量并不大。只乘出来个位的方式是每一次乘法只保留个位，然后继续乘下一次。

N	N4的个位	N16的个位	N16除以5的余数
1	1	1	1
2	6	6	1
3	1	1	1
4	6	6	1
5	5	5	0

然后根据同余定理，如果两个数同余的话，他们的幂次也同余，也就是6¹⁶和1¹⁶同余，7¹⁶和2⁶同余，8¹⁶和3¹⁶同余，9¹⁶和4¹⁶同余，10¹⁶和5¹⁶同余，以此类推，可以知道后面的规律都是每5个数里面有4个余数为1，1个（5的倍数）余数为0，因此余数为1的概率是4/5。

不用尼古莫斯定理解2018 B卷/第16题

用尼古莫斯定理的解法：

这条估计对小伙伴们更加生僻了，尼古莫斯定理又叫平方三角数定理，用以下图示比较清晰：连续立方数之和等于连加后的平方数。

如果我们不知道这个定理，也同样可以用列举-找规律的方法来做，这个方法是能通用于很多数论题。不用这个方法的话，可能每个题都得用不同的定理。

【解答】题目研究的是立方数除以6的余数，我们来列表找一下规律。

ai	ai3	ai3除以6的余数	ai和ai3除以6的余数的关系
1	1	1	相等
2	8	2	相等
3	27	3	相等
4	64	5	相等
5	125	5	相等

我们发现规律很明显，一个自然数的立方除以6后的余数和自然数本身相等。如果严密一点我们还可以证明一下（做选择题可省去证明）：

设一个自然数n=6k+r，其中r为n除以6的余数（r=0,1,2,3,4,5）。于是：

所以n³和r³同余，而根据上表，r³又和r本身同余。

得出以上结论后，我们对题里面的式子进行加工：

不用欧几里得算法解2020 A卷/第24题

用欧几里得算法的解法：

欧几里得算法，听着非常高深。其实就是求最大公约数的辗转相除法而已。所以同学们一般直接看英文的解答，会被里面的名词迷惑的，和我们平时的说法不同。换成“辗转相除法”这个解答就没有那么高深了，但是即使我们没有学过这个方法，用一般最大公约数（gcd）的概念也是可以做出来的。

【解答】根据题意，63和n+120之间的最大公约数是21，也就是说n+120是21的倍数，同时不能是63的倍数。我们可以用mod运算来写：

(n+120) mod 21=0, 也就是 n mod 21=6。

同时，n+63和120之间的最大公倍数是60，也就是n+63是60的倍数，同时不是120的倍数。我们也同样写出来：

（n+63）mod 60=0，也就是n mod 60 =57

所以我们需要找出除以21余6，同时除以60余57，同时超过1000的数。这是中国余数问题，如果没有学过的话也可以用简单的凑数方法来思考。

先找一个超过1000的最小满足除以60余57的数，为1017，然后再其之上每次增加一次60，就能满足除21余6，这个数是1077，但是这个数违反n+63不能是60的倍数。于是我们继续增加lcm(21,60)=420。增加一次为1497，但是这个数又违反了n+120不能是63的倍数。再增加420得1917，检查所有条件均满足。1+9+1+7=18就是我们的答案了。

不用苏菲热尔曼等式解2020 10B卷/第22题

用苏菲热尔曼等是的解法：

苏菲热尔曼，18世纪法国女数学家，看画像很端庄。虽说这个等式只是一个并不高深的代数分解式，但是如果诸如此类都得记住，那得记住多少代数式才够啊。当然因式分解能力强的同学也可以自己分解。

我们来看一下，如果不用这个公式，如何解出这个题。

【解答】这道题要求做一个多项式除法，多项式除法一般用竖式来做，但这个次数太高了，用竖式基本要铺满一屋子的纸采购。我们再用凑数方法。凑数的思路就是要尽量按照分母的倍数去凑。

可以看到，前三项都能被分母2¹⁰¹+2⁵¹+1整除，只有最后一项次数低于分母的次数，是余式，答案是201。这样没有用到任何定理也很简单。

以上四个例题都是属于AMC10里面中高难度的题，是中国学生的难点。学习专门的数论定理，和学习不用定理的通用思维方式，这两者并不矛盾。对于AMC10来说，很多题目不需要用专门的定理，就可以迎刃而解，而且非常锻炼思维能力。与此同时，开始逐步学习专门的数论定理，积累起来，也可以为之后的AIME，乃至大学的学习打好基础。