費馬小定理和歐幾裏得算法是什麽？

美國數學競賽AMC分代數、幾何、概率與(yu) 排列組合、數論幾大類題型。其中，數論題最不為(wei) 中國學生所熟悉，數論領域的定理也聽著讓人暈頭轉向的：

數論四大定理

威爾遜定理、歐拉定理、孫子定理、費馬小定理並稱數論四大定理。

1、威爾遜定理

若p為(wei) 質數，則p可整除(p-1)!+1。

2、歐拉定理

(18世紀瑞士數學家歐拉，被稱為(wei) “數學英雄”)

3、孫子定理

孫子定理，又稱中國剩餘(yu) 定理。孫子定理是中國古代求解一次同餘(yu) 式組（見同餘(yu) ）的方法。

4、費馬小定理

假如p是質數，若p不能整除a，則 a^(p-1) ≡1（mod p），若p能整除a，則a^(p-1) ≡0（mod p）。

若p是質數，且a,p互質，那麽(me) a的(p-1)次方除以p的餘(yu) 數恒等於(yu) 1。

（17世紀法國數學家費馬）

估計大多數同學都沒聽說過這些。那麽(me) ，是不是不會(hui) 這些數論的定理，就不能做AMC10的數論題了呢？

答案是：不會(hui) 數論定理，通過思路的學習(xi) ，也同樣可以掌握AMC10的數論題的。

不用費馬小定理解2017 10B/第14題

用費馬小定理解法如下：

簡潔是非常簡潔的。但是很多同學看了一臉懵啊，什麽(me) 是Fermat’s Little Theorem呢？

當然，我們(men) 可以花時間去學習(xi) 這個(ge) 非常經典的定理，但說實話對於(yu) 大多數同學來說，學了也記不住的。我一直主張參加競賽要記憶的定理要最小化。

我們(men) 來看一下不用費馬小定理的話，也可以用列舉(ju) -找規律的方法來做，這也是數論題的一個(ge) 常用方法。

【解答】題目研究的是N¹⁶除以5的餘(yu) 數，我們(men) 知道一個(ge) 數除以5的餘(yu) 數隻需要看個(ge) 位就夠了。雖然16次方比較費勁，但如果隻乘出來個(ge) 位計算量並不大。隻乘出來個(ge) 位的方式是每一次乘法隻保留個(ge) 位，然後繼續乘下一次。

然後根據同餘(yu) 定理，如果兩(liang) 個(ge) 數同餘(yu) 的話，他們(men) 的冪次也同餘(yu) ，也就是6¹⁶和1¹⁶同餘(yu) ，7¹⁶和2⁶同餘(yu) ，8¹⁶和3¹⁶同餘(yu) ，9¹⁶和4¹⁶同餘(yu) ，10¹⁶和5¹⁶同餘(yu) ，以此類推，可以知道後麵的規律都是每5個(ge) 數裏麵有4個(ge) 餘(yu) 數為(wei) 1，1個(ge) （5的倍數）餘(yu) 數為(wei) 0，因此餘(yu) 數為(wei) 1的概率是4/5。

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

用尼古莫斯定理的解法：

這條估計對小夥(huo) 伴們(men) 更加生僻了，尼古莫斯定理又叫平方三角數定理，用以下圖示比較清晰：連續立方數之和等於(yu) 連加後的平方數。

如果我們(men) 不知道這個(ge) 定理，也同樣可以用列舉(ju) -找規律的方法來做，這個(ge) 方法是能通用於(yu) 很多數論題。不用這個(ge) 方法的話，可能每個(ge) 題都得用不同的定理。

【解答】題目研究的是立方數除以6的餘(yu) 數，我們(men) 來列表找一下規律。

我們(men) 發現規律很明顯，一個(ge) 自然數的立方除以6後的餘(yu) 數和自然數本身相等。如果嚴(yan) 密一點我們(men) 還可以證明一下（做選擇題可省去證明）：

設一個(ge) 自然數n=6k+r，其中r為(wei) n除以6的餘(yu) 數（r=0,1,2,3,4,5）。於(yu) 是：

所以n³和r³同餘(yu) ，而根據上表，r³又和r本身同餘(yu) 。

得出以上結論後，我們(men) 對題裏麵的式子進行加工：

不用歐幾裏得算法解2020 A卷/第24題

用歐幾裏得算法的解法：

歐幾裏得算法，聽著非常高深。其實就是求最大公約數的輾轉相除法而已。所以同學們(men) 一般直接看英文的解答，會(hui) 被裏麵的名詞迷惑的，和我們(men) 平時的說法不同。換成“輾轉相除法”這個(ge) 解答就沒有那麽(me) 高深了，但是即使我們(men) 沒有學過這個(ge) 方法，用一般最大公約數（gcd）的概念也是可以做出來的。

【解答】根據題意，63和n+120之間的最大公約數是21，也就是說n+120是21的倍數，同時不能是63的倍數。我們(men) 可以用mod運算來寫(xie) ：

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

同時，n+63和120之間的最大公倍數是60，也就是n+63是60的倍數，同時不是120的倍數。我們(men) 也同樣寫(xie) 出來：

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

所以我們(men) 需要找出除以21餘(yu) 6，同時除以60餘(yu) 57，同時超過1000的數。這是中國餘(yu) 數問題，如果沒有學過的話也可以用簡單的湊數方法來思考。

先找一個(ge) 超過1000的最小滿足除以60餘(yu) 57的數，為(wei) 1017，然後再其之上每次增加一次60，就能滿足除21餘(yu) 6，這個(ge) 數是1077，但是這個(ge) 數違反n+63不能是60的倍數。於(yu) 是我們(men) 繼續增加lcm(21,60)=420。增加一次為(wei) 1497，但是這個(ge) 數又違反了n+120不能是63的倍數。再增加420得1917，檢查所有條件均滿足。1+9+1+7=18就是我們(men) 的答案了。

不用蘇菲熱爾曼等式解2020 10B卷/第22題

用蘇菲熱爾曼等是的解法：

蘇菲熱爾曼，18世紀法國女數學家，看畫像很端莊。雖說這個(ge) 等式隻是一個(ge) 並不高深的代數分解式，但是如果諸如此類都得記住，那得記住多少代數式才夠啊。當然因式分解能力強的同學也可以自己分解。

我們(men) 來看一下，如果不用這個(ge) 公式，如何解出這個(ge) 題。

【解答】這道題要求做一個(ge) 多項式除法，多項式除法一般用豎式來做，但這個(ge) 次數太高了，用豎式基本要鋪滿一屋子的紙采購。我們(men) 再用湊數方法。湊數的思路就是要盡量按照分母的倍數去湊。

可以看到，前三項都能被分母2¹⁰¹+2⁵¹+1整除，隻有最後一項次數低於(yu) 分母的次數，是餘(yu) 式，答案是201。這樣沒有用到任何定理也很簡單。

以上四個(ge) 例題都是屬於(yu) AMC10裏麵中高難度的題，是中國學生的難點。學習(xi) 專(zhuan) 門的數論定理，和學習(xi) 不用定理的通用思維方式，這兩(liang) 者並不矛盾。對於(yu) AMC10來說，很多題目不需要用專(zhuan) 門的定理，就可以迎刃而解，而且非常鍛煉思維能力。與(yu) 此同時，開始逐步學習(xi) 專(zhuan) 門的數論定理，積累起來，也可以為(wei) 之後的AIME，乃至大學的學習(xi) 打好基礎。