<我有你沒有，你有我沒有，之到底誰有誰沒有?來不及打完的(一)>

腦袋嗎?
圖/Mgmoscatello @Wikimedia Commons

腦袋嗎?

互質啦!

什麼是互質?

如果兩個正整數(這兒僅簡單討論正整數)的最大公因數是1，則這兩個數互質。也就是兩個數沒有(除了1以外的)共同的因數，換句話說，正整數A的因數不會出現在B裏頭，反之亦然。

從小到大一定有寫過一種題目，通常長這樣，請問在...之內與...互質的數有幾個?

確切來說，舉個例子，請問在25內與30互質有幾個?
於是乎開始列出1到25，然後一個一個檢查，反正也才25個嘛~
1跟30，2跟30，3跟30，4跟30，5跟30，6跟30，7跟30，哦哦，8跟30，blablabla...
在後來我們發展出新的檢索方式來加速檢查的速度，質因數分解。

這個我會讓我來~
圖/ Ron Armstrong @Wikimedia Commons

透過短除法，可以得到30的質因數分解如下:

然後回到1至25，便可以馬上剔除不與30互質的數字，也就是2的倍數、3的倍數以及5的倍數。因為，當該數字為2的倍數時，該數字與30便至少有2為他們的公因數。3的倍數與5的倍數，同理。

再進階些，可以使用排容原理:

我們讓圖中A、B、C區塊分別代表25裏頭2的倍數、3的倍數以及5的倍數，是故，A與B的交集(紅色與藍色的重疊區塊)即是那些同時為2的倍數也是3的倍數的那些數字，比如說6、12、18、24，可以發現，也就是6的倍數。

所以，計算25以內與30互質的個數，除了一個個檢查互質以外，也可以透過反面的想法，剔除所有不互質的數，剩下的便是與30互質的數了!

從上圖可以發現，整個不互質的數的區塊為(A區塊+B區塊+C區塊)再扣除重疊的(A與B區塊)、(A與C區塊)以及(B與C區塊)最後再加回(A與B與C區塊)，也就是...

|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|

實際上操作看看:

|A|=25以內2的倍數個數=(25÷2)取整數=12
|B|=25以內3的倍數個數=(25÷3)取整數=8
|C|=25以內5的倍數個數=(25÷5)取整數=5
|A∩B|=25以內6的倍數個數=(25÷6)取整數=4
|A∩C|=25以內10的倍數個數=(25÷10)取整數=2
|B∩C|=25以內15的倍數個數=(25÷15)取整數=1
|A∩B∩C|=25以內6的倍數個數=(25÷30)取整數=0

|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|


= 12 + 8 + 5 - 4 - 2 - 1 + 0

=18

於是，25內與30互質有...

25-18=7 個 (這兒我們將1也算進互質裏頭)

也就是1、7、11、13、17、19、23。

算錯就賞你銳利的爪爪 嘿嘿
圖/ Horstbu @Wikimedia Commons 

新定理出場前，我們稍微修改一下題目~
請問在30內與30互質有幾個?

根據上個例題，我們快速地將式子寫下:

(30÷2)+(30÷3)+(30÷5)-(30÷(2×3))-(30÷(2×5))-(30÷(3×5))+(30÷(2×3×5))

= 15 + 10 + 6 - 5 - 3 - 2 + 1

= 22

可以知道，30內與30不互質的數有22個，所以，30內與30互質的數便有30-22=8個。
接下來可以試試任意一個數字n，在n之內，與n互質的數有幾個?
有沒有辦法在過程中整理出更簡潔的式子呢。
打不完被趕去洗澡了...

繼續閱讀...

<我有你沒有，你有我沒有，之到底誰有誰沒有?接著討論的(二)>